rached-innov: Olympiades Internationales Informatique

vendredi 12 août 2011

Olympiades Internationales Informatique

Les Olympiades Internationales Informatique (IOI) sont une compétition d'algorithmique et de programmation destinée aux collégiens et lycéens du monde entier. Chacun des 80 pays participants sélectionne quatre élèves et les envoie pour se mesurer aux autres candidats durant deux épreuves de programmation d'une durée de 5 heures.

Cette année, les Olympiades se sont déroulées en Thaïlande (Pattaya City), du 22 au 29 juillet, et ont accueilli plus de 300 participants du monde entier. ...

Le déroulement des Olympiades

La compétition, qui s'est déroulée il y a deux semaines en Thaïlande (du 22 au 29 juillet), comprenait deux jours de compétition et deux jours de visite. Elle a été l'occasion pour les participants de découvrir une nouvelle contrée, de rencontrer plein de jeunes passionnés d'informatique, et de travailler sur divers problèmes de nature algorithmique.

Chaque épreuve se compose de 3 problèmes à résoudre en 5 heures. La solution traduite en langage machine est évaluée instantanément par un serveur qui affiche le nombre de points obtenus sur l'exercice qui dépend de deux critères (à supposer que l'algorithme fonctionne, sinon le score obtenu est nul) : le temps que prend l'algorithme pour fournir le résultat, et la quantité de mémoire vive que celui-ci utilise, respectivement appelés complexité en temps et en espace de l'algorithme. Ainsi, le sujet annonce plusieurs paliers de points, chaque palier correspondant généralement à un type d'algorithme ; les points du premier palier étant très faciles à obtenir, et les points du dernier étant réservés aux candidats les plus assidus (les sujets sont accessibles sur le site des IOI).

Chaque problème se base sur une situation plus ou moins réaliste de la vie quotidienne, par exemple :

Vous devez envoyer un message en confiant de petites quantités d'information à des perroquets mais vous ne savez pas dans quel ordre ils vont arriver et il faudra pourtant reconstruire le message original ! La difficulté vient des contraintes très strictes sur la quantité d'information que chaque perroquet peut porter et sur le nombre maximum de perroquets que vous pouvez employer. Il s'agit donc d'encoder efficacement un message pour être invariant aux permutations.
Vous êtes perdu dans un labyrinthe comportant 100 000 pièces mais dont vous connaissez le plan. Les chemins entre deux pièces sont de longueurs variables et prennent donc plus ou moins de temps pour être parcourus. La difficulté est que le gardien du labyrinthe peut à tout instant bloquer un et un seul des chemins reliant deux pièces et ainsi vous empêcher d'aller dans la bonne direction. Sachant que le gardien va tout faire pour vous retarder le plus possible vous devez calculer le temps minimum qu'il vous faudra pour vous échapper.
Des éléphants sont alignés sur une ligne et vous souhaitez les prendre en photo. Sachant que votre appareil ne peut prendre en photo que M mètres de la ligne en même temps, combien de photos seront nécessaires ? On a jusque 150 000 éléphants et en plus on peut avoir jusqu'à 150 000 changements (un éléphant change de position) et on doit après chacun de ces changement calculer le nombre de photos nécessaires.

En guise de récompense, les meilleurs du classement se voient recevoir des médailles : or pour les candidats faisant partie du premier douzième du classement, argent pour ceux du premier quart, et bronze pour ceux du premier demi. La moitié des participants sont donc récompensés.

Et les gagnants sont...

Du côté de la Belgique, Benoît est arrivé 98^ème, et a donc remporté une médaille de bronze, première médaille pour la Belgique depuis 1992.
Du côté de la France, Paul a terminé 9^ème et a donc gagné une médaille d'or (la deuxième pour la France depuis qu'elle participe aux IOI), et Jules a fini 112^ème, ce qui lui a permis d'avoir une médaille de bronze.
Le gagnant général est Gennady, un Biélorusse, qui a fini avec 600 points.

Le classement précis se situe à cette adresse.