Demi-finale 2014, épreuve machine - Correction de copies, pb test 9

Hey,
J'ai un petit pb avec cet exo :
J'ai simplement (et peut-être bêtement) appliqué l'algo de wikipedia (dont la validité est démontrable) et mon code passe tous les tests sauf le 9.
Sauf que celui-ci peut vite devenir très gourmand en mémoire : prog dynamique utilisant une classe héritant de dict construisant la table des solutions dans __missing__, indexé par couple, ce qui n'est pas forcément très optimisé en temps, mais sensé éviter de systématiquement avoir 20M éléments avec les entrées de taille maximum...

Du coup, vu que je serait particulièrement étonné que le programme renvoie un mauvais résultat (j'ai relu et vérifié la correspondance avec l'algo plusieurs fois), je me demandais si une exception levée par python ne pourrait pas elle aussi provoquer le message "Votre programme n'a pas renvoyé le bon résultat. (détails cachés pour ce test)" ?

Ah le python...
Sinon, par curiosite, je suis pas contre le lien Wikipedia.
Mon algo n'etait pas specialement gourmant en memoire alors peut etre n'est ce pas le meme ...

dépêche toi avant que les admins me censurent :P
edit (serialk) : tu te fiches de moi ?

...Sinon, pour une demi-finale, je fais généralement en C(++), mais vu qu'en python je code plus rapidement, je compte faire la finale en python, donc je m'entraîne sur les sujets de demis :P

En fait, j'utilise un algo qui est polynomiale (car l'entrée est majorée). ...Mais d'un autre côté, la mémoire a la même complexité que le temps qui est du O(m*n) où m est la somme de toute l'entrée.

Or, dans le cas de l'entrée la plus grosse, on a un tableau n*m avec n=1000 et m = 20 000 (vu qu'on prend la moitié de la somme) on obtient donc un truc proportionnel à 20 000 000, or un booléen, en C/C++, c'est 1o... on est donc déjà à 20 Mo alors qu'on n'a que 10 Mo...

En cpp, j'aurais optimisé en codant mes bools par sur les bits (et pas de blagues en dessous de la ceinture svp :P ), ce qui aurait ramené à 2.5 Mo, ce qui est bien en dessous de la limite.

Mais en Python, je pense pas trop que ce soit possible... Puis j'ai aussi utilisé un dict ( = table de hashage) sur une seule clef, histoire que ça grandisse au besoin, mais je ne sais pas trop comment ça se comporte sur de grande entrées. Je serais curieux de connaître aussi justement l'entrée du 9 pour mieux comprendre

Tu peux le faire avec 20 ko de mémoire, voire 2.5 ko en optimisant de manière dégueulasse comme tu le proposes.
La complexité en temps est bonne, les contraintes formulées par l'énoncé sont d'ailleurs très critiquables.

+1

Rah, un orga a édité mon message. Mon code était beau pourtant.
Edit : Mais le code de cheikdav dépasse les sommets de l'élégance.

@serialk : qui serais-je pour me ficher des admin voyons... () :-)
(je comptais laisser le lien juste deux jours le temps que cheikdav l'ai puis j'aurais enlevé)

Mais même si j'ai pas eu le temps de voir vos code effectivement, maintenant que tu le dis, je vois où est mon problème niveau mémoire... En fait, je peux me contenter d'une seule colonne, ce qui divise par 1000 ma complexité mémoire, et on tombe à O(Σ Xn)

That's it. 9/9 ?

yep, en python (miracle ?), et 42 lignes seulement :P
(avec des lignes blanches, sinon, on est à 30 lignes)

1) ça simplifie le code
2) c'est carrément plus rapide et moins gourmand...
3) j'ai appliqué le même principe sur deadline avec succès

...1000 fois moins de mémoire et beaucoup moin de temps...

...Ça doit être pour ça que ce problème est le plus simple des problèmes difficiles

cheikdav a besoin de moins de 20 lignes (en C++), mais il est fort.

Joli problème, merci Prologin ! il y a une variante plus compliquée dans le qcm 2009, exo Cargo. Voir aussi une généralisation http://acm.timus.ru/problem.aspx?space=1&num=1005

Sinon, ça passe sans souci (raisonnement + mémoire + temps) en Python comme en C++ avec un set (structure de données ensemble), pas la peine de faire d'énormes tableaux de booléens.

@hl037
"une classe héritant de dict construisant la table des solutions dans __missing__, indexé par couple, "

C'est super rare que t'aies besoin d'utiliser des classes dans des exos de ce genre (pour la finale, j'en sais rien, c'est vrai qu'il y a le temps d'en écrire!). Occasionelement on utilise des structures (C/C++) . Même pour des t ypes de données plus élaborés (graphes) par exemples où la POO est usuelle, on s'en dispense.

@Thomas
C'est quoi le problème avec les tests de cet exo ?

Il n'y a pas de problème de tests, mais un problème de contraintes (qui ne correspondent pas aux tests) a priori.
Je ne pense pas qu'il y ait un test avec n \~= 1000 et Σ l_i \~= 40 000.

Ah ? c'est ce que tu voulais dire par "les contraintes formulées par l'énoncé sont d'ailleurs très critiquables" ?

@candide :
yep, ça passe tranquille, c'est juste que je stocké toutes les solutions, alors qu'on n'a besoin que d'un sous-ensemble d'entre-elles à chaque étapes (et ça me divise par N la mémoire utilisée).

Pour les classes, c'est parfois plus pratique d'avoir une classe pour stocker des graphes par exemple... Mais bon, c'est vrai qu'on peut tout faire avec des tableau (pardon, liste en python :P), c'est juste une question de gout après...

De toute façon, même avec des classes, tous mes code tiennent en moins de 35 lignes pour l'instant.

Pour la finale, on est obligé de faire de la POO puisque l'API est orienté objet :P (enfin... à moins d'un cygne noir)

"c'est vrai qu'on peut tout faire avec des tableau (pardon, liste en python :P)"

En Cpython, les listes sont des tableaux dynamiques (équivalent de vector du C++) en fait, pas des _listes_ chaînées. Et puis plus utiles que les banals tableaux, il y a les map et les ensembles (voire des deques) complètement indispensables (gros défaut du C qui n'en propose pas).

"Pour la finale, on est obligé de faire de la POO puisque l'API est orienté objet"

Ah décidément, la finale de Prologin n'est pas une épreuve comme les autres. POO => codeurs C s'abstenir

Sur ce bon courage pour la finale !

"Pour la finale, on est obligé de faire de la POO puisque l'API est orienté objet"

Non, c'est faux.

Ah tiens, d'après le générateur de stechec, il va y avoir une API C++ ? C'est une première, non ? On n'avait que celle du C avant il me semble ?

>> or un booléen, en C/C++, c'est 1o...

Il me semble très fortement que std::vector<bool> est spécifiquement définie pour faire en sorte de n'utiliser qu'un octet pour huit valeurs.

Ah oui en effet.

"For a class that also optimizes for space allocation and allows for dynamic resizing, see the bool specialization of vector (vector )."
http://www.cplusplus.com/reference/bitset/bitset/

Certes, ce n'est pas de "l'orienté objet" comme on l'entend en C++, mais au final, on reste sur un paradigme de structures, ayant des états internes soit accessibles, soit cachés par un handle (ou id), et des fonctions pour interagir avec... J'appelle ça de l'objet perso...

Maintenant, je dois reconnaître le chouilla de troll quand je poste des affirmations comme celle de mon précédent poste, qui n'était là que pour placer le cygne noir :D

...Et j'aurais appris que l'optimisation des bools était standard en C++ :O
bon à savoir :D

Ça se lit dans les bouquins.

Ouais, y a pas eu d'orienté objet ; l'API C++ était la même qu'en C sauf qu'elle utilisait des vector au lieu des tableaux.
J'ai plutôt tendance à appeler cela de la programmation structurée et procédurale : les structures et les fonctions sont le cœur du programme.

Mais ça signifie quoi, cette histoire de cygne noir ?