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

[cup2of2tea]

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]

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]

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é.
#22