DF 2011 - Carré & Vista

Bonjour à tous,

J'aimerais vérifier quelque chose pour l'algorithme de Carré. Je voudrais juste vérifier que l'algorithme naïf est bien celui que je pense. Parce que mon algorithme qui passe les limites de temps donne le même résultat que le naïf, et qu'il ne passe pas le test 5.

L'algorithme naïf est-il bien le suivant ?
On pose Ways(X, Y) le nombre de chemins possibles vers l'arrivée à partie de la case (X, Y)
Ways(X, Y) = Ways(X + 1, Y) + Ways(X, Y + 1)
Ways(N - 1, N - 1) = 1
Ways(X >= N, Y) = 0
Ways(X, Y >= N) = 0
Ways(X, Y) si (X, Y) est un mur = 0

Le plus étonnant est que le test 5 est donne officiellement presque le même résultat que le mien, à trois chiffres près (j'ai "908" préfixé à la valeur "officielle").

J'ai affiché l'entrée sur stderr, et j'ai testé l'entrée avec l'algorithme naïf. Après un peu de moulinage, il donne le même résultat que mon algorithme évolué.

Donc où est-ce que je me trompe ?

Merci d'avance,

Ekleog (le hérisson écrasé)

[Edit : Même souci avec Vista. L'algorithme naïf que je vois est quasiment le même, avec N+1 et M+1 à la place de N et M.]
[Edit bis : Ah, non, le problème n'est pas là pour Vista. Le problème vient de unsigned long long qui n'est tout de même pas assez grand pour contenir la valeur pour (19, 20). Au passage, la réponse proposée n'est pas valide non plus, vu que (pour mon programme, du moins), (18, 20) vaut 18446744072927813858 - et que je suppose que (19, 20) vaut plus]

est donne-> donne

Je vois mal le problème dans ton naif... Tu peux passer le code sur pastebin/ideone (au cas où si je peux t'aider, même s'il y a peu de chance...) ?

(Oups, j'ai oublié de montrer le cas des murs. C'est ajouté.)

Sinon, http://pastebin.com/CKuG52Ph
J'ai mis le code final, et ai limité le paste à 1 jour, parce que ce n'est pas un problème encore ouvert mais qu'il ne faut pas gâcher le plaisir des autres pour autant !

Tu as vu que dans Carré tu ne dois retourner que les 6 derniers digits ?

Et faut pas oublier le fameux test vicieux avec la case de fin inaccessible...

@ @uguste: sur ce point, le code d'Ekleog n'a pas de problème

Pareil que Serialk. Donc si tu te contentes de rajouter un petit %10\^6 dans ta fonction ways, va aussi falloir changer ton vector\< vector\< int > > NbW pour un vector\< vector \< long long int > > . (Oui je sais : "Bouh le namespace std;!")

"Oh, c'est vicieux ça, avec la phrase qui tient sur une demi ligne ... Il ne faut pas survoler le sujet ! "

Combien de fois me suis-je dit la même chose pour topcoder/codeforces.... Faudrait vraiment mettre en gras ce genre de précisions.

" Euh ... J'admets avoir du mal à lire ce que tu as mis entre les crochets du vector ... !"
édité :) , mais je sais pas si ça passe en mémoire... Mieux vaut mettre des % un peu partout dans le code ;)

En fait, j'ai déplacé le modulo, ça permet de prendre moins de mémoire - la mémoire étant le point limitant avec mon approche. Oui, j'avais la flemme de faire de la vraie programmation dynamique. Mais faire les diagonales dans le bon ordre, c'était ... Comment dire ... Trop de réflexion ? (Et dire que je vais à la demi-finale demain !)

EDIT : Et voilà, le temps que je poste mon message t'as édité !

serialk> Oh, c'est vicieux ça, avec la phrase qui tient sur une demi ligne ... Il ne faut pas survoler le sujet ! Bref, je ne suis pas très doué. =°

alex3er> Euh ... J'admets avoir du mal à lire ce que tu as mis entre les crochets du vector ... !

@uguste> Le memoize permet d'éviter de se tordre le cerveau sur ce point, c'est l'algorithme basique avec un cache - merci les limites mémoire !

EDIT : Ah, bah non, les limites mémoire sont pas aussi lâches que ce que je pensais ! 'va falloir optimiser un peu =°

EDIT 2 : Et vouala, merci la spécialisation de vector\<bool> !

C'est dommage que l'on n'ait pas la dernière soumission réussie... Je ne me rappelle plus de ce que j'avais fait, et comme je testais ton code, je me retrouve avec une soumission fausse \^\^.

Parce que même en modifiant pour un vector de vector rempli de int, je dépasse en mémoire pour le dernier test.
Bon, je vais plutôt tenter de faire en "diagonale"

Passes simplement le Sqr en vector de vector de bool et ça repassera. ;)

Je ne sais pas si tu comptais que je le voie, mais, ayant été à la demi-finale d'hier, je n'ai pas eu le temps de regarder.
Si tu pouvais renvoyer un autre lien d'un jour ... =)

C'est bon : http://pastebin.com/pu1AG7rh (expiré)

(Après avoir fait de nombreuses bêtises...)

Il expire aussi dans un jour, je pense que c'est raisonnable, non?

"Je ne sais pas si tu comptais que je le voie":
Ouaip, pour te montrer que ça n’entraînait pas trop de complications ;)

Donc: http://pastebin.com/S3tVKK9d

Sinon, bien passé? Le sujet écrit était cool?

Oui, ça allait ... Au passage, les orgas prologin sont des esprits de la mort (shinigami), c'est toujours bon à savoir. ;)

Au passage ... On peut quand même avouer que mon code est plus lisible que le tien. =p
D'ailleurs, en général on utilise r et c, pas c et c2. x)
Et quand on ne parle pas de (row, col), on utilise i et j, pour désembrouiller un peu l'esprit du lecteur inattentif. \^\^

Un dernier truc : Plutôt que la boucle de resize au début, ça marche très bien comme ça : ;)
vector\<vector\<int> > v(N, vector\<int>(N));

D'accord, merci :)

Pour le c et c2, c'est une mauvaise habitude que j'ai pris de nommer quasiment toutes mes variables de boucles cn pour aller rapidement dans l'écriture de code...

Pourtant, entre 1 caractère (j) et 2 caractères (c2), je ne vois pas de gain de vitesse ! =p

C'est surtout un gain de temps lié à la réflexion. Parce que ok, dans ce cas, ça va. Mais si y'a tout un tas de variables déjà définies dans le reste du code, ou par exemple, sur topcoder on a en paramètre des variables comme "k", "n", "r" etc... Pas besoin de se creuser la tête. Rares seront les cas où on aura du c1/c2/c3... en paramètres.
Mais c'est sûr que ça ne m’entraîne pas à faire du code clair ;)

Moi je les nomme indexincrementaldebouclefor1, indexincrementaldebouclefor2, etc. !
Et tous mes noms de variables commencent par variable puis le type : variableentiere1, variablecaractere4... :D