Questionnaire 2009 : exo 4

Les exos 1, 2 et 3 sont faciles. L'exercice 4 est moins trivial et est intéressant et amusant.

En attendant que la correction automatique fonctionne sur le site de prologin, l'équivalent de l'énoncé de l'exercice 4 (dans sa version "Caïn et Abel héritent") peut être soumis et testé sur

http://icpcres.ecs.baylor.edu/onlinejudge/external/5/562.html

Je n'ai pas encore essayé mais presque à coup sûr, la solution naïve n'y fonctionnera pas.

Le plus difficile, c'est l'exo 3 pour moi, le 4 m'a paru le plus facile.

Peut être que mon cerveau fonctionne à l'envers.

Euh j'aimerai d'autres exemples si quelqu'un en ont car j'ai trouvé une solution qui marche sur plusieurs exemples (ceux donnée par l'epreuve ainsi que celui donnée ci-dessous) mais je trouve ca assez ... comment dire ... trop simple trop evident , xD
(Si possible des exemples à N=4 voir N=5)

L'exo 4 peut se résoudre par l'algorithme trivial mais dès que N sera grand, le temps d'exécution autorisé sera dépassé. Si vous voulez vraiment savoir si votre méthode est correcte, testez l'exo que j'ai donné en lien ci-dessus (l'exercice est un peu plus général mais c'est exactement le même principe).

L'exo 3 est assez classique dans le genre (parcours de graphe) même si c'est pas trivial. Une fois de plus l'énoncé est assez mal posé car l'exemple est mal choisi (en regardant l'exemple, on a l'impression que les murs sont horizontaux mais je suppose qu'ils peuvent aussi être verticaux et pourquoi pas en oblique). Une fois de plus, au lieu de nous parler de la chatte fétiche de prologin et de sa gamelle, les auteurs feraient mieux de se concentrer sur l'exactitude et la précision de leurs énoncés et de joindre aux textes des graphiques suffisamment parlants (et il y a le problème de l'origine des axes en haut ou en bas, on ne sait pas). Ceux qui veulent quelque chose de plus tangible n'ont qu'à aller sur france-ioi où il y a un problème similaire (et qui initialement était assez mal voire très mal rédigé comme j'avais eu l'occasion de le dire à Mathias Hiron, énoncé qu'il a d'ailleurs modifié suite à mes observations).

Dur de dire qu'il n'est pas trivial, on ne connais rien dessus !
On ne connais pas les limites sur : N, le poids d'un conteneur, le temp, la mémoire... Dur de pseudo-coder quoi que ce soit avec ça ...

J'ajouterai que l'on ne sais pas si l'on doit avoir autant de conteneurs d'un coté que de l'autre ...

"le temps d'exécution autorisé"

Depuis quand il y a un temps d'execution?

Moi je n'ai pas eu cela quand j'ai répondu.

• L'exercice dont tu as donné le lien sur http://icpcres.ecs.baylor.edu/onlinejudge/ n'est pas le même. La question 4 n'est pas un cas particulier du problème "Dividing coins" dont tu donnes le lien.
  Pour le questionnaire, on vous demande le meilleur algorithme que vous pouvez faire pour ce problème, le barème est progressif suivant la rapidité de l'algorithme. Néanmoins, sur le site d'entraînement, les limites seront, pour ce problème :
  temps : 10 secondes, mémoire 10Mo, N sera inférieur ou égal à 100, et le poids de chaque conteneur sera compris entre 0 et 2000 (bornes incluses).

• A ma connaissance, tous les concours d'algorithmique font des histoires autour des problèmes : topcoder, acm, ioi, icfp... Concernant la position (0,0), elle est en haut à gauche dans l'exemple.

Le but est d'écrire un algorithme optimisé. Pour de grandes valeurs, on préfère obtenir le résultat en une seconde, plutôt qu'en dix jours. Teste ton code avec de grands nombres et essaie de voir si tu peux l'améliorer.

Pour la sélection du concours, il n'y a pas un temps d'exécution qui sert de limite, puisque le code est lu (par des humains). Mais, les correcteurs sont à mêmes de juger l'algorithme.

Enfin, quand la rubrique Entrainement sera disponible, tu pourras tester ton code : tu auras un ordre de grandeur des entrées, ainsi que le temps à ne pas dépasser sur le site.

Pour le problème 4, lors du rendu il faut suivre les contraintes que tu donne ?

Dans l'exemple en C++ je ne vois pas l'intérêt de passer n en paramètres (ce serais bien aussi qu'elle soit dans un espace de nom).

L'exercice dont tu as donné le lien sur http://icpcres.ecs.baylor.edu/onlinejudge/ n'est pas le même. La question 4 n'est pas un cas particulier du problème "Dividing coins" dont tu donnes le lien.

C'est vrai, l'exo 4 est selon moi moins facile. Mais c'est quand même dans le même genre.

Par contre, sur le même site, l'exo :

10032 - Tug of War

est quasiment identique sauf que vos contraintes sont plus sévères.