Bonjour,
Quelqu'un aurait-il une "correction" à me proposer pour cet exercice, si possible en Python ? Je galère depuis quelques jours sur cet exercice : mon algorithme est trop exhaustif et donc pas suffisamment véloce pour répondre à la limite de temps. Je serais ravi d'apprendre de ce que vous avez fait.
Merci d'avance. :)
Je crains que donner ainsi les corrections des exercices ne soit pas dans l'optique de l'entraînement de Prologin ;
m'enfin bon, ce n'est pas moi qui vais t'empêcher de la recevoir !
Mais puisque tu sembles voir la faille de ton algorithme, corrige-la donc !
Si tu mets les bons mots sur le problème, tu verras en cherchant sur le net que c'est un problème célèbre.
L'exo est en effet classique (plus longue sous-suite croissante) qui s'implémente via un algo de programmation dynamique, cf. par exemple ce très bon site ICI (plus précisément le fichier dp_3.swf). L'algo est en n\^2 et les contraintes de Prologin étant rudes, je ne pense pas que cet algo passera.
Je suis tombé sur une solution en Python de David Eppstein qui résout le problème mais pas exactement comme on veut sur Prologin où on doit éliminer en priorité les notes les plus faibles (l'algo d'Eppstein au contraire renvoie avec les notes les plus faibles). En bricolant, tu peux adapter le code d'Eppstein et il passera alors 9 tests/10 (problème de dépassement de mémoire pour le dernier). La complexité serait de n*log(n). Probablement que l'équivalent en C/C++ passera tous les tests.
En fait l'algo d'Eppstein me semble être une adaptation du "Patience Sorting".
Prologin
2024