Thread by @MathisHammel

LIVE TWEET - Championnats d'Europe de programmation

Pendant tout le weekend aura lieu la compétition #SWERC à Milan, je suis présent en tant que coach de 3 équipes françaises.

Je vais essayer de vous expliquer le principe et vous tenir au courant des résultats en direct.

La cérémonie d'ouverture commence par un mini concert, je prendrai le temps de vous expliquer les règles du challenge tout à l'heure

Près de 60.000 participants cette année au niveau mondial représentant 3406 universités (oui c'est un championnat réservé aux étudiant/es, c'est pour ça que je peux plus participer en tant que joueur 😁)

Chaque université peut envoyer jusqu'à 3 équipes de 3 personnes, pour ma part j'accompagne les équipes de l'INSA Lyon qui est l'école d'ingénieur dont je suis diplômé

Un mot de bienvenue de Huawei, sponsor de l'événement représenté aujourd'hui par le directeur du centre de recherche Huawei à Milan

Bon y'a d'autres sponsors mais j'ai la flemme de transformer ce thread en encart publicitaire (les autres sont Jetbrains, Jane Street et Bending Spoons)

Et un deuxième concert pour finir la cérémonie d'ouverture !
C'est la première fois qu'on a des animations comme ça sur scène, un changement qui a l'air de faire l'unanimité

Le challenge est en plein essor sur les 10 dernières années, cette année à Milan on a 97 équipes en tout

Je me rends compte que je me fais vieux, à 25 ans c'est ma 7e participation au challenge 😅

Depuis 2015 j'en ai joué 3 en tant que participant et 4 en tant que coach.

C'est l'heure de prendre les photos des équipes, alors on essaie de s'appliquer pour reproduire le logo de l'INSA au mieux

Allez on est de retour dans l'amphi pour les conférences des sponsors, je vais avoir un peu de temps pour vous parler des règles du challenge et les favoris de cette année

Comme je vous le disais, c'est un challenge réservé aux étudiants, mais bon comme toute organisation de qualité impliquant des nerds on a un algorithme de décision à 12 étapes pour vérifier ou non l'éligibilité des joueurs/joueuses 👇

Pendant la compétition, les équipes ont entre 11 et 15 problèmes d'algorithmique à résoudre en 5 heures.

Si ça vous intéresse de voir à quoi ressemblent les sujets, voici les énoncés des deux problèmes les plus faciles de l'an dernier :

C'est de l'algorithmique assez classique (mais les problèmes sont très difficiles à partir du 6e), la plus importante particularité du concours c'est le fait que ça se joue en équipe de 3 personnes. Sans internet. Et un seul ordi par équipe.

Les 98 équipes présentes ce weekend à Milan participent au SWERC (Southwestern European Regional Championship) qui englobe 6 pays : France, Suisse, Italie, Espagne, Portugal et Israël.

L'Europe est partagée en 5 régions géographiques, chacune d'entre elles envoie quelques équipes à la finale mondiale des ICPC qui aura lieu cette année au Bangladesh.

Pour la région SWERC, c'est 2 à 5 équipes qui auront leur place en finale cette année.

Le calcul du classement se base sur deux scores : le nombre de problèmes résolus et la pénalité temporelle.

On classe d'abord les équipes par nombre décroissant d'exercices résolus, la pénalité temporelle sert à départager les ex-aequo.

Pour calculer la pénalité, on prend la somme des temps de résolution de chaque exercice. Par exemple, si une équipe résout le premier problème à 9h10 et le suivant à 9h45, la pénalité temporelle sera de 55 (= 10+45). Une soumission incorrecte ajoute 20mn de pénalité.

Passons à un peu de stratégie. Comment on fait pour coder efficacement quand on a un seul ordi pour 3 personnes ?

(Spoiler : pas comme ça 👇)

Déjà, il faut savoir que la première heure est de loin la plus déterminante, surtout pour les équipes qui résolvent 5 exos ou moins (soit environ 80% des équipes). Le départ est crucial, et on se prépare spécifiquement pour ça.

Quand on arrive dans la salle du concours, les sujets sont posés sur chaque table dans une enveloppe scellée. Au lancement, on ouvre les sujets et on se les répartit : chacun lit 1/3 des exos et essaie de trouver les problèmes les plus faciles.

Généralement, on a deux exercices très faciles (résolus par environ 95% et 90% des équipes respectivement), et un facile (~60% de validations). Ces exos prennent rarement plus de 15 minutes chacun, donc il faut rusher dessus pour minimiser sa pénalité temporelle.

Pour travailler en parallèle avec un seul PC, on va beaucoup travailler sur papier :
- Identification du prochain exo par ordre de difficulté
- Code sur papier
- Recopie sur ordi
- Test en local
- Soumission
- Si mauvaise réponse : on imprime le code et debug sur papier

Pas d'accès à internet non plus, principalement pour éviter la triche en communiquant avec l'extérieur. Les exos sont très originaux donc l'accès à des sites comme StackOverflow et GeeksForGeeks n'apporterait pas un énorme avantage.

Mais les équipes ont le droit à un joker :

Une partie de la préparation pour les championnats d'Europe consiste à créer un notebook papier de 25 pages qui peut être utilisé pendant la compétition.

C'est une des seules choses autorisées dans les salles (avec un dictionnaire, et une mascotte d'équipe pour se porter chance)

Les captures d'écran proviennent du notebook INSA Lyon que j'avais créé en 2017 et qui se transmet de génération en génération (principalement par flemme d'en refaire un😄)

Nos deux notebooks (Python/C++) sont open-source, vous pouvez les retrouver ici : github.com/INSAlgo/ICPC-N…

Le but du notebook est d'avoir des algorithmes déjà prêts qu'on peut juste recopier/adapter, mais on ne met généralement que des choses que l'on connaît.

L'avantage de les avoir sous la main est principalement le gain de temps et l'absence de bugs.

Après on a quand même des trucs extraterrestres et/ou pas hyper utiles dans le notebook, comme des tableaux d'intégrales ou de développements limités. Je crois que ça vient du notebook de Stanford qui est aussi open-source et à qui on a emprunté pas mal de pages 😇

On part déjeuner (ils nous ont mis groupe C 😭), rdv cet après-midi pour la session d'entraînement !

On commence le programme de l'après-midi : d'abord les organisateurs expliquent les règles de la compétition.

Ensuite, les étudiants se dirigeront vers les labs informatiques de l'université pour le concours d'entraînement qui durera 1h30.

Les langages autorisés cette année : C, C++, Java, Kotlin, Python

Pour l'instant pas de surprises ni de nouveautés sur les règles de cette édition.

Ah, une nouveauté ! (je crois)

Les participants ne sont plus obligés de passer par l'interface web Domjudge, ils ont un outil en ligne de commande à disposition pour envoyer leur code source à évaluer

Quand on soumet un code source pour tenter de valider un problème, le serveur donne très peu d'infos sur le verdict : on reçoit l'une de ces 7 valeurs et c'est tout.
Les jeux de tests ne sont pas fournis, donc c'est difficile de débugger et il faut créer ses propres tests.

La session d'entraînement devrait commencer d'une seconde à l'autre, petit souci technique du côté de l'orga 😅

C'est réparé, on va commencer !

Il reste 30mn sur le round d'entraînement, une des équipes INSA est en 14e position !

Aujourd'hui les coachs ont la permission d'aller voir les équipes, donc je tâte le terrain : on a deux équipes qui ont une bonne piste pour valider le problème C et tenter le top 10.

Les deux premiers problèmes du concours d'entraînement sont triviaux, ils servent juste à prendre en main la plateforme de soumission.

Mes solutions pour les deux premiers problèmes.

Les coachs ont une plateforme dédiée pour jouer le challenge entre eux, j'ai soumis le A après 1 minute et le B après 2 minutes.

Le problème C est nettement plus intéressant. On doit choisir chaque jour si l'on allume ou pas le chauffage, et l'objectif est de faire en sorte que la température journalière soit la plus proche possible d'une valeur donnée.

La solution pour celui-ci est plus compliquée !
On ne peut pas se permettre de tester toutes les combinaisons possibles (ça prendrait des milliards d'années à calculer), du coup j'ai codé une solution en programmation dynamique.
Exo validé en 30 minutes tout pile.

Petit moment d'auto-promo : si vous cherchez à apprendre la programmation dynamique pour comprendre ma solution ci-dessus, j'ai publié une vidéo récemment à ce sujet :

Le problème D est un problème de théorie des graphes : combien de chemins différents reviennent à leur point de départ après K étapes, sans jamais revenir sur ses pas en prenant le même chemin deux fois d'affilée ?

Sur cet exo je sèche carrément, j'ai trouvé une solution en complexité O(k*n^3) mais c'est trop lent. Mon pote @gaubian qui est là pour coacher les équipes de l'ENS Paris-Saclay a une solution sympa mais on est pas sûrs que ce soit la bonne.
Aucune équipe ne l'a encore validé.

@gaubian C'est la fin du practice contest !
Pas réussi à valider le problème D, mais je suis quand même très content de ma perf sur le C (en même temps, j'adore la prog dynamique).

@gaubian Côté étudiants, mes équipes ont validé 2 exos chacune sur le challenge d'entraînement. Les meilleurs ont une pénalité temporelle de 59, ce qui les place en 21e position sur le scoreboard temporaire.

À noter que le scoreboard arrête d'être mis à jour sur les 30 dernières minutes pour garder un peu de suspense, on va avoir les résultats finaux dans quelques minutes

Bonne surprise ! On a finalement une équipe d'insaliens qui a validé le problème C quelques minutes après le début de la période de freeze du scoreboard 😍

17e place sur le classement final, on espère avoir une belle perf comme ça sur le vrai championnat demain !

Si y'a bien un truc sur lequel les Français sont premiers, c'est bien le banquet au Crowne Plaza 😇
Tous les ans on prie pour que ce soit open bar, au détriment de nos performances du lendemain

4 fourchettes ????

Update : c'était open bar.

Toute l'équipe est bien rentrée à l'hôtel, on se retrouve demain à 8h pour la deuxième journée des championnats d'Europe !

JOUR 2 - Championnats d'Europe d'algorithmique

On est de retour sur le campus du Politecnico Di Milano pour l'épreuve de programmation qui aura lieu ce matin de 9h à 14h.

Mes 3 équipes sont prêtes !

Dernier contrôle des badges et des t-shirts avant d'entrer dans les labs : obligatoire de les porter pendant toute la compétition pour distinguer les participants des administrateurs.

Les coachs donnent un dernier mot d'encouragement avant de quitter les équipes pour la matinée.

Le challenge commence dans 5 minutes (sauf en cas de problèmes techniques comme hier).

Les sujets seront sous embargo pendant une bonne partie de la matinée, donc j'y aurai accès à 8h45 mais je ne pourrai pas les partager pendant le début de la compétition.

Les favoris de cette année sont des Français ! Sans grande surprise c'est l'équipe ENS Ulm 1, qui compte parmi ses effectifs trois médaillés aux olympiades internationales d'informatique : Arthur Léonard, Félix Breton et Victor Deng.

La compétition a finalement commencé à 9h.

Le scoreboard à T+45' se dessine, 4 équipes françaises dans le top 10 ! Les miens ont eu un départ difficile mais je crois en eux :)

Update après 1h40 de compétition : les universités Harbour Space et Tel Aviv se partagent le top 4, et l'INSA Lyon commence à se réveiller : les meilleurs ont résolu 3 problèmes et sont 39e du championnat.

Réunion réservée aux coaches : la directrice de la compétition discute de l'organisation de la finale.
Les 5 régions d'Europe se partagent 15 places en finale, qui sont réparties notamment au pro-rata du nombre d'équipes. Probablement 2 ou 3 slots pour le SWERC cette année.

6 équipes sont ex-aequo à 7 problèmes validés. Les deux équipes en tête sont en position de force : elles ont validé le problème K qui semble plus difficile que le C qui leur reste à résoudre.

Leaderboard à 15mn de la fin : le scoreboard est freeze depuis 13h pour garder un peu de suspense, le verdict des soumissions (habituellement rouge ou vert) est en bleu pour qu'on ne connaisse pas le résultat.

Tel-Aviv pourrait reprendre le top 2 si les soumissions sont OK.

C'est terminé !
La meilleure équipe de l'INSA est 49e, mais ça risque de changer assez fort après le dégel du leaderboard

Des nouvelles du front : toutes les soumissions de mes étudiants pendant la dernière heure (que je ne pouvais pas voir à cause du freeze) ont été infructueuses 😓

On abandonne l'espoir de top 50, dommage parce qu'ils avaient trouvé les solutions de 5 exos en tout...

Lot de consolation tout de même, je termine 2e sur 23 au challenge amical entre coachs, avec 5 problèmes validés (presque 6 !) 😁

Les coachs de l'école Harbour Space, spécialisée en prog compétitive, ont explosé le leaderboard.

L'embargo sur les énoncés est enfin levé ! Vous pouvez les retrouver ici codeforces.com/contest/1662/p…

Attention, les problèmes A/B/C/J du lien ci-dessus étaient ceux de l'entraînement d'hier, et les autres ont été mis dans le désordre.

Deux exos que j'ai bien aimés 👇

On ne peut pas encore discuter des solutions publiquement (le challenge public sur CodeForces est ouvert jusque 18h).

Mais pourquoi pas faire une vidéo pour présenter les problèmes les plus faciles avec leurs solutions 😇

Session de présentation des corrigés : le problème G, résolu par aucune équipe avant le freeze, a été écrit par Petr Mitrichev qui est l'un des meilleurs programmeurs compétitifs au monde !

C'est l'heure de révéler le leaderboard final !

Le process est super stressant, on révèle le verdict des tentatives effectuées pendant le freeze en partant de la dernière équipe et en changeant le classement au fur et à mesure.

La première de mes équipes à passer à la moulinette est INSA Lyon 2, qui termine à la 72e place.

Les 8 soumissions infructueuses sur le problème J ont ajouté une grosse pénalité temporelle, mais au moins ils ont fini par le valider.

C'est au tour de l'équipe INSA Lyon 3, deux soumissions pendant le freeze mais aucune des deux n'est passée. 61e place au final.

Et pour finir l'équipe INSA Lyon 1 qui a effectivement perdu son top 50 et termine juste 5 places devant l'équipe 3, à la 56e position.

Bravo à eux, pas de bol pour les bugs sur le problème D et L parce qu'ils avaient la bonne intuition et auraient pu finir top 30.

L'équipe de l'Université de Lorraine termine en 16e position avec 6 exos validés, alors que c'était leur première participation. Félicitations à eux !

On passe à la remise des médailles. Il y aura 2 équipes médaillées d'or 🥇, 4 médailles d'argent 🥈 et 8 de bronze 🥉, soit 14 équipes médaillées au total.

Polytechnique (14e) récupère la première médaille de bronze.

On connaît maintenant les équipes qui sont dans le top 10, mais pas encore leur ordre exact !

Parmi les 10 meilleurs, on compte donc :
- 3 🇫🇷
- 3 🇪🇸
- 2 🇮🇱
- 1 🇮🇹
- 1 🇨🇭

Polytechnique prend la dernière médaille de bronze, on entre dans le top 6 du classement.

Dommage pour les favoris de l'équipe ENS Ulm 1, qui vont devoir se contenter d'une médaille d'argent cette année.

Il n'y aura pas d'équipe française à la finale des championnats du monde d'algorithmique 2022.

Le top 4 se joue maintenant entre deux équipes de l'université de Tel Aviv et deux de l'école Harbour Space.

La seule soumission sur le problème G, par l'équipe TAU++, est refusée. Cet exercice créé par le double vice-champion du monde aura donc tenu les 97 équipes en échec 😁

Moment de suspense avant l'annonce du grand vainqueur de l'édition 2022 du championnat d'Europe...

C'est fait !
Félicitations à l'équipe de l'université Harbour Space (🇪🇸) qui remporte l'édition 2022 des championnats d'Europe de programmation !

Merci d'avoir suivi le live-tweet !

Sur la prochaine édition des championnats d'Europe, j'ai comme projet d'aider gratuitement des étudiant/es n'ayant pas de coach pour participer à cette compétition. Envoyez-moi un DM si ça vous intéresse 😁