Arthur Charguéraud et Mathias Hiron pour www.france-ioi.org
Les olympiades se composent de deux épreuves, à deux jours d'intervalle. Chaque épreuve, d'une durée de 5 heures, est composée de 3 problèmes. Différents types de problèmes peuvent être proposés, tous de nature algorithmique. On distingue trois types d'exercices :
Détaillons chacun de ces trois cas.
1. Sujet évaluation sur une série de test. Le source de votre programme est compilé, puis l'exécutable généré est soumis à une série de tests, en général une vingtaine. Chaque test doit être exécuté en un temps limité avec une mémoire limitée, et sans erreur fatale ; les limites sont précisées pour chaque sujet. Les premiers tests sont là pour vérifier que le programme fonctionne, mais on passe très rapidement à des fichiers de test immenses, dont le but est de vérifier les performances de votre algorithme. Chaque test correctement résolu donne un certain nombre de points (en général 5 points pour chacun des 20 tests), le but est donc de résoudre un maximum de tests (pour obtenir 100 points sur 100).
2. Sujet interactif. Le source de votre programme est compilé avec la bibliothèque fournie, et votre programme est lancé plusieurs fois, toujours avec les limites de temps et de mémoire données dans le sujet. La bibliothèque calcule votre score pour chacune des exécutions, et ne vous donne aucun point si votre programme ne termine pas correctement. La bibliothèque sert à interagir avec votre programme, par exemple en incarnant l'adversaire dans un jeu à deux joueurs, ou bien à limiter les données disponibles, par exemple pour des problèmes où l'on ne peut trier des entiers qu'en les comparant deux à deux sans accéder à leur valeur.
3. Sujet avec sortie uniquement. Cette fois le problème est sensiblement différent : on vous donne un sujet et des fichiers d'entrées, et on vous demande de soumettre directement les fichiers de sortie. Il n'est pas demandé de soumettre le source ni l'exécutable de votre programme, ce qui fait que vous pouvez même résoudre certains tests à la main ! Pour ces sujets, il n'y a pas de contrainte de temps autre que la durée de l'épreuve, ni de contrainte de mémoire autre que la limitation de la machine qui se trouve devant vous.
Remarque générale : la plupart du temps, on vous demande de fournir un résultat exact, qui doit correspondre mot pour mot à la sortie attendu pour obtenir les points. Dans certains cas cependant, le sujet accorde un score partiel pour des réponses proches de la réponse idéale. Parfois certains problèmes sont tellement difficiles que les points sont attribués en fonction du score du meilleur candidat, qui obtient la totalité des points.
Aux IOI, les langages autorisés sont : C, C++, et Pascal.
Les compilateurs associés sont gcc, g++ et Free Pascal (tous libres). Pour connaître les versions exactes, reportez-vous au site des IOI à venir.
Si vous êtes motivé par les IOI mais que vous ne connaissez que Caml, sachez que vous pouvez apprendre en un temps tout à fait raisonnable à coder vos algorithmes en C++. En effet, apprendre un second langage de programmation est incomparablement plus rapide qu'apprendre le premier.
Les PC fournis aux olympiades sont tous sous Linux. Si vous travaillez sous Linux vous n'aurez aucun problème. Si vous utilisez une autre plateforme, vous pouvez apprendre tout ce qu'il faut savoir pour les IOI en moins de 2 heures.
Lors des olympiades, vous n'aurez pas forcément à votre disposition vos outils de développement habituels. Pensez donc à vous renseigner sur les outils disponibles lors des prochaines olympiades, choisissez ceux que vous préférez utiliser, et utilisez-les régulièrement pour vous y habituer.
Dans le même ordre d'idées, vous n'aurez pas le droit d'apporter le fichier de configuration de votre éditeur préféré. Si vous ne pouvez pas être à l'aise avec Vim ou Emacs sans votre conf perso de 5 pages, essayez un éditeur graphique configurable rapidement (Kate pour ne citer que lui).
Là encore, pour connaître les distributions et les versions des logiciels disponibles, reportez-vous au site des IOI à venir.
Aux IOI, des claviers US sont fournis, et vous n'aurez donc pas votre habituel clavier français. Cela peut beaucoup vous gêner, être une source d'erreurs, et surtout de perte de temps et de concentration. Trois solutions s'offrent à vous :
Commentaires sur chacune des solutions :
Techniquement, pour émuler un clavier on utilise :
setxkbmap us
et setxkbmap fr
,