QCM 2011 Sujet 4

Tu as dit plus haut que tu avais trouvé le jeu original, continue d'y jouer, essaie d'autres tailles de grille, en particulier les tailles où tu peux faire du cas par cas facilement (2x2 voire 3x3) et essaie d'en déduire certaines propriétés exploitables pour un algo ;)

Parcequ'il y a d'autre propriété que l'ordre (qui n'as aucune importance) et que le fait d'appuyé 2 fois sur une même touche ne sert a rien? Y'as aussi la symetrie, mais au final je trouve pas de solution qui marche a chaque fois :/

M=10, l'ordre n'a pas d'importance (donc tu peux peut-être en imposer un ?), appuyer 2 fois revient à appuyer 0 fois.
De ces propriétés, d'une petite astuce, et de l'algo bourrin (en O(2\^(NM)*NM)), tu en déduis un algo simple qui passe les contraintes.

Essaye de réduire les possibilités à tester.
Pour cela, il faut trouver une propriété et le meilleur moyen pour la trouver est de résoudre à la main des petits exemples (5x5, peut-être plus gros).

Est-ce qu'il y a une solution simple qui résout le problème avec les contraintes du sujet initial (1000x1000) ?

Pour réduire les possibilité a testé, y'as les symétries, mais après je vois pas trop, j'ai regardé tout les cas en 2*2 y'en a déjà beaucoup, j'ai commencé les cas 3*3, et pour l'instant, mise a part cette histoire de symétrie ou encore les chemins que je prend qui mène au même résultat sinon, je vois pas encore trop de chose exploitable... Et dire que depuis le début du concours je suis dessus, sans trop avancé... C'est énervant...

Pas besoin de gérer les cas symétriques !
Imagine que tu as lancé ton algo bourrin dans l'ordre ligne par ligne, de gauche à droite. Il explore une possibilité, et il est amené à faire un choix pour la 1ère colonne de la 2nde ligne. Est-ce qu'il a vraiment le choix ?
C'est un gros indice.

J'ai beau chercher le fait si j'ai le choix ou non, je vois pas, par exemple j'ai :

011 .XX
001 -> XXX
111 . . .

Bah ce résultat, j'arrive a le trouver à la main, mais au hasard, donc je vois pas comment coder un algo pour arriver a une méthode qui arrive là, ensuite je peux tester le différente possibilité, mais ça prendrais trop de temps par un algo bourrin qui teste toute les combinaisons, donc il doit bien y avais une méthode pour que l'algo fasse des choix, le problème c'est que malgré vos indice je vois pas...

Je crois que je vais abandonné cette exercice et envoyé mon QCM et les 3 exos, en espérant que ce soit suffisant pour les demis car là vous avez beau essayer de m'aider, et je vous en remercie, mais là y'as vraiment rien qui me viens \^\^" et pourtant je peux vous assuré que je fait pas preuve de mauvaise volonté, j'ai tout un tas de brouillions pour cette exercice que j'accumule tout les soirs quasiment sur mon bureau...

Au pire, tu peux coder ton algo bourrin et l'envoyer, c'est mieux que rien. Les contraintes dans la partie QCM sont un objectif à atteindre, mais c'est pas parce que ton algo ne les remplit pas qu'il faut le jeter à la poubelle.

1010
x
->Ai-je le choix pour x ?

Oui, si jamais ton algo passe pas dans les temps, il faut quand même le mettre dans le QCM. Comme c'est corrigé par les orgas, c'est quand même un plus ;)
Et à mon avis ça suffira pour la demi-finale (du moins si t'as bien réussi le reste).
Surtout, n'envoie pas ton QCM maintenant, t'as encore beaaaucoup de temps pour y réfléchir, tu peux toujours avoir une illumination pour l'exo 4 :)

A rocket, je vois ce que tu essayes de me dire, ça j'avais remarqué ensuite, c'été d'ailleurs ceux sur quoi j'été parti à la base, de descendre tout les 1 en bas, mais le problème c'est qu'une fois tous à la dernière ligne, je me retrouve bloqué, je m'explique je reprend l'exemple tout de tout à l'heure :

011
001
111

Si je fait mon étape qui vise a appliqué en dessous des 1 au final j'ai

000
000
001

Dans ce cas là je peux enclenché la position (0,1) et (0,2) et je recommence une "descente" et hop problème résolu, sauf que pour trouvé la bonne combinaison de la ligne du haut pour la seconde descente, sauf que en taille 3 ça va vite de tout testé, mais en taille 15 ça fait énormément de combinaison et prend énormément de temps, de plus je respecte pas la propriété de n'appuyer qu'une fois, par moment j'applique 2 fois...

Je pense pas que tu auras d'autres indices ici, Artix et roket ont déjà énormément aidé (un peu trop même je trouve, 'fin bon ...).
Continue de chercher sur ces pistes (et des pistes, il en reste un bon nombre :) ), tu devrais pouvoir trouver ;)

Bon en faite j'ai décidé de testé ce a quoi je pensais depuis le début, je n'ai jamais testé car je pensé que c'été trop brutal, que j'essayai trop de combinaison, et que j'allais dépassé la limite de temps, alors je me suis dit cherchons autre chose... Et puis au final j'ai tenté de passé les test avec cette méthode brutal, et j'ai eu la chance d'avoir réussi les 23 tests du premier coup sans dépassé la limite de temps, me voilà rassuré, quel beau cadeau de noël x) une place pour la demi final :P

Moral de cette histoire -> Toujours écouté ses intuitions première xD

:) tu vois tu l'as ton algo

Merci last_dreamer, j'avais trouvé un algo qui marchait bien (sauf mon implé buggué), et fallait que tu le donnes... comment les orgas prologin vont savoir si j'ai triché ou pas ?

Joyeux Noël à tous sinon

Tu vas devoir joindre à ton QCM une déclaration signée, visée par 3 notaires, étudiée par 2 juges d'instructions (oublie pas de laisser un cheveux, pour qu'ils puissent comparer l'ADN).

« (oublie pas de laisser un cheveux, pour qu'ils puissent comparer l'ADN) »

Pour tester la prise de drogues aussi

Pikrass : Je sais pas si j'interprète bien ton message mais ça m'a fait bien rire =D

Ça serait pas possible d'avoir le O optimal ? :-°

Celui de Pole si tu veux, mais tu risques de te demander pendant longtemps comment on peut obtenir un truc comme ça (y'a un peu des logs dans tous les sens je crois), pas celui qui passe juste les contraintes, sinon c'est trop facile \^\^