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

Thomas, t'as tout compris ... Faut dire que les explications de pole ... on comprend pas grand chose (à coté, mon arbre quaternaire et mon algo hybride est une solution parfaitement logique...).

@sam : J'avais pensé à faire comme ça et j’ai eu le même problème mais j'ai pas pensé à l'appliquer plusieurs fois >_Du coup, j'ai fait un truc pas terrible du tout...

Mon code : http://www.xavierm02.net/prologin/xavierm02/BWA/
Le BWA dans l'url, c'est parce que si vous allez sur http://www.xavierm02.net/prologin/xavierm02 , ça vous le demande et vous ne pouvez pas y accéder sans savoir que le mdp est BWA. J'ai donné l'url dans mes réponses pour qu'ils puissent tester directement.
Et le "click me", c'est parce que j'ai remplis le qcm à l'arrache au dernier moment (j'ai fini 5min avant la fin, avant de savoir qu'elle avait été rapportée) donc juste au cas où ils accepteraient que je modifie mes réponses :o

Il est cool ton script!
Par contre, informations rame, même pour les images assez petites.
L'exemple 2 par exemple semble petit, mais informations rame...

« @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. »
Tu lis la matrice 1 fois et tu la résous 1000 fois :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

int main(){
    scanf("%d%d",&Y,&X);
    for (int y=0;y Y;y++)
        for (int x=0;x X;x++){
            int val=0;
            scanf("%d",&val);
            image[y]|=val  x;
        }
    for (int i=0;i 999;i++)
        resoud();
    puts(resoud() ? "1" : "0");
    return 0;
}

(j'ai du enlever les Histoire que le temps mis par l'algo ne soit pas dominé par la lecture de l'entrée.

shp : tu peux nous donner un code ?

Bonjour,

Moi non plus je n'ai pas encore vu les matrices... (ni compris l'algo de Pole)
J'ai fait quelque-chose de plus simple :
L'idée de mon algorithme est de parcourir le tableau en diagonal, afin de les trouver une par une en tenant compte des précédentes. Je ne sais pas si je suis très clair...
Voila mon code en C : http://codepad.org/h9ZgN1n0
Pour la complexité je l'ai calculée mais je ne suis pas sûr. Je vais donc éviter de dire des bêtises...

@LPTheKiller : Pour tester si une ligne de départ donne la bonne ligne d'arrivée, jaloyan utilise une fonction récursive et au lieu de retenir un tableau, il retient 3 lignes en mémoire et utilise un modulo pour les gérer. D'où son expression.

@pole4:
http://blabddla.pastebin.com/g1vZJ9dc

@alex3er : C'est parce que "Information" calcule estSymetrique, estDessinable et estDessinable2. Et estDessinable2, c'est le 4ème exercice et mon algorithme est lent (complexité exponentielle je pense et niveau mémoire, ça doit pas être loin vu que j'a une fonction qui s'auto-appelle et que toutes les matrices possibles sont générées...).
En plus le JS, c'est un langage interprété...

Attends attends attends. Pole d'où tu sors pour inventer des trucs pareil en Term' S ? Même en me prenant la tête entre les mains je pige pas ce que t'as fait. Et j'suis en MP*, donc deuxième année de prépa maths, aspirant à l'ENS info l'année prochaine x)

Tu pourrais, heu, genre, expliquer qu'est-ce qui, dans ta solution, est représenté par des vecteurs, des matrices... ? Parce que quand j'ai vu que ça utilisait de l'algèbre linéaire, j'ai cru que c'était pareil que la solution d'un pote, mais en fait non. Lui il a trouvé quelque chose en O((NM)\^3), donc qui est pas super cool vu les exigences de l'énoncé mais qui passait quand même les tests, et qui a autrement plus la classe que la solution exponentielle... Mais au moins sa solution était compréhensible, c'était juste du pivot de Gauss sur une matrice dans Z/2Z, enfin j'arrivais à piger et je me disais même que j'aurais pu le trouver tout seul quoi x) Mais ta solution, là... Je comprends vraiment pas =/

shp :
Que penses-tu de cette grille ?
1 0 0
1 0 0
1 0 0
1 0 0
(Résultat de :
0 0 1
1 1 1
1 1 1
0 0 1
)
DeeTay : dis-moi à partir d'où tu ne comprends pas.
« D'où tu sors ? » : Pas de chez moi ;)
À part C, tout ce qui est en majuscule est une matrice carrée.

A partir du tout début... Que représentent A, u, v ? Sur quel corps est basé l'espace vectoriel dans lequel tu travailles ?

Pour n=7,
A=
1 1 0 0 0 0 0 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 1 0 0 0 0 0
0 1 1 1 0 0 0 0 0 1 0 0 0 0
0 0 1 1 1 0 0 0 0 0 1 0 0 0
0 0 0 1 1 1 0 0 0 0 0 1 0 0
0 0 0 0 1 1 1 0 0 0 0 0 1 0
0 0 0 0 0 1 1 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0

Tout est dans Z/2Z.
Si tu as trois lignes comme
0 1 0 1 1 1 1 (=u)
1 0 1 1 0 0 1 (=v)
0 0 0 0 0 0 0
Alors tu appuies sur la 2ème ligne en colonne 2, 4, 5, 6, 7 et ça donne :
0 0 0 0 0 0 0
0 1 1 1 1 1 1
0 1 0 1 1 1 1
Tu peux vérifier que A*(0 1 0 1 1 1 1 1 0 1 1 0 0 1)=(0 1 1 1 1 1 1 0 1 0 1 1 1 1)

En gros, tu applique un vecteur de tel sorte que ta première ligne soit remplie de zéros. Ensuite tu calcule les deux lignes suivantes et tu recommence. C'est cela ?

Salut Shp !
En deuxième année de prépa (intégrée…) j'ai eu une idée très similaire à la tienne : je faisais la même chose mais en ligne et pas en colonne : j'avais la flemme de tester si la matrice était plus large que haute et si oui l'inverser - de toute manière il y a 15 colonnes max contre 100 lignes max donc…
En revanche je ne me suis pas servi de la "réversibilité" de l'algorithme mais j'ai tenté d'obtenir un "critère" en ma basant sur la distribution des 1 et des 0 dans la dernière ligne… ce qui m'a fait violemment rencontrer le concept "d'explosion combinatoire" : aïe ;-)
Ce n'est qu'après avoir rendu ma soumission que je me suis dit que j'aurai dû profiter de la mémoire disponible et insérer une espèce de dictionnaire des cas possibles, mais trop tard, snif !

Sincères félicitations à Pole4 pour son brillant algorithme !!
Depuis combien de temps codes-tu en C ?
Les matrices sont-elles ta passion ;-) ?? pourquoi connais-tu déjà de si magnifiques théorèmes ?

Piratdu52 : Non. Je vais devoir ajouter un exemple.
Piotr : ça doit bien faire 5 ans.
J'aime bien l'algèbre et je prépare ma prépa ;)

La prépa c'est déjà censé préparer , alors si tu la prépares... xD

Moi aussi comme les deux autres je suis en deuxième année de prépa (intégrée, à l'INSA Lyon), et j'avoue que ton raisonnement écrit comme ça, là, il fait un peu peur (et j'ai autre chose à faire qu'essayer de m'y plonger).
En tout cas t'as dû passer un sacré temps dans les bibliothèques ou sur internet pour apprendre tout ça, bravo.

Si ça peut vous rassurer, je suis à l'ENS en info et j'ai rien compris au raisonnement de Pole4 :D (j'ai pas dis que j'avais beaucoup cherché non plus \^\^).

Comme quoi on peut avoir de bonne idée sans arriver à les expliquer clairement =) (et c'est souvent le cas quand on explique des choses utilisant des notions qu'on n'a pas encore vu en cours).

Avec l'exemple, ça devrait être plus facile à comprendre.

Euh... j'ai un doute sur Pole4 :S

Soit nous avons vraiment affaire à un passionné de Mathématiques et d'Algorithmique : on peut lui souhaiter bonne chance pour les Olympiades Internationales de Maths car il finirait sans doute parmi les 15 premiers !

Soit c'est une personne qui a dépassé la limite d'âge et qui s'amuse à faire peur à des MP* et des gens à Ulm Info. On peut toujours le féliciter : il a atteint un bon niveau !

Qu'en penser ?

Ah non mais moi chui à Lyon, pas à Ulm (j'ai pas précisé xD).
Enfin là en ce moment chui aussi à Montréal, mais ça n'a pas vraiment de rapport.