Corrigés

Oui il manquait un petit truc : je parlais de l'exo 4.
Dans le très naïf : r e s = min ( t r e s n a i f ( i +1, Pgauche + p o i d s [ i ] , Cgauche +1) ,
// on l e met a gauche
t r e s n a i f ( i +1, Pgauche , Cgauche ) ) ;
// on l e met a droite
Dans les 2 cas, on appelle avec i+1, donc on peut ne garder qu'une seule ligne (même astuce que pour les autres solutions).
Et pour le naïf : "En effet, ces poids sont ceux atteignables avec k − 1 conteneurs pris parmi les l − 1 premiers, augmentés du poids du lme , d’une part, et ceux atteignables avec k conteneurs pris parmi les l − 1 premiers, d’autre part. Les conditions aux limites s’écrivent elles aussi facilement."
Poids possibles=bit à 1 ou 0
Et il suffit de faire un | sur 2 trucs, dont l'un est décalé, soit la même chose que la solution subtile : même complexité, même petite constante (/64), même consommation de mémoire.

Moi j'ai bien aimé les dolipranes \^\^

Bah, oui, mais avec l'état du très naïf tu n'iras pas beaucoup plus loin même en optimisant la mémoire en ne gardant qu'une ligne, alors que l'état du 2e est déjà plus petit...

Pour passer du naïf au subtil, la moitié de l'idée est de mettre les poids dans un bitset. Après effectivement tu peux direct appliquer cette technique au naïf, ça fait juste des bitsets de longueur Nw (avec w fois moins d'opérations effectuées dessus) et pas N... Bref, il y a plein de solutions (bien que très peu de candidats en aient trouvé une valable), nous donnons juste un schéma de raisonnement qui permet d'aboutir à une solution correcte.

Cela permet également de tourner l'état de différentes manières pour voir différents angles d'approche du problème...

Euh... Peu importe la taille du bitset, non ?

Bah en gros tu as le choix entre faire w opérations sur des bitsets de taille N ou 1 opération sur un bitset de taille nw, selon que tu stockes des index de conteneurs ou des poids dedans. Oui, peu importe. Comme je le disais ça permet de montrer les différents angles d'attaque...

Prologin n'a jamais communiqué là-dessus. C'est-à-dire que les sélections au niveau de la qualification se résument à :
- vous êtes qualifiés
- vous ne l'êtes pas
C'est comme ça..
Les seules 'notes' chiffrées sont les points en épreuve machine de demi-finale et les scores en finale.

Non, il n'y a pas de notes, et encore moins de classement. Pour chaque questionnaire, on a essayé d'évaluer le niveau du candidat. Certains ont été acceptés de suite ; d'autre refusés ; d'autres encore ont été mis de côté. Pour ces derniers, le questionnaire a été évalué par plusieurs correcteurs, avant d'être classé.

Il n'y a donc pas de notion de classement, il n'y a ni premier, ni dernier. Mais vous devez avoir une idée de ce que vous avez fait. Comparez avec la correction. Votre code était-il concis, clair et efficace ?

Cela prendrait du temps de faire des retours individuels sur vos travaux. Et puis, il y a aurait inévitablement des contestations, des critiques, etc. (la différence entre le "dernier" accepté et le "premier" refusé n'est pas très élevé au fond, il y a forcément une part, même minime, de subjectivité).

(cela permettrait à moult d'entre nous de s'améliorer.

Nous avons fait une correction commentée. Vous pouvez aussi vous entrainer avec les sujets des années passées. Si cela ne suffit pas, il est toujours possible de poser des questions sur le forum (ou sur IRC). Il est difficile de faire plus pour vous (l'organisation du concours nous prend déjà énormément de temps).

Il serait possible de remettre la correction en ligne ?
J'ai bien envie de relire l'explication de l'algo optimal pour Cargo... Histoire de peut-être enfin la comprendre. :D

Je serais également intéressé. Je n'avais même pas remarqué qu'une correction existait...

La correction est disponible ICI en attendant que je mette ca dans la partie archives ;)

Merci beaucoup !