Coding Battle 2019 – Shaker : Les solutions

Mercredi soir se tenait l’édition 2019 de la Coding Battle. INSAlgo a une fois de plus travaillé en partenariat avec le Shaker pour l’organiser : nous avons réalisé la plateforme, les problèmes, et assuré le support pendant le concours.

Vous pouvez trouver ici les solutions aux différents exercices :  https://github.com/INSAlgo/codingbattle-2019

En cas de besoin d’éclaircissement ou de précisions vous pouvez nous contacter par mail insalgo.contact@gmail.com !

Pour chacun d’entre eux nous vous fournissons le programme de référence dans des langages proposés sur la plateforme. Si vous cherchez des explications, c’est juste en dessous avec une description rapide des solutions !

Merci à tous les participants de cette édition : vous avez été exceptionnellement nombreux et nous vous attendons toujours plus motivés l’année prochaine pour vous améliorer encore et vous amuser avec ce concours.

Le bureau d’INSAlgo.


A. « Barques et ferries »

Ce problème a été compris et résolu par l’immense majorité des participants. Pour trouver le nombre de personnes que l’on ne pouvait pas emmener il fallait calculer le nombre total des places disponibles avec les bateaux à disposition, puis faire la différence avec le nombre de personnes. Petite nuance précisée dans l’énoncé, si la différence est négative on attend bien « 0 » en résultat !

B. « Un problème d’heures »

Ce problème a encore été bien réussi, même s’il a demandé du temps aux participants. Ici on voulait faire une conversion d’heures extraterrestres en heures terrestres.

La stratégie de résolution la plus simple : à partir des données de l’énoncé, calculer le nombre total de minutes extraterrestres dans l’heure donnée en entrée, et le convertir en nombre d’heures terrestres (en arrondissant bien au défaut). À partir de là on reconvertit le nombre de minutes en format heures:minutes, et le tour est joué. Une difficulté pour beaucoup, si le nombre d’heures est supérieur à 23 alors il faut faire un modulo 24 dessus pour recommencer une nouvelle journée !

C. « Alerte à la bombe 1 »

Ce problème confrontait les participants à de la géométrie et a donc réveillé des souvenirs un peu anciens pour certains. Il fallait le décortiquer un peu pour comprendre comment l’approcher : un suspect aura pu poser la bombe seulement si parmi ses relevés de positions il y en a 2 successives qui permettent de « faire un détour » par la bombe dans le temps imparti.

Concrètement, un suspect a pu poser la bombe si pour une de ces paires de positions (p1, p2) on valide la condition distance(p1, bombe) + distance(bombe, p2) ≤ 100m, en utilisant la distance euclidienne. L’implémentation la plus simple est alors de stocker toutes les positions dans des listes et de boucler dessus en testant cette condition pour trouver le ou les coupables.

D. « Pluie d’astéroïdes »

Par manque de temps ou à cause du saut de difficulté par rapport au précédent (notamment pour passer les tests de performances), cet exercice a été beaucoup moins réussi que les précédents.

Vous avez été nombreux à vous en rendre compte, ce problème s’approchait par un algorithme de programmation dynamique. Il fallait reprendre l’algorithme du sac à dos (KnapSack) et le modifier pour s’adapter au problème. La difficulté est de respecter la contrainte qu’il doit y avoir autant d’astéroïdes d’une couleur que de l’autre.

L’astuce est alors de rajouter une dimension au sac à dos : dans la matrice des remplissages possibles on enregistre non pas simplement si une capacité est atteignable mais bien toutes les différences entre le nombre d’astéroïdes d’un type et de l’autre. De cette manière on vérifie à la fin les cases qui sont à 0, c’est à dire qu’elles sont atteignables en ayant une différence nulle.

E. « Alerte à la bombe 2 »

Cet exercice reprenait le concept de l’exercice C, mais cette fois dans une grille et avec des contraintes supplémentaires . L’algorithme à utiliser est alors un pathfinder, par exemple Dijkstra. La subtilité est qu’il faut adapter dynamiquement le poids des arcs selon la distance/durée déjà parcourue et les feux. Un simple parcours en largeur ne permet pas de résoudre le problème, puisqu’il faut pouvoir quantifier le fait que l’on attend potentiellement devant un feu.

En appliquant simplement pour chaque position des suspects l’algorithme, on pouvait ainsi trouver à chaque fois la durée du trajet position -> bombe et la durée du trajet bombe -> position afin de déterminer si le suspect avait eu le temps d’atteindre la bombe ou non.
Cette solution vous permettait de valider les jeux de tests facile et difficile.
Pour réussir les performances, il fallait comprendre que seul 2 appels à Dijkstra depuis la bombe (une fois feu rouge, une fois feu vert) pouvaient suffire. En effet, même si la durée d’un trajet n’était pas la même selon le sens de parcours, cette durée ne variait au plus que d’un. Pour trouver la durée du trajet position -> bombe, il fallait donc obtenir le chemin optimal bombe -> position à partir du Dijkstra et le reparcourir dans le bon sens pour calculer la durée réelle du trajet.

F. « Déménagement périlleux »

Dernier problème, abordé par très peu de personnes. Il fallait trouver le nombre de personnes que l’on pouvait emmener dans les navettes en respectant des contraintes sur les personnes que chaque médiateur pouvait prendre avec lui. Les habitués auront reconnu un problème de matching, le problème étant qu’il est ici à 3 groupes et non deux comme habituellement.

Le mécanisme des méta navettes n’est en réalité pas utile : si toutes les navettes ont un nombre pair de places passagers et si chaque passager doit pouvoir être emmené par tous les médiateurs à bord alors on ne gagne rien à coller des navettes.

Cet exercice se résolvait donc avec un algorithme de flot (Ford Fulkerson dans notre correction) sans modification mais en concevant bien le graphe en entrée :

– Sur la première couche, tous les membres du premier peuple, reliés par un flot entrant de 1 à la source

– Sur la dernière couche, tous les membres du second peuple, reliés par un flot sortant de 1 au puits

– Entre elles, les médiateurs. Un médiateur est utilisable dans autant de trios qu’il a de paires de places dans sa navette. Pour matérialiser cette contrainte on duplique chaque nœud médiateur et on relie ces nœuds jumeaux par une arrête avec autant de flot qu’il peut emmener de paires. Il ne reste qu’à connecter chaque médiateur avec les personnes du peuple A et B qu’il peut emmener.

L’algorithme va alors maximiser le flot correspondant au nombre de triplets trouvables, à multiplier par 2 pour avoir le nombre de passagers emmenés.

 

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *