search

INSAlgo / coding-battle2020

MIT License
2 stars 10 forks source link

Soucis limites de temps pour le 6 ème problème #7

Open cup2of2tea opened 3 years ago

cup2of2tea commented 3 years ago

Bonjour,

J'étais curieux de voir quelle était la solution pour le dernier, étant donné qu'une complexité est toujours compliquée à évaluer pour des solutions à bases de "pseudo-bruteforce élagué", ce qui est un peu le cas de la solution donné vue qu'il peut exister énormément de chemins menant à 50 (et donc énormément de subsets sur lesquels appliquer KMP).

J'ai donc stress-testé la solution avec des testcases générés aléatoirement, mais respectant les contraintes de l'énoncé.

Pour ce test:

50
27
1 1 2 2 3 3 3 4 4 5 5 6 6 7 8 9 9 10 10 11 12 12 13 13 14 14 14

J'obtiens une exécution en locale de ~= 25 secondes. Sur ideone.com, j'obtiens également un dépassement de la limite maximale (15 secondes).

Est-on certain de la validité de cette solution?

Merci d'avance

cup2of2tea commented 3 years ago

Même problème mais en bien pire pour le 4 ème problème (qui est aussi un élagage de bruteforce): 25 secondes pour des cas à dimension 8x8 (là je laisse tourner du 20x20 mais ça prend plus de 5 minutes).

arfevrier commented 3 years ago

Bonjour,

J'étais curieux de voir quelle était la solution pour le dernier, étant donné qu'une complexité est toujours compliquée à évaluer pour des solutions à bases de "pseudo-bruteforce élagué", ce qui est un peu le cas de la solution donné vue qu'il peut exister énormément de chemins menant à 50 (et donc énormément de subsets sur lesquels appliquer KMP).

J'ai donc stress-testé la solution avec des testcases générés aléatoirement, mais respectant les contraintes de l'énoncé.

Pour ce test:

50
27
1 1 2 2 3 3 3 4 4 5 5 6 6 7 8 9 9 10 10 11 12 12 13 13 14 14 14

J'obtiens une exécution en locale de ~= 25 secondes. Sur ideone.com, j'obtiens également un dépassement de la limite maximale (15 secondes).

Est-on certain de la validité de cette solution?

Merci d'avance

J'ai proposé une solution du problème F qui améliore la vitesse d'exécution du problème. ~1.3s pour résoudre l'input cité. https://github.com/INSAlgo/coding-battle2020/pull/22