Bonjour,
Juste un petit message pour signaler que les tests sur le dernier exercice ne sont pas suffisamment large. En effet mon algorithme a passé tous les tests sans exception alors qu'il n'aurait pas du !
Je vous propose d'ajouter ce test supplémentaire :
19 11 10 3 1
Sachant qu'on peut battre le système avec le volume "21 L"
A mon avis, ce sont surtout les limites de temps qui sont trop larges : avec un test généré par un script maison de 5000
bidons (soit 10 fois plus que le maximum de prologin) de 1 à 1 milliard (soit comme prologin), mon algorithme ne met
avec -O2 et sur mon ordinateur pas si puissant que ça que 0.007s :
real 0m0.007s
user 0m0.000s
sys 0m0.003s
Alors que l'exercice autorise jusqu'à 200 fois plus !
Est-ce qu'il n'y aurait pas un petit problème sur les limites de temps, du coup ?
Je pense qu'il parlait plutôt des tests qui vérifient la validité de l'algo, comme quoi il a soumis un algo qui renvoie un faux résultat pour un cas alors qu'il passe tous les tests sur le serveur.
Pour les limites de temps, tu as essayé de voir ce que ça donnait avec un algo sous-optimal ? Si ça se trouve les différences sont vraiment grandes entre la meilleure solution et une juste un peu plus naïve. Les limites doivent simplement cerner si ton algo est optimal ou non. Si elles sont trop sévères elles risquent de ne pas valider pour un langage plus lent malgré les coefficients multiplicateurs.
Je crois que c'est surtout du au fait que tu aies fait un algo en O(N²) optimal et donc moins bourrin qu'un algo en
genre O(NM) avec M la somme des tailles ou O(N!) :D
Dans ces cas, ça devrait quand même passer les test de verifications mais pas ceux de performance... Enfin, de ce que
j'ai compris.
Sauf que les tests de performances sont eux-mêmes limités par les mêmes contraintes, si j'ai bien compris.
Et un algorithme sous-optimal en O(N\^3) - que je n'ai pas essayé d'implémenter mais qui existe - passerait, si je ne me trompe pas, facilement les tests : 500\^3 \~= 125M alors que 5000\^2 \~= 25M (que je fais en 7ms). Du coup, en considérant que les intérieurs de boucles sont de mêmes tailles (et en considérant que le coût de startup de mon algorithme est de 0ms, ce qui n'est pas le cas, puisqu'en re-testant avec seulement 500 boites ça me fait entre 4 et 20ms ; autrement dit le coût de chargement des inputs est prédominant), on peut dire que l'algorithme en O(N\^3) mettra environ 5*7ms = 35ms pour l'input de taille maximale.
Donc les limites de temps me semblent encore beaucoup trop larges.
Edit : Et pour les coefficients multiplicateurs, de mémoire il a été dit qu'ils étaient toujours trop larges, pas trop serrés : un langage à coefficient multiplicateur peut donc plus facilement rentrer dans les limites de temps.
@Tiller: Moi aussi, j'avais d'abord fait un algo qui passait tous les tests du serveur, mais pas 19 11 10 3 1. D'ailleurs, il suffit de demander un volume de 13 pour faire mieux que l'algo glouton.
Edit (par Jill-Jênn). Spoiler.
C'est marrant, ce que tu dis, Tiller, parce que ce test fait précisément partie des tests, et ce depuis le début de la semaine.
Oui je parlais bien des tests qui vérifiaient le fonctionnement de l'algorithme.
@le_sphinx, Ah, tant mieux alors :] Je n'avais pas retesté depuis ma soumission
Prologin
2024