ACM-ICPC

Présentation

Il s’agit d’un concours d’origine américaine destiné aux étudiants post-bac, découpé en deux épreuves. Les demi-finales régionales font un premier tri entre les candidats. Les 70 meilleurs s’affrontent ensuite lors d’une finale mondiale.

L’épreuve régionale à laquelle participe la France, abrégée en SWERC, se déroule sur le campus de l’École Polytechnique à la fin novembre. Les finales ont généralement lieu en avril, chaque année dans un pays différent.

Le nombre d’équipes sélectionnées pour la finale par chaque région varie beaucoup. Notamment, de nombreuses universités américaines participent d’emblée à la finale, tandis que l’Europe de l’Ouest ne peut envoyer que deux ou trois équipes.

Participation de l’ÉNS Lyon

L’ÉNS Lyon a participé pour la première fois à ce concours en 2004 en envoyant deux équipes, dont une a aussitôt remporté la première place des demi-finales.

L’équipe encadrée par Nicolas Schabanel et constituée d’Arthur Charguéraud, d’Alexandre Buisse, et de moi-même s’est donc vue invitée à la finale en Chine, à Shanghai. Sous prétexte que nous n’étions pas dans la moitié supérieure du classement, les juges des ACM ont refusé de donner notre rang ; il n’en reste que nous sommes plutôt satisfaits pour une première participation. J’ai profité de l’occasion pour écrire une chronique du voyage et rassembler les photos prises par Alexandre et Nicolas.

Préparation au concours
Le module d’algorithmique effective de l’ÉNS Lyon

Nicolas Schabanel dispense un cours d’algorithme effective pour préparer au concours des ACM. Il s’agit de s’entraîner à résoudre des problèmes algorithmiques relativement simples (dans le sens où trouver la solution ne nécessite pas des algorithmes aussi compliqués que dans certains papiers de recherche) et de les programmer effectivement sur machine (autre raison pour laquelle les problèmes ne sont pas d’une difficulté trop soutenue).

Détails techniques, folklore

Chaque concours se compose d’une unique épreuve de cinq heures, pendant laquelle les candidats ont à résoudre une dizaine de problèmes. Les problèmes traitent chacun d’un sujet algorithmique différent, que les candidats doivent non seulement résoudre de manière théorique (trouver un algorithme suffisamment rapide qui répond au problème), mais aussi le programmer effectivement sur un ordinateur.

Le code source des problèmes résolu est envoyé aux juges, qui le compilent et le font tourner sur de nombreux tests d’entrée pour vérifier que le programme est bon et l’algorithme correct. En cas d’erreur (bug ou erreur théorique dans l’algorithme), l’équipe n’a aucun détail : elle sait juste si le programme a fait un timeout (algorithme trop lent) ou bien a renvoyé une mauvaise réponse (algorithme faux). Il est donc vital de faire bien du premier coup, car en cas d’erreur on n’a aucun indice sur l’origine du problème.

Les équipes sont évaluées selon le nombre de problèmes résolus, et en cas d’égalité sur le temps mis pour résoudre ces problèmes. Chaque soumission erronée donne lieu à une pénalité de 20 minutes. Le temps est comptabilisé par cumul : à chaque fois qu’un problème est résolu, on ajoute au temps total la durée séparant le début de l’épreuve de l’envoi de la solution correcte, ainsi que la somme des pénalités pour ce problème. Par exemple, si la compétition commence à 12h, qu’un problème est résolu à 13h30 et un autre à 15h, et que deux soumissions erronées ont été faites, le temps total est de 1h30 + 3h + 2 × 0h20 = 5h10.

En termes de stratégie, il est donc préférable de commencer par les problèmes les plus faciles afin de minimiser le temps total. Noter qu’une soumission erronée pour un problème finalement non résolu n’est pas comptabilisée : à la fin de l’épreuve, on a donc tout intérêt à effectuer le plus de soumission possible, car cela ne peut que permet d’obtenir un nouveau problème résolu et n’augmente pas le temps total dans le cas contraire.

Chaque équipe peut comporter au plus trois candidats, mais ne dispose que d’un seul ordinateur. Il faut donc se répartir les tâches pour travailler efficacement : lecture des sujets, résolution du problème algorithmique, codage effectif, test, débogage éventuel.

Les résultats de chaque équipe sont disponibles en temps réel lors de la compétition : d’une part un écran géant affiche le classement provisoire, d’autre part à chaque fois qu’une équipe résout un problème, les organisateurs accrochent un ballon gonflé à l’hélium à côté de son poste de travail (voir photo), dont la couleur correspond au problème résolu. Ainsi, il est possible de voir d’un coup d’œil les problèmes que les autres équipes parviennent à résoudre facilement.

Ballons indiquant les problèmes résolus par chaque équipe. On aperçoit au fond l’écran géant affichant les résultats provisoires en temps réel.