FLASH INFORMATIQUE FI



Un penseur, un fignoleur et un programmeur...




Christian KAUTH


... se donnent rendez-vous pour la seconde édition de l’Helvetic Coding Contest HC2 qui se déroulera ce 12 mars à l’EPFL !

Vu le grand succès de la première édition,    PolyProg a décidé de mettre les bouchées doubles pour vous offrir un HC2 2011 exceptionnel !
Vos cellules grises trouveront leur compte pendant ces cinq heures de concours. Avec vos deux coéquipiers, votre équipe disposera de quinze heures de réflexion (trois cerveaux qui turbinent en parallèle pendant cinq heures) pour imaginer des solutions aux huit problèmes algorithmiques proposés. Les occasions pour démontrer votre créativité et vos capacités de réflexion pluridisciplinaire ne vont pas manquer et vous amèneront à des solutions originales et stupéfiantes. Il s’agira ensuite de les traduire en des petits programmes en C, C++ ou Java. Si les meilleures équipes se battent sur des solutions hautement avancées et visent un score parfait, la fascination pour les casse-têtes tout comme une pensée logique et originale sont suffisantes pour participer. En effet, pour chaque problème, un juge automatique compile et exécute vos programmes et vérifie qu’ils produisent des résultats corrects dans les limites de temps et de mémoire. Ces contraintes se serrent au fur et à mesure des tests et assureront que seuls des algorithmes bien pensés parviennent aux 100%, les autres s’arrêtant entre 30% et 80% des points. Cette stratégie de correction vous permettra de tenter votre chance et de vous amuser à résoudre tous les problèmes, quel que soit votre niveau. L’HC2 2011 rassemblera des étudiants bachelor, master, des doctorants et même quelques gymnasiens intrépides venant des quatre coins de la Suisse. Pour vous mettre dans l’ambiance, voici l’un des casse-têtes de l’Helvetic Coding Contest 2010.
Heidi, la vache mascotte de l’événement, organise un banquet de fondue pour célébrer la fin d’hibernation de toutes les marmottes en Suisse. Les emplacements de ces dîners peuvent être modélisés par des points équidistants le long d’une ligne. Toute planification étant soumise aux caprices du hasard, Heidi connaissait certes le nombre total d’invités, mais a dû estimer à son mieux l’emplacement qui sera choisi par chacune des marmottes. Si certains villages sont abondants en fondue, il en manque à d’autres et il faudra recourir à une redistribution des portions. Heidi priera simplement quelques marmottes de changer de village tout en garantissant que la distance cumulative parcourue par l’ensemble des marmottes pour ce réarrangement sera minimisée. Si la distance entre deux villages voisins vaut un, combien vaut alors la distance minimale de parcours pour que chaque marmotte trouve sa fondue ? Il y a pour les tests les plus durs jusqu’à 100’000 emplacements dont la différence absolue par village entre le nombre de marmottes et celui des portions de fondue peut atteindre 1000. Votre satisfaction sera maximale si vous essayez de trouver la  solution par vous-même avant de la vérifier dans le glossaire. Et pourquoi pas l’implémenter et la tester sur les quelques tests proposés sur le site de l’édition 2010   ? Vous y trouverez aussi les autres problèmes accompagnés des idées aux solutions.
Composez votre équipe du tonnerre et relevez le défi ! Si ce n’est pas un prix (pour les cinq meilleures équipes), votre t-shirt HC2vous restera comme souvenir de cette journée hors du commun. Inscrivez-vous d’ores et déjà sur hc2.ch. Il va de soi que l’organisation d’un événement d’une telle ampleur repose sur un considérable soutien logistique et financier. À ce propos, nous adressons nos chaleureux remerciements à l’EPFL qui fournit l’infrastructure et à Open Systems  qui a fait confiance à PolyProg pour l’organisation de HC2 2011 et parraine généreusement l’initiative.



Glossaire

HC2 Helvetic Coding Contest :
inscriptions sous www.hc2.ch
PolyProg :
association du campus qui représente l’EPFL à des concours de programmation internationaux et fondatrice de l’HC2.polyprog.epfl.ch.
solution :
chaque voyage de marmotte peut être décomposé en plusieurs étapes, reliant chacune deux emplacements voisins. Il n’importe pas de savoir quelle marmotte se déplace, puisqu’on s’intéresse exclusivement à la distance cumulative. Ainsi une solution greedy fait l’affaire. On demande aux marmottes excessives ou virtuellement manquantes du village 1 de se rendre au village 2. Maintenant le village 1 est en équilibre et nous répétons l’opération depuis le village 2 au village 3 et ainsi de suite, chaque fois sommant la différence absolue entre marmottes et portions de fondue dans le village actuel.


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.