Prologin 2003 - Page 2

nitro a écrit :
Moi je te vois souvent, c'est toi qui me voit pas

arfff, bah forcement je sais pas a quoi tu ressemble lol
et vous avez pas de trombi a epita, ou du moins si vous en avez un, on n'y a pas acces...

On a passé nos soutenances avant noel... on attend les résultats

ok
nous c a rendre pour ce soir (dimanche soir), et soutenances lundi surement...

quoi ! ils demandent du travail pour le dimanche ??!

mdr

Au fait, vous avez fait comment, vous, pour la dernière question des sélections ?

Moi j'ai déjà dit que je ne l'avais pas faite, mais je l'ai vue récemment dans un bouquin d'algo, elle est classées dans les pb très difficilesà résoudre (appelés NP-Complets, mais je ne sais pas du tout ce que ça veut dire).
Je suis très curieux de savoir comment tu l'as résolue.

jackiechan
a écrit : appelés NP-Complets, mais je ne sais pas du tout ce que ça veut dire

Ça veut dire qu'il appartient à une classe de problèmes équivalents pour lesquels on ne connaît aucun algorithme en temps polynomial pour les résoudre avec un ordinateur électronique. (Il faut probablement un ordinateur quantique pour les résoudre en temps polynomial.) Donc l'algorithme de Thibaut, qui est apparemment en O(2ⁿ), est bon.

J'ai fait un algo en O(2ⁿ) mais le server me le refuse. Même qd je le lance sur mon pc en fait, il met du temps et je sais même pas s'il arrive à résoudre (en théorie oui).
Qd à la complexité, il faut tout tester: avec ou sans le nombre. Or il y a n nombre donc c(n)=2^n-1.
J'espère que c une erreur dans mon programme, et que la faute ne vient pas d'eux!

Je n'ai pas vu le sujet mais ça doit etre un exemple typique de programmation dynamique (à Epita on a ce genre de problemes en exam, je comprends mieux pourquoi on ne peut pas faire prologin). PaXaL ton algo récursif est surement correct, mais il est trop couteux, donc le server le refuse... Il faut que tu le transforme en algo dynamique, généralement c'est juste quelques lignes à rajouter dans l'algo récursif, pour éviter de recalculer des valeurs déjà calculées dans l'arbre de parcours.
Thibaut : est-ce que tu sera là pour la finale ? On pourra ptet se voir, lors de la demi-finale a Paris j'etais à l'entretien de jackichan

1Mo de données max c po bcp!
Sinon j'ai jamais entendu parler de programmation dynamique, mais de ce que tu dis c'est équivalent à l'option remember de ce cher maple

nitro : à moins que j'aie fait une grosse erreur d'incompréhension de la consigne, l'algorithme n'a pas à être dynamique.
Par contre, l'avant-dernière question nécessitait un algo dynamique (algo un peu du genre "recherche d'un chemin dans un labyrinthe")

Je serai à la demi-finale de Nantes. Pour la finale, je ne rêve pas : en m'entraînant sur le sujet de l'année dernière (http://www.prologin.org/archives/2002/demi-finales/sujets/lille-nantes/joseph.pdf) je me suis rendu compte que je suis incapable de résoudre la dernière question
Si tu peux m'aider... j'ai envoyé un mail à Mathias Hiron pour lui demander s'il pouvait m'expliquer grossièrement comment faire, mais il ne m'a pas répondu.

Il m'a répondu. Mon Dieu que c'est chaud ! Voici :
L'idée est de remplir un tableau qui est indexé par l'état des récipients.
Si tu as 5 récipients, cela correspond à un tableau à 5 dimensions : une par récipient. Chaque récipient ayant un volume entre 1 et 16, tu peux déclarer ton tableau comme ca :
int recipient[17][17][17][17][17];

dans ce tableau, tu stocques le nombre de transvasement nécessaires pour obtenir l'état des récipients correspondant aux index.

Par exemple, si recipient[0][4][2][5][2] contient 5, cela veut dire que tu peux, en 5 transvasements, avoir 0cl dans le récipient 1, 4cl dans le récipient 2, 2cl dans le récipient 3, etc.

Il suffit ensuite de remplir ce tableau : tu pars de la position initiale (recpient[0][0][0][0][0]), et tu determines toutes les postitions qu'on peut atteindre en 1 transvasement, a partir de cette position. Tu marques un 1 à chacune de ces positions, et tu stockes chacune d'elles dans une file. Tu prends ensuite le premier élément de cette file, et tu recommences... pour marquer toutes les positions qu'on peut atteindre en 2 transvasements, dont le premier donne cette position. Tu mets toutes les positions atteintes dans la file, sauf celles qu'on pouvait déjà atteindre en un nombre plus petit de transvasement.

Tu t'arrêtes dès que tu as atteint une position où tu as la contenance recherchée, dans un des récipients.

Ca me fait pensé à dijkstra (dsl si c mal ortografié)

Tu connais une URL ou je pourrais comprendre facilement ce qu'est Dijkstra ? J'en entend parler mais c'est impossible de savoir en quoi ça consiste !

ah non... moi g vu ca en cours. Si tu veux je cherche dans mes sujets et je t'envoie par la poste

ok mail moi ton adresse postale, sauf si tu veux attendre le prochain OpenTi (mais sur Paris)

Tu le ferais vraiment ??????? t'1 t'es cool toi

Mais si tu préfères, tu peux aussi les scanner et les mailer.

J'ai trouvé:
L'idée est de travailler avec ensembles qui sont modifiés au fur et à mesure de l'algo:
- un ensemble E contient les paires (y,l) des sommets y pour lesquels la longueur du plus court chemin de x à y est connu (cet ensemble va croire);
- un ensemble F contenant les paires (y',l') en attente; plus présisement, on y trouve tous les succésseurs des sommets de E qui ne sont pas dans E avec l' = min (l+p(y,y')), (y,l)€E,(y,y')€A.

Initialisation: E={(x,0)} et F={(y,p)|(x,y)€A, p=p(x,y)}

tant que F non vide
prendre dans F un couple (y,p) avec p minimal et l'ajouter à E
mettre à jour dans F les successeurs de y

Fin: E est l'ensemble des paires (y,p) tel qu'il existe un chemin dans G allant de x à y et p est la longueur du plus court chemin de x à y.

A est l'ensemble des arcs du graphe.
p(x,y) = poids du chemin
l = liste des couples (y,p) pour (x,y)€A et p=p(x,y).

pa le droit (epita)

charlyz> tu es en quelle anée? Quelle classe si tu es en SUP?

PaXaL : tu parles de quel problème

Bah ca c'est Dijstkraksdrerre pkoi?

Moi (enfin, je suis qualifié, mais je ne sais pas si j'irai).

(Je sais que tu le sais déjà, je l'indique aux autres, c'est tout)
Et au fait, tu as oublié de mettre que tu y allais aussi.

Donc :
- jackiechan
- Thibaut
- ???

Bonjour,
Je vais a la finale

kjus> Tu l'as passée où, ta demi-finale (et quand ?) ?

c quand au fait la finale?

généralement il la mette le seul we de 3 jour de mai.

Est-ce le cas cette année

vers le 25 avril je crois.
J'ai la flemme de vérifier, mais on peut trouver la date sur www.prologin.org