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
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:
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