FLASH INFORMATIQUE FI



Médaille au SWERC = justesse x efficacité


Entraînée et sélectionnée par PolyProg  , la délégation EPFL aux finales régionales de l’ACM ICPC  , concours d’algorithmique par excellence au niveau universitaire, a décroché une médaille de bronze. La combinaison d’analyses profondes, d’idées originales, d’implémentations efficaces, tout comme une coordination d’équipes impeccable est la clé du succès dans ce concours.



Trained and selected by PolyProg  , the EPFL delegation to the regional ACM ICPC   finals, won a bronze medal. The combination of profound analyses, splendid ideas and efficient implementations along with perfect team coordination is the key to success in this probably most prestigious programming contest for universities.


Christian KAUTH




Cinq équipes, composées chacune de trois étudiants EPFL, se sont affrontées lors du concours de sélection local organisé par PolyProg. Un ensemble de huit problèmes algorithmiques variés permettait de trouver les deux équipes les plus prospères. Le prix fut un voyage sponsorisé par PolyProg aux finales régionales de l’ICPC, le SWERC. Les délégations des universités de Suisse, France, Italie, Espagne, Portugal et Israël se donnèrent rendez-vous à Madrid pour déterminer la meilleure d’entre elles, qui représentera la région sud-ouest européenne aux finales mondiales à Charm el-Cheikh (Egypte) cet hiver. L’équipe de l’ETHZ a su réaliser ce grand exploit. La formation et les entraînements avec des équipes de St Petersburg, desquels aussi les membres de PolyProg ont pu grandement bénéficier, ont vraisemblablement porté leurs fruits. Nos sincères félicitations  !
Les cinq heures de concours demandent une énorme concentration et une excellente organisation d’équipe. Il s’agit effectivement de résoudre le plus grand nombre de problèmes le plus rapidement possible et des tentatives erronées se voient accompagnées d’une pénalité. Avec seulement un ordinateur à disposition par équipe, chaque seconde devant le clavier compte et les conflits d’accès entre les coéquipiers doivent être résolus de manière intelligente. Les problèmes étaient particulièrement ardus pour cette édition 2010 et il a fallu surmonter plusieurs niveaux de difficulté : seuls des algorithmes justes et efficaces implémentés sans la moindre faute ont pu résoudre tous les tests et marquer des points.

En guise d’exemple, une brève réflexion sur un des problèmes mena à la conclusion qu’il fallait vérifier si deux matrices (A et B) sont l’une le carré de l’autre (A2=B ?). Si un premier réflexe est de calculer le carré de la matrice A en complexité O(N3), puis de comparer le résultat A2 avec B en O(N2), cette solution est trop lente, vu la taille des matrices. Plutôt que de calculer le carré, il aurait fallu comparer le produit de la matrice par un vecteur (A*A*v=B*v ?). Ceci peut se faire en complexité O(N2). Si les deux résultats sont différents, alors B n’est définitivement pas le carré de A. En revanche, un résultat identique n’implique pas forcément A2=B. Mais si l’identité persiste pour un certain nombre de vecteurs choisis de manière aléatoire, alors il y a des fortes chances que B soit effectivement le carré de A. Une démonstration mathématique rigoureuse donne le nombre minimal de vecteurs à tester qui s’avère étonnamment petit !

Les autres problèmes cachaient des flux maximaux, de la 2-satisfaisabilité avec ses composantes fortement connexes, de la recherche de cycles, de la programmation dynamique, des graphes et une résolution d’équations linéaires qui devait se résoudre avec de la géométrie pour contourner les problèmes de dégénérescence.
Pour vous donner une idée très concrète des casse-têtes auxquels les étudiants ont dû faire face, je vous guide à travers ce problème qui a été résolu par six des 38 équipes.

Vous êtes à la poursuite d’un singe qui se cache dans une forêt à N (1≤N≤21) arbres. Vous n’avez pas la moindre idée dans lequel de ces arbres il se cache, mais si vous tirez avec votre fusil surdimensionné sur l’arbre derrière lequel se cache le singe, vous ne pouvez pas le manquer. Si par contre vous vous êtes trompé d’arbre, il profitera du fait que vous devez recharger votre fusil et sautera vers un arbre voisin sans que vous ne vous en aperceviez (le singe a tellement peur qu’il ne restera jamais sur l’arbre actuel). Si on vous donne la description de la forêt (M relations de voisinage entre arbres), est-ce que vous sauriez trouver la suite d’arbres sur lesquels vous devriez tirer pour être sûr d’arrêter le singe ?
Pour économiser la munition, cette suite, si elle existe, doit être aussi courte que possible et permettre d’arrêter le singe indépendamment de sa position de départ et de la suite des sauts qu’il décide d’entreprendre.


Solution

Pour chaque arbre, il est soit possible soit impossible que le singe se cache dedans. Associons à chaque bit (d’un nombre à N bits) un arbre différent. Chaque bit i aura comme valeur 1 si le singe peut potentiellement se cacher dans l’arbre i et 0 sinon. Ainsi les positions possibles du singe à chaque instant se laissent encoder dans un nombre inférieur à 2N. 2 N-1 est la constellation de départ (le singe peut se trouver dans n’importe quel arbre), et 0 sera la constellation finale (on aura fusillé le singe), si accessible. La transition d’une constellation current à une autre next se fait en deux étapes.

  1. D’abord on laisse sauter le singe : pour toute connexion d’un arbre A vers un arbre B, si dans la constellation actuelle, le singe peut être dans l’arbre A, alors dans la constellation suivante, il peut être dans l’arbre B. Ceci se traduit dans le code C++ suivant qui utilise du bitmasking.
    for (int i=0; i<M; i++)
            if (current & 1<<A[i])
                    next |= 1<<B[i];
  2. 2 Ensuite on tire dans un arbre i, donc le singe ne peut plus y être

    if (next & (1<<i))
            next -= (1<<i)

Nous avons maintenant une constellation de départ (2 N-1), un objectif d’arrivée (0) et une fonction de transition. Il suffit maintenant d’ajouter toutes les nouvelles constellations dans une queue d’attente et de traiter les éléments de cette queue de manière FIFO. Techniquement parlant, on fait un BFS. Si la constellation 0 est atteinte, nous avons réalisé une suite minimale de tirs pour fusiller le singe. Si d’autre part la queue se vide avant que le 0 n’apparaisse, le singe a toujours un chemin de fuite (par exemple dans le cas d’un graphe cyclique).
Il ne reste alors plus qu’à retrouver la suite des tirs qui nous a amenée de la constellation de départ à la constellation finale.
À cette fin, nous mémorisons pour chaque constellation C la constellation C’ depuis laquelle nous avons fait la transition C’-C tout comme le tir qui correspond à la transition.

dad[next] = current;
shot[next] = i;

Cette petite indication nous permet de restituer la suite totale

while (constellation != (1<<N)-1) {
        cout<<shot[constellation];
        constellation = dad[constellation];
}

Notez que ce code imprime la suite dans l’ordre inverse.

Si ce petit amuse-gueule vous a ouvert l’appétit, n’hésitez pas à passer au buffet complet. Les problèmes du SWERC tout comme ceux des autres concours organisés par PolyProg sont accessibles à travers notre site Web et notre moodle. Vous y trouvez aussi le code source complet de ce problème.
Que vous soyez étudiant ou doctorant, profitez de nos séminaires pour vous mettre en forme pour la seconde édition de l’HC2 & , l’équivalent suisse au concours européen, qui se tiendra le 12 mars 2011 sur le campus de l’EPFL, organisé par PolyProg et sponsorisé par Open Systems.



Glossaire

ACM ICPC (International Collegiate Programming Contest) :
cm.baylor.edu/welcome.icpc.
BFS (Breadth-First-Search) :
parcours en largeur.
Bitmasking :
un masque utilisé pour manipuler des nombres bit par bit en parallèle.
FIFO :
(First In First Out)
HC2 (Helvetic Coding Contest) :
Inscriptions sous www.hc2.ch/
PolyProg :
association du campus qui promeut les compétences en algorithmique des étudiants et doctorants, polyprog.epfl.ch.
ACM ICPC (International Collegiate Programming Contest) :
cm.baylor.edu/welcome.icpc.
PolyProg moodle :
moodle.epfl.ch/course/view.php ?id=8471, avec SayHello comme key.
SWERC (Southwestern Europe Regional Contest) :
swerc.eu/


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.