FLASH INFORMATIQUE FI



public avertiLa Suisse a trouvé ses meilleurs programmeurs


Le 13 mars, l’EPFL a accueilli quarante étudiants de la toute la Suisse qui se sont livrés une bataille intellectuelle captivante. PolyProg  a su défier les quinze équipes avec neuf problèmes algorithmiques pendant cette première édition de l’HC 2 . À l’issue des cinq heures de concours, la Suisse a connu ses premiers champions de programmation. Une équipe de l’ETHZ a remporté la victoire, suivie d’une équipe de l’EPFL.



On March 13th, EPFL welcomed forty students from all over Switzerland to an exciting brain battle. PolyProg  challenged the fifteen teams with nine algorithmic problems at this first edition of the HC 2. After five hours of competition, Switzerland identified its first champions in programming. The contest was won by a team from ETHZ, followed by a team from EPFL.


Christian KAUTH


L’initiative de l’Helvetic Coding Contest est née à une altitude de 10’000m quelque part dans le ciel entre Madrid et Genève. Les membres de PolyProg   venaient de gagner l’argent et le bronze au SWERC   lorsqu’ils décidèrent de mettre sur pied un concours d’algorithmique au niveau Suisse. En effet, chaque année plusieurs équipes suisses se retrouvent et s’affrontent au SWERC, sans pour autant disposer de leur propre événement au niveau national.

PolyProg, soutenue par Brocade , était là pour relever le défi et faire de l’ HC 2 le concours de référence en Suisse, tant en empruntant les éléments forts du SWERC qu’en levant les barrières qui limitent la participation à ce genre de concours.
Ainsi, s’il est vrai que l’idée d’une équipe de trois cerveaux se partageant un seul ordinateur provient du système SWERC, le HC2 ne se restreint pas aux seuls étudiants universitaires mais est ouvert tout aussi bien aux gymnasiens qu’aux doctorants. Bien évidemment, cela requiert une préparation spécifique et soignée, et si ces jeunes ont pu profiter de ce contact précoce avec des programmeurs confirmés, c’est parce que PolyProg a su agencer un ensemble de problèmes algorithmiques sur lequel les experts ont pu se casser les dents tandis que les novices appréciaient la diversité des problèmes et résolvaient les moins compliqués.
La diversité était le mot-clef de ce concours, qui d’une part laissait le choix du langage (Java, C ou C++) et d’autre part incorporait à la fois des problèmes validés par un juge automatique contre un ensemble de fichiers de test Mooshak  - modifié pour les besoins du concours), des problèmes interactifs où le code des participants communiquait directement avec le juge, et enfin des problèmes dits offline, c’est-à-dire des problèmes pour lesquels les participants avaient entièrement accès aux entrées et devaient soumettre uniquement leurs solutions, pas le ou les programmes qui leur avaient permis d’y arriver. Chaque problème était évalué avec dix fichiers de test différents avec un degré de difficulté croissante. Combiné avec un système de classement à points partiels, cela a permis de donner aux solutions un pourcentage adapté de la note maximale, en fonction de leur complexité. Ainsi, un problème requérant la mise en oeuvre de la programmation dynamique pour obtenir 100% de la note pouvait être résolu avec une approche Brute Force   dans environ 40% des cas, car la simplicité des premiers tests permettait d’obtenir la solution en essayant simplement toutes les combinaisons. Le but de ce système était de récompenser avant tout la justesse de la solution, puis l’efficacité de l’algorithme.
Chaque problème s’ouvre avec une courte histoire qui décrit une aventure d’Heidi, the Coding Cow (la mascotte de l’HC 2). Le chemin qui mène le concurrent de l’histoire vers l’idée d’un algorithme correct et plus ou moins performant, puis finalement vers une implémentation sans faute n’est jamais trivial et rend le concours très intéressant :

Derrière une planification de dates de présentations se cachait un graphe biparti sur lequel il fallait déterminer une couverture minimale de noeuds. Une descente à ski autour des marmottes demandait une recherche exhaustive améliorée par des optimisations subtiles afin d’obtenir la note maximale. La distribution de fondue aux marmottes avait une solution greedy . L’exploration de la Suisse selon des règles particulières était décomposable en sous-problèmes que l’on pouvait résoudre avec le concept de programmation dynamique. Une stratégie min-max devait être implémentée pour aider Heidi à gagner un jeu dont la récompense est du délicieux chocolat suisse. Au moyen d’une solution très simple, bien que fastidieuse à implémenter, les concurrents devaient aider Heidi à prendre des photos avec un appareil argentique. Libre cours fut ensuite laissé à la fantaisie des participants pour décrypter un livre d’histoires secrètes. Finalement, les participants devaient aider Heidi à choisir le meilleur coéquipier pour l’édition 2011 du HC 2, grâce à des concepts probabilistes (le fameux problème du secrétaire).

Si dans cette multitude de concepts, vous n’avez pas trouvé votre favori, le problème suivant le renferme certainement :
Pour des boissons rafraichissantes, Heidi veut créer des glaçons pyramidaux de quatre faces triangulaires. Ces glaçons doivent être d’un volume donné et de surface minimale afin de ralentir leur fonte au maximum. Si on vous donnait la longueur des trois côtés d’une de ces faces, ainsi que le volume désiré, est-ce que vous sauriez trouver la surface minimale de la pyramide ? Il y a une multitude d’approches différentes à ce problème et il se peut que la suite ne mentionne même pas la vôtre.

Par sa formulation, il s’agit d’un problème de minimisation sous contrainte qui peut effectivement être résolu par des méthodes d’optimisation telles que Newton contraint, la méthode des points intérieurs, celle du lagrangien augmenté, voir de la programmation quadratique séquentielle. Ces méthodes ont cependant le défaut d’être d’une telle généralité qu’il n’est pas évident de les mettre en oeuvre dans le cadre d’un concours de cinq heures qui comporte huit autres problèmes. Ce problème mérite certainement une inspection plus détaillée.
Des résultats bien connus depuis le gymnase comme le théorème d’Al-Kashi et la formule du volume de pyramides (un tiers fois la base fois la hauteur) permettent déjà de déduire la hauteur de la pyramide.
Reste à déterminer la projection de ce point sur la face décrite dans l’énoncé. Ce sous-problème en deux dimensions se résout très bien par des méthodes de descente et les fichiers de test ont été construits de sorte que la recherche ternaire aboutisse pour sa part à une note de 70%.
Les participants se voient alors confrontés au dilemme suivant : vaut-il mieux coder une des méthodes mentionnées ci-dessus ou trouveraient-ils peut-être encore d’autres astuces qui rendent le problème plus facile  ? Une excellente idée est toujours de faire du reverse-engineering sur les quelques exemples d’entrée-sortie qui sont fournis avec le problème et qui sont utiles pour tester la justesse du code (condition nécessaire, mais non suffisante).
Quelques minutes de réflexion mènent à l’intuition que cette projection de la crête sur la base pourrait être le centre du cercle inscrit de la base. Alternativement la méthode des multiplicateurs de Lagrange, avec comme système de variables les distances entre la projection de la pointe et les côtés de la base, prouve cette hypothèse analytiquement. Que ce soit dans la certitude, ou dans l’espoir que l’intuition ne trompe pas, il ne reste plus qu’à trouver le centre du cercle inscrit à un triangle, qui se situe à l’intersection des bissectrices du triangle. Cette intersection peut être trouvée soit par une construction géométrique, soit par de la recherche binaire en testant des droites de différents angles qui devront êtres ou bien doublés ou bien dédoublés en fonction du rapport des deux angles résultants. De manière équivalente, mais plus élégante, on peut observer que le rayon du cercle inscrit est égal au rapport entre l’aire et le demi-périmètre du triangle. Il ne reste alors plus qu’à calculer la surface totale de la pyramide ou bien par le théorème de Pythagore ou bien par la formule d’Héron.

Cette explication se devait très exhaustive pour vous faire un petit tour d’horizon de la créativité qui peut entrer en jeu dans un concours d’algorithmique. Pour terminer, nous aimerions vous étonner avec la simplicité de la solution (en C) d’une équipe de l’EPFL qui a fini en sixième position :

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int main(void)
{
 double a, b, c;        // les 3 côtés de la base
 double v;        // le volume désiré
 double S;        // la surface de la base               
 double p;        // le demi-périmètre de la base
 double r;        // le rayon du cercle inscrit à la base
 double h;        // la hauteur de la pyramide
 double A;        // la surface totale des 4 faces

 scanf("%lf %lf %lf %lf", &a, &b, &c, &v);

 p = (a+b+c)/2;                               
 S = sqrt(p*(p-a)*(p-b)*(p-c));
 r = S / p;
 h = 3*v / S;
 A = S + sqrt(h*h + r*r) * p;
   
 printf("%lf\n", A);
         return 0;
}

Comme dit précédemment, chaque équipe disposait d’un ordinateur pendant le concours. Ces machines ont été mises à disposition par le service informatique de la faculté IC et nous tenons à le remercier. Toutefois, les organisateurs ont dû relever le défi de les configurer pour le concours sans pour autant pouvoir toucher les logiciels déjà installés sur ces machines.

Pour arriver à ce but, un système live a été développé. Il démarre depuis une clé USB et réside complètement dans la mémoire vive, sans toucher au disque dur. Il permet d’avoir un système taillé pour les besoins du concours : un choix riche d’éditeurs et d’environnements de programmation, des compilateurs, débogueurs et outils a été installé. De plus, l’accès au réseau a été limité par un firewall afin de restreindre la navigation aux seuls sites Web autorisés. Enfin, un système de surveillance par réseau a permis d’effectuer des sauvegardes régulières et d’offrir un service d’impression de code aux participants.

C’est ainsi toute une constellation de défis techniques qu’a dû affronter le comité PolyProg lors de l’organisation d’un concours qui a su, au final, relever les attentes des participants en leur offrant une ambiance compétitive, mais très conviviale.

Nous espérons vous accueillir dès l’année prochaine avec un nouveau concours !

Que vous soyez intéressés à nous rejoindre pour l’organisation de l’Helvetic Coding Contest 2011 ou à prendre part aux activités organisées par PolyProg, une seule adresse : polyprog@epfl.ch.

Le comité sera ravi de vous répondre dans les plus brefs délais !



Glossaire

Brocade
Brocade Communication Systems, Inc..
Brute Force
approche exhaustive des problèmes : la solution est trouvée en testant tous les cas possibles jusqu’à la découverte de la solution.
Greedy
algorithme glouton qui suit le principe de faire, étape par étape, un choix optimum local, dans l’espoir d’obtenir un résultat optimum global.
HC2
Helvetic Coding Contest
PolyProg
association du campus qui promeut les compétences en algorithmique des étudiants et doctorants
SWERC
qualification régionale pour l’Europe du sud-ouest au prestigieux ACM ICPC (International Collegiate Programming Contest).


Cherchez ...

- dans tous les Flash informatique
(entre 1986 et 2001: seulement sur les titres et auteurs)
- par mot-clé

Avertissement

Cette page est un article d'une publication de l'EPFL.
Le contenu et certains liens ne sont peut-être plus d'actualité.

Responsabilité

Les articles n'engagent que leurs auteurs, sauf ceux qui concernent de façon évidente des prestations officielles (sous la responsabilité du DIT ou d'autres entités). Toute reproduction, même partielle, n'est autorisée qu'avec l'accord de la rédaction et des auteurs.


Archives sur clé USB

Le Flash informatique ne paraîtra plus. Le dernier numéro est daté de décembre 2013.

Taguage des articles

Depuis 2010, pour aider le lecteur, les articles sont taggués:
  •   tout public
    que vous soyiez utilisateur occasionnel du PC familial, ou bien simplement propriétaire d'un iPhone, lisez l'article marqué tout public, vous y apprendrez plein de choses qui vous permettront de mieux appréhender ces technologies qui envahissent votre quotidien
  •   public averti
    l'article parle de concepts techniques, mais à la portée de toute personne intéressée par les dessous des nouvelles technologies
  •   expert
    le sujet abordé n'intéresse que peu de lecteurs, mais ceux-là seront ravis d'approfondir un thème, d'en savoir plus sur un nouveau langage.