Le Python utiliserait 8 octets par booléen.
Et entre 40 octets par entier (sur mon ordi) et 73 octets par entier (sur le serveur PROLOGIN).
C'est énorme, tu peux nous donner le lien où est indiqué l'unité de la fonction resource.getrusage(resource.RUSAGE_SELF).ru_maxrss ?
OK merci, une doc Debian, alors que je cherchais dans la doc Python.
Finalement le problème 5 est solvable en Python :
en maxi 11 à 15 Mo sur les tests n°10,11,13,14,15,26, ça correspond à environ 100 000 entiers.
et maxi 0.9 à 1.1 seconde sur les tests n°12,15,18,26.
J'aimerais bien qu'un administrateur intervienne sur le forum pour dire quelle limite de mémoire ils ont mis pour les tests n°10, 16 et 18 avec Python ?
Salut,
Pour commencer, désolé de la réponse lente.
Pour répondre à vos interrogations, les contraintes mémoires affichées dans l'énoncé d'un exercice s'appliquent aux langages les plus bas niveau (C, Rust, ...) qui peuvent se permettre d'utiliser des représentations en mémoire très simples comme celles que vous décriviez. Lorsque vous soumettez un programme dans une autre langage plus lourd (Python, Java, ...) les contraintes sont automatiquement relaxées pour que le problème soit résolvable avec un programme similaire dans tous les langages.
Tous les tests sont soumis à la même contrainte de mémoire et temps, qui est celle affichée dans l'énoncée, et réadaptée dans votre langage.
Enfin, soyez prudent en interprétant la consommation mémoire affichée sur le site quand la limite de mémoire est atteinte, elle peut être trompeuse. Par exemple si la première chose que votre programme essaye de faire est de créer un gros tableau de 1Go, il sera interrompu avant que cette instruction s'applique, et la consommation mémoire affichée sera donc très faible.
Du coup pour conclure, l'exercice et la gestion des contrainte est formatée pour que les candidats puissent résoudre le problème sans avoir à se préoccuper de l'overhead introduit par leur langage.
J'espère que ça vous aura éclairé, en règle générale on préférerai éviter de donner les valeurs précises de limite mémoire par langages pour justement éviter que des candidats en profitent pour chercher une faille et écrire un programme hyperoptimisé dans un langage normalement coûteux.
Bon week'end !
Donc... ceux qui écrivent en C ont les moyens de tester leur solution avant de la soumettre, mais pas les autres qui ne connaissent pas la limite mémoire autorisée.
Je ne comprend pas bien pourquoi " éviter que des candidats en profitent pour chercher une faille et écrire un programme hyper optimisé dans un langage normalement coûteux ".
Ecrire des programmes optimisés est le but du jeu non ?
Bon, peu importe j''ai finalement trouvé la raison du problème de mémoire en python : un tableau de tableaux vides [ [ ] for i in range(1000000) ] prends déjà 80 octets par tableau vide [ ], soit 80 Mo, avant même d'avoir entré un seul chiffre c'est déjà plus que la limite de 73 Mo. Dans mon cas il faut commencer par réduire la zone aux extrémités > xmin, > ymin, < xmax, < ymax, avant de réduire l'espace non utilisé au centre.
Seulement après on peut entrer dans le coeur de l'algorithme.
Info amusante : quelqu'un de ma famille qui a utilisé un algorithme assez proche et qui a optimisé la programmation, a réussi a descendre a toujours moins de 0.77 seconde en python, mais a découvert que c'est un algo probabiliste qui trouve souvent la bonne solution (il passe les 26 tests) mais par toujours (il existe des contre-exemples) !
Prologin
2024