Les solutions proposées par les candidats pour le qcm 2011

Hello alls!

Alors voilà, ce n'est surement pas à moi de faire ça, mais je voulais créer ce sujet pour qu'on puisse comparer les solutions trouvées ( j'imagines que pour les premiers algos, les solutions seront plus ou moins les mêmes) , comme on avait pu le faire l'année derniere.

Je ne vais pas poster tout de suite mes codes, puisque je ne sais pas si c'est autorisé pour l'instant (même si normalement on ne peut plus soumettre), donc si un orga passe par là, pouvons nous donner nos solutions?

Ps: La solution de Pole pour la question 4 est ... "wah!"

On aura mieux dans pas longtemps. On aura un compte-rendu des différentes solutions proposées par l'ensemble des candidats avec la correction. :) Y'a parfois des perles dedans.

Sinon j'suis intéressé par l'algo de Pole... Et surtout par son raisonnement et son explication de l'algo, vu que l'algo tout seul je ne le comprendrais pas xD

Heuu… moi je veux bien donner la solution du 1er en C++. \o/
C'est quoi l'algo de pole ?
/me veux le voir.
/me veux le voir.
J'ai trouvé que la solution exponentielle au 4em, bon j'ai pas trop cherché non plus :\. On pouvait avoir du O(nm+m2\^m), qui a trouvé mieux ?
EDIT : grilled

Argg des matrices de partout avec des fft, c'est pas gentil de me montrer ça alors que j'ai les partiels qui ont commencés. J'ai même pas essayé de comprendre en quoi ton algo est valide, que là, j'ai pas de Doliprane à porté.
Moi j'ai quelque chose de beaucoup plus simple qui, tant qu'on laisse m à 15 reste sous le centième de seconde même avec n=1000000. Par contre des qu'on touche à m… c'est long. *_*
Sur du 15x100 c'est donc tout aussi rapide que l'algo (tordu) de pole, plus rapide si on augmente n, et beaucoup plus lent si on augmente m.
@pole : D'ailleurs, sur du 15x1M, ton algo renvoie un résultat faux, c'est normal ? je n'ai modifié que la variable MAXY, il y a peut être autre chose ?
Voici donc une solution un peu moins matheuse de complexité O(nm+m2\^m) :
http://codepad.org/vx992jYQ
Je suppose que c'est ce que la plus part des gens ont trouvé, le passage de O(n2\^m) à O(nm+m2\^m) pouvait être atteint en pré-calculant les applications sur la première ligne.

Pour les autres, l'idée :
1) On regarde ce que donne sur la dernière ligne les m 1-applications possibles sur la première ligne.
2) On regarde ce qu'il reste sur la dernière ligne après avoir dessiné les n-1 premières sans avoir appliqué le pinceau sur la première ligne.
3) Pour les 2\^m combinaisons d'applications possibles sur la première ligne, on xor les (au plus m, au min 0) dernières lignes calculés en 1) avec la dernière ligne calculé en 2). On regarde si obtient la dernière ligne souhaité.

Bah, dans ce cas-la, regarde quelle est la valeur la plus petite entre m et n et choisi ce sens la non?
Je posterais le mien plus tard :D

Bah, moi j'ai supposé m=largeur (donc m\<16), mais pole je suppose que c'est l'inverse, sinon en effet, il suffit d'inverser n et m sachant que m\<n (le cas où m>n étant simple puisque m\<16).

@Nimls_ : t'as un algo en quelle complexité ? Qu'on m'a dit qu'il y en avait un de polynomial.

pour le 4, je me suis amusé à le coder en modulo 3, rien que pour m'entrainer à gérer des tableaux avec des modulos, ca m'a bien fait réviser.

« Moi j'ai quelque chose de beaucoup plus simple qui, tant qu'on laisse m à 15 reste sous le centième de seconde même avec n=1000000. Par contre des qu'on touche à m… c'est long. *_* »
Oui, enfin, tout ceux qui ont passé le 4 l'ont aussi ;)
Il suffit de voir que résoudre la matrice transposée, c'est pareil.

« @pole : D'ailleurs, sur du 15x1M, ton algo renvoie un résultat faux, c'est normal ? je n'ai modifié que la variable MAXY, il y a peut être autre chose ? »
Étrange, mais pas tant que ça me connaissant :/
Je fais des tests et je ne vois pas d'erreur. Aurais-tu un fichier d'exemple ?

« Pour les autres, l'idée :
1) On regarde ce que donne sur la dernière ligne les m 1-applications possibles sur la première ligne.
2) On regarde ce qu'il reste sur la dernière ligne après avoir dessiné les n-1 premières sans avoir appliqué le pinceau sur la première ligne.
3) Pour les 2\^m combinaisons d'applications possibles sur la première ligne, on xor les (au plus m, au min 0) dernières lignes calculés en 1) avec la dernière ligne calculé en 2). On regarde si obtient la dernière ligne souhaité. »
Je reformule : on calcule chaque colonne de B en calculant A\^m*n vecteurs indépendants.
Ensuite, on résoud bourrinement le système d'équation en testant les 2\^n combinaisons linéaires (si on cherche bien, on peut en trouver un O(n2\^(n/2)) ).

Si je puis me permettre, c'est quoi "coder en modulo 3" jaloyan ?

Sinon epsilon, j'ai fait la même chose que toi (enfin, sans pré-calcul, parce que j'avais la flemme et que ça passait déjà les contraintes du site comme ça, et sans l'optimisation à base d'unsigned shorts).

Est-ce normal que je ne comprenne pas du tout ce que pole a fait ? Je pense que c'est une histoire de vocabulaire, par exemple, je ne sais pas mais alors pas du tout ce qu'est une matrice tridiagonale, ni même a quoi réfère certaines lettres( comme k et chi) ...

Spoiler: j'ai eu 18 ans la veille.

D'ailleurs Pole, j'aimerais bien savoir en quelle année de quoi tu es ?

epsilon : Ton lien marche pas.

Stop reformuler en matheux là. \^\^
En effet si on touche à la largeur c'est long, mais dans mon cas c'est exponentiel, dans le tiens ce serait polynomial d’après ce que j'ai compris.
Sinon oui, c'est résolut « bourrinement », c'est ça que j'aurais dû amélioré, mais je ne suis pas arrivé à trouver un lien entre les lignes générés en 1) et la dernière ligne…
Le fichier sur le quel nos algos trouvent un résultat différent est celui ci .

Les résultats :

[Epsilon012@nemesis /tmp]% time ./pole 1
./pole [Epsilon012@nemesis /tmp]% time ./alpha 0
./alpha [Epsilon012@nemesis /tmp]% time ./beta 0
./beta --------------------------------------------------------------------------------------
alpha étant mon algo en O(n2\^m) et beta mon algo en O(nm+m2\^m).

EDIT : @LPTheKiller : Non mais moi aussi, j'ai soumis celui sans le pré-calcul, même si j'avais déjà l'autre algo en tête, c'était le nouvel an, j'avais autre chose à faire. :p

EDIT² : Quelqu'un peut aussi faire le test sur ce fichier ? Histoire de savoir si j'ai soumis un algo valide ou pas. :p

oups, avec le http:// ça marche mieux. :\

Mon algo renvoie 0 également.

EDIT : Je crois que ça va pas le faire sur mon vieux netbook intel à 1.33Ghz \^\^

En 1ère année de terminale S (SVT spé maths si tu veux tout savoir).
Déjà tu aurais dû voir un petit problème parce que ton code mets 0.03 s pour lire 30 Mo.
Voilà la grille solution : http://dl.free.fr/p7EtD8Iv9
2 bugs que j'ai trouvé : pas de prise en compte de l'espace terminal (ou \n) présent dans ton fichier (tu dois faire un getchar), utilisation d'un short pour stocker des indices qui vont jusqu'à 1M.
Ton programme donne alors 1.
http://codepad.org/gxW7REKj
1000 grilles 15x1M (1 lecture) : 13 s pour moi, 56 s pour toi.

En effet, bien le merci \^\^.
C'est sur que si je m’arrête à 2\^16, c'est plus rapide.

@Pole : Heuu… quelle version de ton algo utilises-tu ?
Sur celle que tu as paste ci-dessus, j'ai toujours un facteur 13 (en faveur de l'algo basique) sur du 1Mx15. Qu'est ce que tu entend par 1 lecture ?
Que moi sur mon (très petit) PC, c'est 1s pour mon algo, 13s pour le tiens, alors 1000 grilles… heuu… non je préfère pas le lancer.

ne connaissant pas les matrices (terminale s) on pouvait s'y prendre comme ça (bien sûr cela doit être plus dégueulasse que certaines solutions mais ça marchait et assez vite):
l'idée est à partir de l'image envoyée au programme, parvenir à retrouver une image totalement blanche (le curseur étant reversible).

Pour ce faire, on applique le curseur (et plus particulièrement le côté gauche sur le bit) sur tous les bits 1 de la première colonne => la première colonne est blanche.
On passe à la deuxième colonne et ainsi de suite.
On s'arrête à l'avant dernière colonne (on ne peut pas appliquer le côté gauche du curseur sur la dernière colonne sinon le centre est hors image).
Si l'image ne contient que des 0, l'image est dessinable, sinon (c'est là que je me suis rendu compte que l'image pouvait quand même être dessinable dans certains cas)
On remet la dernière colonne dans la première colonne (l'algorithme étant symétrique c'est permis, c'est pour continuer à redécaler de gauche vers la droite) et on répète l'algorithme principal. A la fin, on note la dernière colonne quelque part, et on recommence, jusqu'à ce que:
- soit la dernière colonne contient que des 0 donc l'image entière contient que des 0 donc l'image est blanche donc l'image est dessinable
- soit la dernière colonne a déjà été rencontré et on tourne en rond :D => l'image n'est pas dessinable on arrivera jamais à une dernière colonne blanche.
Il faut noter que répéter l'algorithme principal n'est utile que pour une minorité très très bah minoritaire de cas. Si on ne faisait pas répéter on devait zappait 1% des cas (pas assez bon en maths pour faire le calcul).

Bien sûr il y a un ou deux cas particuliers (avec 2*n ou n*2 comme dimensions) auxquels cas j'ai utilisé le résultat du modulo 3 (je suis en spé math ça sert) enfin rien d'important c'est pas l'algorithme principal.

Shp