Méthode de résolution d'un sujet

Méthode de résolution d'un sujet
Arthur Charguéraud et Mathias Hiron pour www.france-ioi.org
Ce document a pour but de vous aider à résoudre à un sujet d'algorithmique efficacement. Il décrit une méthode d'approche en plusieurs étapes qui permet de partir du sujet et d'arriver à un code juste implémentant la solution. Les conseils que vous trouverez dans ce document ne sont pas du tout spécifiques aux IOI, et s'appliquent dès qu'il s'agit de trouver et/ou programmer des algorithmes.
Étapes de la méthode
Lisez le sujet
Résolvez des exemples
Cherchez un algorithme
Pseudo-codez l'algorithme
Vérifiez votre solution
Codez votre solution
Testez votre solution
Déboguez votre code
Annexe : Organisez-vous
1) Lisez le sujet
La première chose à faire consiste à bien lire le sujet, et entièrement ! Cela peut paraître évident, mais l'expérience montre que certaines personnes impatientes de résoudre le sujet passent à côté de quelques détails importants. Pour éviter cela, il faut donc prendre son temps pour lire le sujet, et ne pas hésiter à le relire plusieurs fois pour bien tout comprendre et ne laisser aucun détail de côté.
Ce qui est important :
Ne faites surtout pas de contresens. Si vous comprenez un autre sujet que celui qui est décrit, c'est foutu. Ne commencez pas à chercher avant d'être sûr d'avoir bien compris le sujet.
À la fin, vous devez avoir le sujet entièrement en tête. Il faut vraiment éviter d'y revenir toutes les 30 secondes pendant que vous cherchez une solution.
Reformulez le sujet le plus simplement possible, de manière à faire le tri entre les idées clés et le texte d'enrobage.
Reformuler un sujet, c'est ce que l'on fait naturellement lorsqu'on veut expliquer le sujet à quelqu'un qui ne l'a pas lu. En général, quelques courtes phrases suffisent lorsqu'on utilise des termes algorithmiques précis, comme « graphe », « plus court chemin », « dag » (graphe orienté sans cycle), « sous-ensemble », etc. Voici quelques exemples de reformulation de divers sujets :
On a N entiers entre -1000 et +1000, et on veut en piocher un certain nombre de manière à obtenir une somme donnée.
On a un arbre avec des poids positifs ou négatifs sur chaque nœud, et on cherche le sous-arbre dont le poids total est maximal.
On a un graphe quelconque, et on cherche un circuit passant une et une seule fois par chaque sommet.
On a un rectangle quadrillé, chacune des cases a une certaine altitude, le but est de calculer la plus grande zone rectangulaire tel que la hauteur de la plus basse case de cette zone et de celle de la plus haute ne diffère pas de plus de 10.
Il est absolument crucial de vérifier que la version reformulée est bien équivalente au sujet. Il ne faut oublier aucun détail, et s'assurer que la version reformulée n'est pas une généralisation ni une simplification du sujet.
Il est très important de se concentrer jusqu'au bout sur la compréhension totale et sans contresens du sujet. Il faut s'interdire d'essayer de deviner la totalité du sujet alors qu'on en a lu que la moitié, car c'est la meilleure façon d'interpréter de travers ce qui est écrit dans la seconde moitié. Dès que vous avez fini de lire la description, lisez rapidement les contraintes, vérifiez votre compréhension du sujet sur l'exemple fourni en l'étudiant attentivement, puis revenez sur les contraintes pour les apprendre par cœur. Essayer autant que possible de ne pas laisser votre esprit dériver vers la recherche d'une solution alors que vous n'êtes pas encore certain de rechercher sur le bon sujet !
2) Résolvez des exemples
Vous avez lu et compris le sujet, puis vous l'avez reformulé le plus simplement possible, maintenant il faut le résoudre. Chercher comme ça dans votre tête jusqu'à obtenir une solution complète et efficace n'est pas le moyen le plus efficace de procéder sur des sujets d'algorithmique difficiles.
La première étape pour chercher un algorithme consiste à se demander comme on ferait soi-même, pour résoudre le problème posé à la main. Comment cela peut-il aider ? Le cerveau humain est très intelligent (en tout cas par rapport à une machine) donc il a de bonnes chances de trouver une manière juste de résoudre le problème, et puis aussi il est plutôt flemmard en général, et il trouvera donc naturellement une méthode efficace pour résoudre le problème. Une solution juste et efficace, c'est exactement ce que l'on cherche !
Résoudre des exemples à la main sert même à beaucoup plus que faire sortir des idées. Pour résoudre des exemples, il faut bien commencer par générer des exemples. Pendant cette phase, on commence souvent par générer de tout petits exemples qui seront les cas limites, et on repère aussi quels vont être les pires cas à résoudre. Ensuite, le fait d'avoir des exemples entièrement résolus à la main permettra de vérifier que l'algorithme que l'on propose est juste, et servira plus tard à tester son implémentation.
En résumé, résoudre des exemples sert à :
faire sortir des idées ;
déterminer les cas limites (les cas triviaux et les cas pathologiques) ;
préparer un support pour tester et déboguer efficacement.
Ce qui est difficile dans cette étape, c'est de générer des exemples intéressants. Ces exemples doivent être :
différents, de manière à faire apparaître tous les cas possibles ;
corrects, sinon cela peut faire perdre énormément de temps ;
proprement résolus, pour pouvoir les utiliser facilement dans la phase de test ;
suffisamment gros pour être intéressants, mais pas trop pour ne pas perdre de temps.
On regroupera un jour dans un document des illustrations de résolution d'exemples à la main.
3) Cherchez un algorithme
Sur des sujets compliqués, vous ne trouverez généralement pas la solution en ne faisant que résoudre quelques exemples. Attention, cela ne veut surtout pas dire qu'il faut sauter cette étape de résolution d'exemples à la main. L'objectif est de ne pas rester bloquer sur le problème. Pour aboutir à une solution qui marche, il n'y a pas de secret, il faut s'y prendre méthodiquement.
Tout cela est détaillé dans la méthode de recherche d'un algorithme, dont voici le résumé des points :
Faites bien attention aux contraintes.
Générez des exemples, et résolvez-les entièrement à la main.
Cherchez une bonne représentation visuelle du problème.
Envisagez la solution bourrin.
Envisagez les algorithmes classiques, en particulier dynamiques.
Simplifiez le problème (de plusieurs manières), et recommencez récursivement au point 3.
Cherchez des contre-exemples à vos idées d'algorithmes.
Appliquez ces conseils récursivement, sur les sous-problèmes rencontrés.
Calculez la complexité en temps et mémoire de vos solutions.
4) Pseudo-codez l'algorithme
Une fois que vous avez décidé d'un algorithme à programmer pour un problème donné, ne vous jetez pas sur votre clavier pour le coder aussitôt. Entre avoir l'idée de l'algorithme en tête et savoir quel est le meilleur moyen de le programmer, il reste du travail. Si vous commencez directement à taper du code, vous risquez de vous perdre dans les détails et d'obtenir quelque-chose de trop compliqué, ou d'oublier certains points. Un même algorithme peut s'implémenter de nombreuses manières différentes, qui peuvent être plus ou moins difficiles à programmer, et surtout plus ou moins propices à l'apparition d'erreurs.
Pour avoir les idées claires au moment de l'implémentation et écrire votre programme d'une manière simple, en réduisant ainsi les risques de bugs, il est important de passer un certain temps à réfléchir sur papier à la manière dont vous allez organiser votre code. Pour ce faire, un moyen très efficace consiste à commencer par écrire le pseudo-code de votre algorithme. Le pseudo-code d'un algorithme est une version allégée de son implémentation. En se contentant des éléments essentiels du programme et en ignorant les détails spécifiques au langage, ou les parties évidentes, le pseudo-code permet de travailler efficacement sur la structure du programme et sur les points importants comme certaines limites ou les formules mathématiques utilisées.
Le pseudo-code étant beaucoup plus court que le programme complet, on peut en écrire plusieurs versions successives, de plus en plus simples, sans perdre de temps. Une fois que l'on a trouvé la manière la plus simple d'organiser son programme, on peut alors commencer à la programmer avec sérénité, en se focalisant sur les détails de l'écriture. Découvrez les secrets du pseudo-code, à quoi il ressemble, ce qu'on y met et ce qu'on n'y met pas.
5) Vérifiez votre solution
Attendez d'avoir un algorithme dont vous êtes sûr, et que vous ayez testé à la main sur quelques exemples, et vérifié qu'il soit suffisamment efficace, avant d'envisager de programmer. Programmer prend du temps, et s'apercevoir que son algorithme est faux une fois qu'il est implémenté est une perte de temps considérable. Ne commencez pas avant d'être sûr à 100 %. Bien réfléchir avant de commencer à coder vous évitera de perdre beaucoup de temps par la suite. L'expérience montre que les candidats passent beaucoup plus de temps à corriger des erreurs, de tous types, qu'à résoudre le problème lui-même et écrire la partie principale du programme.
Ne commencez pas à coder avant d'avoir vérifié que votre algorithme :
répond bien au sujet (relire le sujet !),
est correct (en particulier qu'il résout bien les exemples que vous avez générés au début, y compris les cas limites),
a bien la complexité que vous pensez (recalculez-là soigneusement),
a le pseudo-code le plus simple possible.
Assurez-vous aussi qu'il restera du temps pour tester et déboguer une fois que vous aurez codé. S'il ne reste pas assez de temps, choisissez une version plus simple quitte à ne viser qu'un score partiel. Il vaut mieux avoir 9 chances sur 10 d'assurer 50 % des points, plutôt que de viser 100 % des points mais de n'avoir qu'une chance sur quatre d'obtenir ce score, en laissant ainsi 3 chances sur 4 d'avoir un bug et de n'obtenir au final que 10 % des points. Personne ne peut prétendre coder sans bugs. Il faut savoir en tenir compte et limiter son ambition d'obtenir 100 % des points pour assurer en moyenne un meilleur score et progresser plus.
6) Codez votre solution
Lorsque vous écrivez votre code, votre objectif doit être avant tout de réduire les risques de bugs :
Faites du code le plus simple possible, non pas en minimisant le nombre de caractères du source, mais en minimisant la probabilité d'apparition d'un bug dans le code.
N'essayez pas d'optimiser le code, vous ne gagnerez pas plus de 10 ou 15 % des points, et vous augmentez sérieusement le risque d'introduire un bug et du coup de vous retrouvez avec 0 point. S'il vous reste du temps et que votre algorithme n'est pas dans une complexité suffisante pour prétendre avoir 100 % des points, optimiser la principale boucle de l'algorithme sera beaucoup plus rentable que de parsemer l'ensemble du code d'optimisations diverses.
Prenez votre temps. Avec du bon pseudo-code, le code peut s'écrire en peu de temps. En prenant bien votre temps, vous mettrez peut être 5 minutes de plus, mais vous diviserez par deux le nombre de bugs dans le code, et ce sera autant de temps qui ne sera pas perdu à déboguer.
Toutes ces techniques visant à simplifier le code au maximum et à réduire l'apparition de bugs sont détaillées pour ceux qui codent en C++ dans le document coder proprement en C/C++.
Lorsque vous avez fini d'écrire la dernière ligne de code, vous n'avez pas pour autant terminé cette phase de code. Eh oui, lorsqu'on dit « coder », on sous-entend toujours « coder juste ». Pour coder juste, il faut être comme on l'a dit attentif durant toute la phase d'écriture du code, et il faut également se concentrer à fond ensuite pour relire le code. Relisez donc votre code, plusieurs fois et de différentes manières. Il y a des techniques pour ça, visant à vérifier que vous n'avez rien oublié et que chaque ligne est correcte. Par exemple on peut relire le code ligne par ligne, mais aussi variable par variable. Il est également intéressant de relire le code en parallèle avec le pseudo-code.
Ces techniques de relecture seront bientôt détaillées dans un document spécifique.
7) Testez votre solution
Il y a deux choses à vérifier. D'abord que votre algorithme est bien correct. Ensuite, s'il est correct, qu'il a bien la vitesse et la consommation mémoire attendue. Évidemment, dans l'idéal tout est bon. Mais en pratique, il est plutôt rare que les algorithmes soient justes du premier coup. Tester sa solution ne prend de toutes manières pas beaucoup de temps lorsque tout est correct.
Pour tester son implémentation, la première méthode qui vienne à l'esprit consiste à prendre un exemple, lancer le programme dessus, regarder la sortie, et la comparer au résultat obtenu en faisant les calculs à la main. Une seconde méthode bien plus puissante consiste à vérifier que la structure de données utilisée par l'algorithme se comporte correctement au cours de l'exécution de l'algorithme. Précisons cela en distinguant deux cas possibles :
Premièrement, si les structures de données utilisées dans l'algorithme sont simples (tableaux), on peut les afficher en entier au fur et à mesure des itérations de l'algorithme. On vérifie ainsi qu'à chaque étape l'état de l'algorithme est entièrement cohérant.
Second cas, les structures utilisées sont complexes, et à ce moment là on va les tester séparément avant de commencer à tester l'ensemble de l'algorithme. On va donc écrire du code en plus effectuant quelques requêtes sur ces structures complexes afin de vérifier que leur comportement est cohérant.
Dans les deux cas, le travail supplémentaire est relativement minime : il faut rajouter quelques lignes de code. L'intérêt de la méthode est qu'elle facilite grandement la détection et la correction d'éventuels bugs.
Voici l'ordre recommandé des exemples à tester :
l'exemple du sujet,
les exemples résolus entièrement à la main,
d'autres exemples générés sur le tas,
des exemples de pire cas, dans la mesure du possible.
Souvent, pour générer un pire cas, il suffit de générer un fichier d'entrée à l'aide d'une boucle sur un printf. Mais pour certains sujets, c'est bien plus délicat, et on n'a pas toujours le temps d'écrire un générateur. Dans ces cas, il faut relire une fois de plus la complexité théorique de l'algorithme, et faire confiance à la théorie.
Il y aura prochainement un document pour détailler l'écriture les lignes d'affichage pour tester.
Très important : conservez vos fichiers de tests. Ne prenez pas la mauvaise habitude d'écrire un premier test, puis de le modifier plusieurs fois en retestant à chaque fois, sans conserver les différentes versions. Conservez tous vos fichiers de tests, pour pouvoir les réévaluer rapidement si vous faites une modification. En corrigeant un bug, on en ajoute souvent un autre... Il ne faut pas perdre de temps à recréer des tests que vous avez effacés.
8) Déboguez votre code
Lorsqu'on trouve un exemple sur lequel l'algorithme se plante, il faut absolument commencer par simplifier l'exemple qui bug. Passez une bonne minute s'il le faut pour obtenir l'exemple le plus petit possible que le programme ne résout pas correctement, cela vous fera gagner beaucoup de temps. En effet, plus l'exemple est simple, et moins il y a de choses à afficher pour suivre l'exécution de l'algorithme pas à pas sur cet exemple.
Une fois que vous avez votre test minimal qui plante, utilisez les instructions d'affichage des structures de données pour localiser le bug. Si cela ne suffit pas, rajoutez quelques lignes d'affichage pour visualiser quels sont les choix qu'effectue l'algorithme (par exemple quels sont les paramètres des appels récursifs), et ce en plus des données contenues dans la structure. Ce qu'il ne faut pas faire c'est afficher uniquement les paramètres des appels récursifs : vous verrez bien qu'au bout d'un moment il y a un problème, mais vous ne saurez pas pourquoi.
Remarque : certains adorent utiliser leur débogueur préféré (par exemple gdb). Ces outils sont très efficaces pour déboguer des gros projets de programmation, mais lorsqu'il s'agit d'algorithmique ils se révèlent assez inadaptés. Le principal cas où un débogueur sert, c'est pour localiser un segfault (lecture à une adresse mémoire invalide).
Déboguer prend énormément de temps par rapport au reste. Il faut impérativement être rigoureux, méthodique et savoir s'arrêter au bout d'un certain temps même si on n'a pas trouvé le problème. Il est dangereux de passer plus de 15 ou 20 minutes à déboguer. Dans 95 % des cas si l'on ne trouve pas tous les bugs dans les 10 minutes, c'est que le code est trop compliqué ou alors (encore pire) que l'algorithme est faux. Conclusion : il faut vraiment tout faire pour que vous n'ayez pas besoin de déboguer, c'est-à-dire faire très sérieusement toutes ces phases :
simplifier l'algorithme,
vérifier l'algorithme,
simplifier le pseudo-code,
vérifier le pseudo-code,
relire le code des différentes manières possibles,
tester indépendamment les morceaux difficiles du code.
Annexe : Organisez-vous
Pour bien réfléchir, il faut être dans de bonnes conditions. En particulier, il faut éviter de perdre du temps à retrouver sur quelle page on a écrit le premier exemple, il vaut mieux gommer des lignes que les rayer dans tous les sens, et c'est pratique de laisser dans la marge des petites notes pour s'y retrouver entre les différentes phases de recherche de la solution. Pour être dans de bonnes conditions :
Prenez un porte-mine et une gomme. C'est très pratique de gommer, ça permet d'améliorer une partie de ce qu'on a écrit sans tout recopier.
Prenez une grande feuille toute blanche. Trouvez du papier qui ne se froisse pas quand on le gomme plusieurs fois.
Notez le nom de l'exercice et le numéro de la page en haut de chacune des feuilles utilisées pour l'exercice, afin de vous y retrouver plus tard. L'idéal est d'avoir une grande feuille double.
Marquez l'heure de début et de fin de chaque phase de recherche dans la marge, pour pouvoir bien gérer votre temps.
N'ayez pas la flemme de vous mettre dans de bonne conditions, vous verrez c'est très rentable. Si vous doutez vraiment de ces conseils, essayez au moins une fois de les suivre à la lettre pendant toute une épreuve de 5 heures, et vous comprendrez peut-être.
Conclusion
Si certains points vous semblent obscurs et que vous ne voyez pas trop où l'on veut en venir, envoyez un mail à entraineur[at]france-ioi.org pour nous aider à améliorer la formulation des idées dans ce document.
Si vous pensez que nos conseils ne sont pas optimaux et que votre façon de faire est plus efficace, prenez le temps d'appliquer nos conseils à la lettre sur trois sujets d'algorithmique de suite. Une fois que vous les avez essayés vraiment, si vous n'avez pas changé d'avis, envoyez-nous un mail pour nous expliquer votre point de vue. Peut-être participerez-vous ainsi à l'amélioration de la méthode !
Bon courage, et bonne progression en algorithmique !

Méthode de recherche d'un algorithme
Mathias Hiron pour www.france-ioi.org
Voici un ensemble de conseils à appliquer pour trouver la solution d'un problème algorithmique, en particulier pour les problèmes du type de ceux proposés aux IOI. Prenez l'habitude de les appliquer sur tous les sujets, dans l'ordre, jusqu'à-ce que cela devienne un automatisme. Une liste résumée de ces conseils est donnée en bas de la page.
Cette méthode est le fruit de plusieurs années d'expérience et s'améliore régulièrement, entre autres grâce aux réactions de nombreux candidats qui l'utilisent. Elle est issue de l'application d'une règle simple que nous vous conseillons de suivre : après avoir résolu un problème, prenez du recul sur votre processus de réflexion, et déterminez ce qui vous a permis d'avoir la bonne idée, ce qui vous a fait gagner du temps, ou ce qui vous en a fait perdre. Déduisez-en ce que vous pourrez faire à l'avenir pour être plus efficace et notez le. C'est l'application de cette philosophie à nous-mêmes et aux candidats, qui a abouti à la méthode présentée ici.
Son premier objectif est de vous aider à réfléchir, sans rester coincé devant le problème : lorsque vous n'avez pas d'idée tout de suite, rester devant le problème en laissant libre cours à votre réflexion devient très vite une perte de temps. Ces conseils permettent d'avoir toujours de quoi avancer. Il ne s'agit pas d'une méthode miracle qui résoud les problèmes à votre place, mais une fois que vous la maîtriserez, elle vous permettra très probablement d'obtenir de bien meilleurs résultats que si vous vous contentez de réfléchir sans méthode particulière.
L'illustration suivante résume le fonctionnement de la méthode. Sans méthode particulière, votre intelligence, vos connaissances, etc. vous permettent déjà de résoudre des problèmes d'une certaines difficulté.
Appliquer une méthode revient à décomposer la réflexion en étapes, à poser des jalons qui vous permettent de résoudre des problèmes bien plus difficiles que ceux que vous êtes capables de résoudre naturellement.
Après l'avoir appliquée systématiquement et entièrement de nombreuses fois, il est bien sûr possible que certaines parties ne vous conviennent pas, et que vous trouviez plus efficace de procéder autrement. Dans ce cas, n'hésitez pas à nous contacter, pour nous dire de quelle manière vous procédez, cela peut nous aider à améliorer ces conseils. Evitez cependant de décréter que certaines choses sont inutiles, avant même de les avoir mises plusieurs fois en pratique.
1) Lisez bien le sujet et reformulez-le
La première chose à faire consiste à bien lire le sujet, et entièrement.
Cela peut paraître évident, mais l'expérience montre qu'il arrive à tout le monde de lire le sujet un peu vite, et de ne pas voir certains détails importants. Pour éviter cela, il faut donc prendre son temps pour lire le sujet, et ne pas hésiter à le relire plusieurs fois pour bien tout comprendre et voir tous les détails.
Les problèmes vous sont généralement donnés sous la forme d'une petite histoire. Une partie de votre travail consiste à décrypter cette histoire pour vous faire une idée claire du problème. Souvent, l'essence du sujet peut se résumer en une ou deux phrases simples. Ecrire ces phrases aide à mieux avoir l'ensemble du problème en tête, donc à le résoudre. Reformulez-donc le sujet le plus simplement possible, sous la forme d'une question. Relisez ensuite le sujet pour bien vérifier que votre reformulation est correcte, et qu'il n'y manque rien d'important.
N'essayez pas de commencer à chercher des idées d'algorithmes au cours de la lecture, consacrez-vous entièrement à la compréhension du sujet. Si malgré cela vous avez une idée d'algorithme au cours de la lecture du sujet, vous pouvez la noter brièvement pour ne pas l'oublier, mais reprenez aussitôt la lecture sans y repenser. En cours de lecture, n'hésitez pas à noter les points importants et à souligner les détails à ne pas oublier.
Après cette phase de lecture, vous devez connaître le sujet suffisamment pour ne plus avoir le moindre doute et pouvoir rechercher un algorithme sans hésiter sur la nature du sujet.
2) Faites la liste des dimensions du sujet
Dans tous les sujets, on vous fournit un certain nombre de données en entrée, à partir desquelles vous devez calculer puis afficher un résultat. Ces données étant au coeur du problème, il est important de les décrire précisément et d'avoir bien en tête les valeurs qu'elles peuvent prendre. Chaque type d'information que l'on vous donne en entrée, ou que l'on vous demande en sortie, est ce que nous appellerons une dimension du problème.
Un moyen simple de déterminer quelles sont les dimensions associées à certaines données consiste à se demander quelles structures il est nécessaire de déclarer pour les stocker. Chaque variable ou attribut d'une structure simple est une dimension. L'indice d'un tableau 1D correspond également à une dimension, de même que chacune des valeurs contenues dans une case du tableau. Pour un tableau 2D, on a deux dimensions pour les indices, etc.
Juste après la lecture du sujet, notez donc bien clairement la liste de ses dimensions, en distinguant :
Les dimensions d'entrée : elles correspondent à tout ce qui est fourni à votre programme.
Les dimensions de sortie : elles correspondent à ce que l'on demande à votre programme d'afficher, ainsi qu'à ce qu'il est indispensable de calculer pour pouvoir obtenir le résultat. Par exemple si on vous demande d'afficher le coût total d'un chemin, ce coût est une dimension de sortie, mais le nombre d'étapes du chemin correspondant l'est également, même si on ne vous demande pas de l'afficher.
Les dimensions implicites : elles correspondent à des dimensions qui n'apparaissent que si l'on change de point de vue sur le sujet. Par exemple si l'on vous donne des coordonnées de points dans le plan, l'angle des droites allant de chaque point à l'origine peut être vu comme une dimension (si cela semble utile) même s'il n'en est pas fait mention dans le sujet. De même, si l'on donne dans le sujet des rectangles sous la forme des coordonnées de deux sommets, il peut être intéressant de lister la largeur et la hauteur des rectangles comme dimensions implicites.
Pour chacune de ces dimensions, précisez :
Les valeurs minimales et maximales. Elles sont souvent données directement dans le sujet, mais il est parfois nécessaire de faire un calcul pour les trouver, en particulier pour les dimensions de sortie.
Les valeurs minimales et maximales de chaque dimension sont une donnée très importante du sujet. Le temps d'exécution et la quantité de mémoire nécessitées par votre programme en dépendent directement. Pour que votre programme obtienne un bon score, il faut donc qu'il fonctionne dans les limites imparties, même pour les valeurs les plus grandes de toutes les dimensions.
Si l'ordre est important ou non pour cette dimension. Par exemple, s'il s'agit d'un indice de tableau, la solution change-t-elle si on change l'ordre des cases ?
Si l'ordre des valeurs d'une dimension est important, alors vous pouvez envisager de vous baser dessus dans votre algorithme, par exemple en parcourant les données selon cet ordre. Si au contraire elles n'influencent pas le résultat, alors vous pouvez envisager d'imposer l'ordre de votre choix.
En dessous des dimensions, notez également les contraintes de temps et de mémoire du sujet. Ces contraintes ne sont pas définies au hasard : elles sont souvent choisies de telle sorte que l'algorithme le plus efficace puisse tout juste s'exécuter dans les limites imparties.
En regardant les dimensions et en les mettant en relation avec les limites de temps et de mémoire, vous pouvez déjà vous faire une bonne idée de la complexité en temps et mémoire que vous pouvez vous permettre. Pensez donc systématiquement à calculer ces complexités possibles, puis à partir de ces complexités, essayez de deviner le type d'algorithme à utiliser. Par exemple si une complexité en temps de O(N.log(N)) semble le maximum possible d'après les limites, il y a de fortes chances que la solution fasse intervenir un algorithme de tri, une dichotomie, ou bien un arbre binaire.
3) Cherchez une bonne représentation visuelle du problème
L'un des moyens les plus efficaces pour avoir des idées sur un problème est, comme indiqué à l'étape suivante, de créer vos propres exemples, puis d'essayer de les résoudre à la main. Pour que cette étape soit efficace, il faut que l'on puisse "voir" un maximum de choses sur ces exemples.
Il existe souvent de nombreuses manières de les représenter, et suivant celle que vous choisissez, ce qu'il faut faire apparaît plus ou moins nettement. Choisir la ou les bonnes représentations visuelles est donc une étape cruciale dans la résolution d'un problème. Ce qui n'est pas du tout évident quand on lit la description d'un problème peut apparaître très nettement une fois celui-ci présenté selon une bonne représentation visuelle.
La représentation visuelle la plus intéressante n'est pas toujours celle qui semble naturelle au départ. Ne vous contentez donc pas de votre première idée, même si elle vous semble bonne. Dans certains problèmes, il y a de très nombreuses représentations visuelles intéressantes, mais un petit nombre d'entre-elles, voire une seule fait apparaître l'idée de la solution.
Pour représenter un exemple du problème, vous ne disposez que d'une feuille de papier. Cette feuille n'a que deux dimensions, ce qui signifie que seules deux dimensions du problème pourront être représentées très clairement, et que les autres, quelle que soit la manière dont on les représente, n'apparaîtront pas aussi nettement. Il est donc très important de bien choisir ces deux dimensions parmi l'ensemble des dimensions listées à l'étape précédente. Lorsqu'il y a plusieurs possibilités, il ne faut pas hésiter à toutes les essayer, avant de choisir la meilleure. Dans certains cas, il peut être intéressant d'en garder deux, voire plus, et de les utiliser côte à côte sur chacun des exemples.
Pour certains types de sujets, il est bon de prendre l'habitude de toujours essayer certaines représentations dites "classiques", qui fonctionnent bien. Ainsi, dans le cas d'un problème de graphe, un représentation naturelle consiste à placer les noeuds à divers endroits et de dessiner simplement les arcs qui relient ces noeuds. Il existe cependant une manière de représenter un graphe qui aide mettre en évidence de nombreuses propriétés : la représentation de Tarjan, qui présente un graphe en mettant en valeur la forêt correspondant à un parcours en profondeur de ce graphe.
Passez donc toujours un certain temps à chercher la meilleure manière de représenter visuellement le problème, cela pourra beaucoup vous aider à trouver sa solution. Appliquez alors cette représentation sur tous vos exemples. Pensez également à bien choisir la manière de représenter les solutions de ces exemples.
4) Générez des exemples et résolvez les entièrement à la main.
Un très bon moyen pour aider vos idées à se former et éviter de vous engager sur de fausses pistes, est d'essayer de résoudre un exemple à la main. Partez de l'exemple fourni dans le sujet, ou d'un exemple encore plus simple, et essayez de résoudre cet exemple à la main simplement à l'aide d'un crayon et d'un papier.
Pendant que vous cherchez à résoudre cet exemple vous-mêmes, faites attention à la manière dont vous procédez. En cherchant à résoudre des exemples, votre cerveau va automatiquement chercher des moyens efficaces qui pourront très probablement être utilisés par un algorithme. Si vous voyez tout de suite la réponse pour cet exemple, demandez-vous pourquoi vous la voyez si facilement. Essayez ensuite sur des exemples plus difficiles, en vous débrouillant pour que la solution ne saute pas aux yeux, mais demande un minimum de travail. La solution ressemble très souvent à ce que vous avez tendance à faire automatiquement à la main, profitez-en.
Essayer plusieurs exemples peut aussi vous aider à bien avoir tous les paramètres du sujet en tête, donc ne peut que vous aider à avoir des idées.
Lorsque vous générez des exemples, ne vous contentez pas de les créer au hasard. Essayer de générer un exemple pour chaque cas particulier auquel vous pouvez penser, et des exemples utilisant des valeurs extrêmes. Générez avant tout des exemples petits et simples, avant d'attaquer des exemples plus gros et compliqués.
Régulièrement au cours de votre réflexion, si vous ne trouvez pas d'algorithme, il ne faut pas hésiter à réessayer à nouveau sur d'autres exemples que vous créez vous-mêmes. Il faut le faire si vous ne trouvez pas tout de suite l'algorithme naïf, et également une fois que vous l'avez, si vous ne voyez pas rapidement d'algorithme efficace. Et même si vous avez un algorithme, il est toujours utile de l'essayer à la main sur des exemples.
Lorsque vous faites cette étape, faites le proprement et conservez les exemples que vous utilisez, ainsi que la réponse associée. N'ayez pas peur de perdre du temps là dessus : ces exemples serviront plus tard de tests pour votre solution. Créez dès à présents les fichiers .in et .out avec lesquels vous testerez votre programme. Ceci est d'ailleurs une raison supplémentaire de ne pas bâcler cette étape : tout ce que vous chercherez à la main vous servira plus tard, pour débugger votre code.
Attention : il est parfois rentable, plutôt que de générer plusieurs exemples à la main, d'écrire une version de l'algorithme naïf permettant de générer de nombreux exemples. Ecrire le code d'un algorithme naïf est souvent très simple et les exemples générés ont moins de chances de contenir des erreurs que s'ils étaient écrits à la main. Dans tous les cas, il faut quand même en vérifier un certain nombre à la main pour s'assurer qu'il n'y a pas de bugs dans votre algorithme naïf.
5) Exprimez le problème comme une question à laquelle on peut répondre récursivement, et envisagez la solution naïve associée.
Avant de commencer à chercher des algorithmes puissants et complexes, il faut s'assurer que l'on sait résoudre le problème indépendamment des limites de temps et de mémoire. Le but de cette étape est donc de trouver au moins une manière très simple de résoudre le problème, par un algorithme dit naïf, ou bourrin. Une fois que l'on a exprimé clairement un ou plusieurs algorithmes naïfs, on peut alors essayer de les améliorer, pour obtenir des complexités en temps et mémoire raisonnables.
Lors de l'étape de lecture du sujet, vous aviez reformulé celui-ci sous la forme d'une question. Dans la plupart des problèmes, il est possible de généraliser cette question pour qu'elle puisse exprimer non seulement l'ensemble du problème, mais également des sous-ensembles ou des variantes de ce problème, de telle sorte que l'on puisse utiliser les réponses sur ces sous-ensembles, pour former la réponse du problème complet.
Par exemple, si un problème peut s'exprimer sous la forme de la question suivante :
Quelle est la somme des valeurs fournies en entrée ?
On peut généraliser cette question en :
Quelle est la somme des K premières valeurs fournies en entrée ?
La différence avec la question initiale est qu'elle dépend désormais d'un paramètre : le nombre K des valeurs à traiter, là où la question initiale portait sur l'ensemble des valeurs de l'entrée. La nouvelle question généralisée permet toujours de répondre à l'ensemble du problème. Il suffit pour cela d'utiliser comme valeur pour le paramètre K, le nombre total de valeurs de l'entrée.
L'avantage de la question généralisée, est que l'on peut y répondre en la reposant pour une valeur différente : pour répondre à la question "quelle est la somme des K premiers nombres fournis en entrée", on peut reposer la question "quelle est la somme des K-1 premiers nombres fournis en entrée", et ajouter la Kème valeur de l'entrée à la réponse obtenue. Cela donne donc un algorithme simple pour résoudre ce problème, même s'il n'est pas nécessairement le plus efficace.
L'exemple présenté est un peu simpliste, mais pour peu que l'on trouve la bonne question et la bonne généralisation, la plupart des sujets, mêmes très difficiles, peuvent se résoudre de cette manière. Cela donne une solution récursive souvent très lente, mais qui a le mérite d'être simple et de fonctionner. C'est surtout une très bonne base pour chercher ensuite des solutions plus rapides.
Pour trouver une telle généralisation, ajoutez chaque dimension de l'entrée séparément, comme paramètre de la question initiale. Essayer d'atteindre ainsi une version de la question à laquelle on puisse répondre en la reposant avec des valeurs différentes des paramètres. Dans certains cas, il peut être nécessaire d'utiliser deux, voire plus de paramètres simultanément.
Pour chaque question généralisée qui permet une telle récursion (ne vous arrêtez pas à la première), envisagez l'algorithme naïf correspondant, et calculez sa complexité en temps et en mémoire. Il s'agit généralement d'une fonction récursive dont les paramètres sont ceux de la question, et dont la valeur de retour est la réponse à cette question. Parfois, la solution naïve suffit telle quelle. Dans d'autres cas, une petite modification, profitant d'une propriété mathématique du sujet ou d'une simple astuce peut permettre à la solution exhaustive de fonctionner dans les limites de temps et de mémoire imparties.
Vérifiez donc systématiquement chaque solution naïve, et regardez ce qu'il vous manque pour qu'elle passe en dessous des limites de temps et de mémoire. Cherchez alors ce que cette solution naîve fait en trop, et cherchez un moyen de l'éviter.
Un très bon moyen pour "voir" ce qu'un algorithme naïf fait en trop, consiste à l'exécuter vous-même, à la main, sur un exemple de bonne taille. Il y a de fortes chances qu'à force de l'appliquer mécaniquement, vous remarquiez que certaines opérations pourraient être évitées, et aboutissiez à une idée d'algorithme plus rapide.
Un autre moyen également très efficace pour vous aider à améliorer chaque algorithme naïf, consiste à dessiner une bonne représentation visuelle de ce qu'il fait. On peut dans certains cas, voir apparaître très clairement les calculs non indispensables effectués.
Lorsque la solution naïve est simple à programmer, n'hésitez pas à le faire, cela a plusieurs avantages :
Vous aurez au moins un programme qui permet d'obtenir quelques points.
Vous pouvez l'utiliser pour résoudre de nombreux exemples, et remarquer certaines choses en analysant les solutions.
Il y a des chances qu'une partie du code puisse être repris tel-quel dans la solution finale, et il est plus facile de débugger du code d'une solution naïve simple, que de débugger le même code lorsqu'il fait partie d'un algorithme complexe.
Quand vous aurez implémenté un meilleur algorithme, vous pourrez comparer les résultats, et vérifier que vous n'avez pas fait d'erreur.
Si votre algorithme final ne fonctionne pas à tous les coups, vous pourrez intégrer la solution naïve à votre source et l'appeler pour les petits tests, pour vous assurer d'avoir au moins les points correspondants.
6) Envisagez les algorithmes les plus classiques.
Il n'y a pas des millions de types de problèmes différents. On peut en général les classer dans une quinzaine de catégories. Certains types d'algorithmes apparaissent très très souvent. Vous pouvez trouver une liste des algorithmes les plus utilisés, dans le cours 'Connaissances nécessaires pour résoudre des problèmes IOI'.
Les algorithmes les plus classiques apparaissent tellement souvent, qu'une des premières choses à faire lorsque vous réfléchissez sur un problème, est de regarder si ces algorithmes classiques peuvent aider à résoudre le problème. Cherchez comment vous pouvez les appliquer, et cela vous donnera peut-être la solution.
Il n'est pas nécessaire d'énumérer chacun des algorithmes classiques : on peut le faire par catégorie. Par exemple, pour chaque sujet, essayez de voir s'il est possible de voir le problème comme un problème de graphes, même si cela ne semble pas être le cas a priori : est-ce qu'on peut représenter certaines choses comme des noeuds, et d'autres comme des arcs entre ces noeuds ? Si cela n'a aucun sens, alors aucun des algorithmes de graphes n'a de chance de fonctionner, et vous pouvez éliminer d'un coup toute cette catégorie.
Ceci est aussi particulièrement valable pour les problèmes de type programmation dynamique. De très nombreux problèmes entrent dans cette catégorie. Quel-que soit l'exercice, il faut donc passer un certain temps à se demander s'il peut ou non se résoudre par un algorithme dynamique, ne serait-ce qu'en partie.
Si un algorithme classique fonctionne mais ne permet pas de respecter les limites de temps et de mémoire, notez le quand même. Il pourra vous servir si vous ne trouvez rien de mieux.
7) Résolvez des versions simplifiées du problème, puis généralisez les solutions obtenues
Ce conseil est le plus important de cette liste, il ne faut jamais oublier de l'appliquer.
Si vous ne trouvez pas la solution tout de suite, ou après avoir essayé à la main sur plusieurs exemples, il ne faut pas trop tarder. Le problème est trop difficile pour que vous puissiez trouver facilement la solution, mais il y a un moyen qui peut souvent y conduire. Il s'agit de transformer le problème en le simplifiant, puis d'essayer de résoudre la version simplifiée.
Cette technique est particulièrement efficace pour les raisons suivantes :
Il est plus facile de trouver les solutions des versions simplifiées, que de résoudre le problème initial.
Tout algorithme qui résoud le problème complet doit nécessairement résoudre les problèmes simplifiés, donc doit au moins faire ce que fait une solution de chacune des versions simplifiées.
Les idées qui permettent de résoudre les versions simplifiées sont des idées qu'il faut généralement avoir, pour être capable de résoudre le problème initial.
Pour appliquer ce conseil efficacement, il faut :
Chercher toutes les versions simplifiées du problème qui gardent un sens.
Bien choisir quelles versions tenter de résoudre en priorité, et y réfléchir dans cet ordre.
Une fois les versions simplifiées résolues, généraliser ces solutions, ou les adapter au problème complet.
Pour effectuer chacune de ces étapes efficacement, il est important de bien s'organiser, nous allons décrire comment :
a) Listez les simplifications ayant un sens.
Tous les problèmes ne peuvent pas être simplifiés sans perdre complètement leur nature, mais la plupart le sont. Si vous simplifiez un problème puis trouvez la solution de cette version simplifiée, cela vous donne un très bon point de départ pour chercher la solution de la solution complète.
Il y a deux manières d'obtenir des versions simplifiées d'un problème, à appliquer systématiquement :
Simplifier certaines des dimensions du problèmes. Ceci se fait de manière assez mécanique :
Pour chacune des dimensions listées à l'étape 2, essayez de :
la supprimer complètement
la réduire à la plus petite valeur, ou au plus petit sous-ensemble de valeurs pour lequel le problème garde un sens.
la fixer à une valeur bien précise (la même valeur pour tous les objets).
Supprimer ou simplifier certaines règles du sujet.
Cette partie est moins mécanique, mais est en général assez simple à appliquer. Si le sujet interdit certaines opérations, on peut par exemple essayer sans les interdire. Ou s'il y a trois types actions possibles à partir d'une situation, on peut essayer de réduire à un ou deux types d'actions, etc.
Pour chacune de ces simplifications, vérifiez que le nouveau problème obtenu a un sens. S'il en a un, reformulez le clairement sur votre feuille, éventuellement accompagné d'une petite représentation graphique associée.
b) Choisissez l'ordre dans lequel résoudre les versions simplifiées, et réfléchissez y dans cet ordre.
Une fois la liste complète des simplifications obtenue par la méthode décrite ci-dessus, classez la pour les étudier en commençant par celle qui semble la plus intéressante. Il est important de noter que toutes les simplifications ayant un sens sont utiles, et qu'il est nécessaire d'être capable de toutes les résoudre pour pouvoir résoudre le problème entier.
Lorsque vous choissez un version simplifiée du problème, définissez la précisément, ainsi que les contraintes sur ses variables.
Vous devez ensuite chercher la solution de cette version simplifiée du problème, exactement de la même manière que vous chercheriez la solution d'un problème indépendant. Appliquez tous les conseils de la méthode : recherchez une solution naïve, trouvez une bonne représentation visuelle, essayez des exemples à la main, etc. Il ne faut pas hésiter non plus à simplifier une nouvelle fois le problème, tant que cela a du sens.
Il faut bien vous dire que si vous ne réussissez pas à résoudre la solution simplifiée, vous ne pourrez pas non plus résoudre la version complète. Il faut donc chercher à la résoudre avec autant d'attention que si c'était un problème complet.
c) Généralisez, ou réutilisez les solutions obtenues, pour résoudre le problème initial.
Une fois que vous avez un, ou plusieurs algorithmes permettant de résoudre les versions simplifiées, il faut regarder si on peut les utiliser pour la version complète. Remarquez que s'il y a quelque-chose que vous êtes obligé de faire pour résoudre la solution simplifiée, il y a de très grandes chances que vous soyiez obligé de le faire également pour la version complète. Si par exemple la solution simplifiée se résout avec un simple algorithme de plus court chemin, la solution évoluée sera donc au moins un algorithme de plus court chemin, il y a très peu de chances que vous trouviez une version complète qui évite d'utiliser un tel algorithme.
Envisagez toutes les manières de généraliser chaque solution simplifiée obtenue :
L'appliquer telle-quelle, en transformant le problème complet pour qu'il soit équivalent à la version simplifiée.
L'utiliser pour résoudre une partie du sujet, au sein d'un algorithme plus général.
Répéter cette solution pour chaque valeur possible de la dimension qui a été supprimée ou réduite.
Si le problème a des dimensions symétriques, et que la simplification a consisté à supprimer l'une de ces dimensions, appliquez la solution simplifiée selon l'une des dimensions, puis selon l'autre.
Essayer de généraliser l'idée même qui a donné la solution simplifiée, en réintégrant la dimension supprimée à l'ensemble de l'idée.
N'oubliez pas que chacune des solutions des diverses simplifications est utile, et que la solution complète est souvent une combinaison des solutions simplifiées.
8) Cherchez des contre-exemples à vos idées d'algorithmes.
Vous pouvez avoir une idée d'algorithme, mais ne pas être entièrement sûr qu'elle fonctionne. Vous pouvez également savoir qu'elle ne fonctionne pas toujours, mais ne pas avoir de meilleure idée, ou ne pas savoir exactement dans quel cas elle ne fonctionne pas.
Dans ces deux situations, un moyen efficace de mettre les choses au clair, est de chercher des contre-exemples. Réfléchissez aux situations auxquelles votre algorithme semble le moins adapté, et cherchez à produire un exemple extrême de ces situations (en gardant des dimensions de données raisonnables), ou si votre algorithme suppose que certaines choses ne puissent pas se produire, essayez de construire explicitement un exemple qui les produise.
Une fois que vous avez généré un contre-exemple potentiel, et de même qu'à chaque fois que vous générez un quelconque exemple, résolvez-le à la main, en vous appliquant. Dans tous les cas, il pourra vous servir plus tard, lors de la phase de tests. Appliquez ensuite votre algorithme sur cet exemple, pour vérifier s'il fonctionne ou non. Pensez d'ailleurs, avant toute chose, à appliquer votre algorithme à la main, sur les exemples que vous aviez déjà créés, avant d'en créer de nouveaux.
Si votre algorithme trouve le bon résultat sur les contre-exemples que vous avez essayé de générer, cela ne prouve pas qu'il fonctionne toujours, mais c'est plutôt bon signe que vous êtes sur la bonne voie, et que cet algorithme vous rapportera des points, même s'il ne fonctionne pas forcément toujours.
Si au contraire vous trouvez un contre-exemple, qui prouve que votre algorithme ne fonctionne pas, c'est une information très utile. D'une part, vous pouvez l'utiliser pour comprendre ce qui fait que votre algorithme ne fonctionne pas, ce qui peut vous aider à le corriger, ou vous donner l'idée d'une meilleure solution. D'autre part, vous pourrez réutiliser ce contre-exemple plus tard, pour évaluer vos nouvelles idées d'algorithmes, et bien sûr, dans la phase de tests.
Pour vous aider à comprendre ce qui fait que votre algorithme ne fonctionne pas sur un contre-exemple donné, essayez de simplifier celui-ci au maximum, en réduisant les données tant qu'il fait échouer votre algorithme. Une fois simplifié, il sera d'autant plus facile de réfléchir à ce qui pose problème.
9) Appliquez la méthode récursivement aux sous-problèmes rencontrés.
Souvent, résoudre un problème nécessite de résoudre plusieurs sous-problèmes, la solution ne s'appliquant pas directement aux données fournies, mais sur les résultats d'un premier calcul devant être fait sur ces problèmes. Lorsque vous rencontrez un tel sous-problème, faites de votre mieux pour l'exprimer clairement, avec ses propres contraintes, et cherchez-en la solution de manière rigoureuse, comme s'il s'agissait d'un problème complet, donc en appliquant de nouveau cette liste de conseils.
10) Calculez la complexité en temps et en mémoire de toutes vos idées.
Lorsque vous avez un algorithme en tête, même si vous savez qu'il est trop lent, prenez l'habitude de calculer sa complexité en temps et en mémoire, pour estimer le temps et la mémoire nécessaires à son exécution, et les contraintes maximales pour lesquelles il peut s'appliquer.
Cette complexité vous permettra de déterminer combien de points cette solution pourrait vous apporter. Elle vous permettra également de vous rendre compte de ce qui manque pour qu'il fonctionne dans les limites, et vous aide à trouver une direction de recherche.
Résumé des étapes de la méthode :
Vous devez avoir cette liste de conseils parfaitement en tête, et l'appliquer de manière systématique. Si vous ne trouvez pas la solution d'un problème, alors que vous n'avez pas appliqué tous ces conseils, vous serez inexcusable.
Lisez bien le sujet, et reformulez-le.
Faites la liste des dimensions du sujet.
Cherchez une bonne représentation visuelle du problème.
Générez des exemples, et résolvez les entièrement à la main.
Exprimez le problème comme une question à laquelle on peut répondre récursivement, et envisagez la solution naïve associée.
Envisagez les algorithmes les plus classiques
Résolvez des versions simplifiées du problème, puis généralisez-les solutions obtenues.
Cherchez des contre-exemples à vos idées d'algorithmes.
Appliquez ces conseils récursivement, sur les sous-problèmes rencontrés.
Calculez la complexité en temps et mémoire de vos solutions.
Une fois toutes ces étapes faites, et seulement là, vous pourrez passer à l'implémentation. Cela ne consiste bien-sûr pas à vous jeter sur le clavier et à commencer à coder, comme nous le verrons dans les conseils correspondants.
Reformuler l'énoncé d'un problème d'algorithmique
Mathias Hiron pour www.france-ioi.org
Introduction : pourquoi reformuler ?
Un problème bien posé est un problème à moitié résolu.
Si l'on prend au mot cet adage bien connu, on peut dire que ce document décrit comment effectuer la première moitié de la résolution d'un problème d'algorithmique.
La plupart des problèmes de ce site sont décrits au sein d'une petite histoire. On vous présente une situation impliquant des personnes où animaux, dans un monde plus ou moins imaginaire avec des règles bien particulières, que vous devez mettre à profit pour vous tirer d'affaire.
L'histoire est en général présentée (parfois volontairement) d'une manière qui cache la vraie nature du problème. Une part significative de la difficulté est donc de comprendre précisément ce que l'on vous demande sans vous laisser embrouiller par tous les détails superflus liés à l'histoire.
Pour avoir une chance de trouver la solution à un problème, il faut s'assurer de l'avoir très clairement en tête. Ceci peut paraître évident, mais l'expérience montre que très souvent, on n'arrive pas à trouver la solution, tout simplement parce-que l'on a mal compris le problème. Pour s'assurer de l'avoir parfaitement compris, il faut bien sûr le relire plusieurs fois, mais le meilleur moyen de est de le reformuler en quelques phrases. Le fait de les écrire vous aide à avoir une idée bien claire et synthétique de ce qu'est le problème, et vous fournit ensuite une base solide pour votre réflexion. Ce document décrit comment rédiger cette description succinte.
L'objectif est de décrire le sujet en ne conservant que ce qui est nécessaire pour pouvoir chercher une solution.
On ne conserve de l'histoire que ce qui aide plus à comprendre que cela nuit à la concision. On pourra garder les noms des objets plutot que de revenir sur des termes génériques comme "point", "case" etc, si cela ne nuit pas à la clarté.
Ecrivez cette description comme si vous expliquiez le sujet à un ami qui n'a pas lu le sujet complet. Vérifiez bien que la description suffit pour réfléchir à une solution, éventuellement en demandant les valeurs des contraintes, séparément.
Cet ensemble de conseils s'applique non seulement sur le problème initial que l'on vous fournit, mais également sur les sous-problèmes ou versions simplifiées, que vous aurez également à résoudre : à chaque fois que vous avez un nouveau problème à résoudre, ré-exprimez le comme décrit dans ce document.
Structure de la description :
La structure d'une reformulation doit généralement prendre la forme suivante :
La description des objets du problème.
Décrivez ce que représentent les données d'entrée, indépendamment du format dans lequel elles sont fournies. Dites par exemple "On vous donne une grille de nombres strictement positifs", ou "On vous donne les coordonnées de rectangles dans le plan, et les coordonnées d'un point de départ.", etc.
Si vous avez repéré certaines caractéristiques de l'entrée, qui permettent d'en avoir une vision simplifiée, n'hésitez pas à y faire appel. Par exemple, plutôt que de dire "On vous donne un ensemble de personnes et des relations entre ces personnes, telles qu'il existe toujours une suite de relations permettant de passer d'une personne à tout autre", dites simplement, "On vous donne un graphe connexe, constitué de personnes et de relations entre ces personnes", voire même simplement "On vous donne un graphe connexe", si le fait qu'un noeud correspond à une personne n'aide pas à la compréhension du sujet.
La description des "règles" qui s'appliquent à ces objets (si nécessaire).
Dans certains sujets, un certain nombre d'actions peuvent être effectuées sur ou relativement aux objets d'entrée. Il peut s'agir de règles de déplacement, d'ajouts ou de suppression d'objets, etc. Lorsque le sujet implique de telles règles, il est important d'en décrire l'essence. Par exemple "A chaque étape, le jeton peut faire un déplacement en cavalier", ou "Vous pouvez placer un bloc uniquement au dessus d'un bloc plus grand.", etc. Cette section doit contenir autant de phrases qu'il y a de règles. On peut cependant omettre certaines choses comme la description précise de ce qu'est un mouvement en cavalier si on la connaît déjà sans hésiter, ou autres détails qui n'influent pas fondamentalement sur la solution.
Ce que l'on vous demande.
Ce point est le plus important, car il constitue le coeur du problème. Les points précédents n'étaient que les pré-requis pour pouvoir exprimer celui-ci simplement.
Pour décrire clairement ce que l'on vous demande, exprimez-le sous la forme d'une ou plusieurs questions. Ces questions commenceront généralement par "Quel est le ... ". Par exemple "Quelle est la longueur du plus court chemin entre l'entrée et la sortie", ou "Quelle est la longueur de la plus longue séquence de somme inférieure à S", etc. Si le sujet demande un ensemble de réponses correspondant à plusieurs éléments de l'entrée, on peut l'exprimer sous la forme : "Pour chaque ..., quel est le ... ?". Par exemple : "Pour chaque intervalle fourni, quelle est la somme des nombres couverts par l'intervalle ?".
Les détails demandés sur la solution.
Souvent, en plus de vous demander une meilleure valeur que l'on peut atteindre, on vous demandera les différentes étapes ou décisions à effectuer pour atteindre cette valeur. Le fait de le demander n'influence relativement que peu l'algorithme et ne doit pas être mentionné dans la question principale, mais il faut malgré tout le rappeler. On pourra ajouter sous la/les questions, une simple phrase du style "Afficher la direction empruntée à chaque étape".
Ce que l'on omet dans la description :
Les valeurs des contraintes.
Celles-ci sont primordiales pour chercher une solution efficace, mais ne sont pas nécessaires à la compréhension du problème lui-même. On les mettra donc dans une autre section, la "liste des dimensions".
La description des formats d'entrée et de sortie, ou d'une éventuelle API.
Les détails dont on est absolument certain qu'ils ne changent pas l'algorithme lui-même.
Conclusion
Une fois que vous avez terminé la rédaction de ces différentes parties, relisez-le en vérifiant que si l'on ne vous avait donné que cette description, vous auriez suffisamment d'éléments pour résoudre le problème. Si ce n'est pas le cas, c'est que la description est incomplète.
Relisez ensuite une dernière fois le sujet, pour bien vérifier que rien d'important ne manque à votre description.
Dans la suite de la réflexion, vous reviendrez régulièrement sur cette description, assurez-vous donc qu'elle soit bien évidence et parfaitement lisible sur votre feuille, quitte à la ré-écrire entièrement si elle contient trop de ratures.