Coding Battle – ShaKer : les solutions des problèmes

Cette année encore INSAlgo a travaillé en partenariat avec le ShaKer pour organiser la Coding Battle. 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-2018

Pour chacun d’entre eux nous vous fournissons le programme de référence dans presque tous les langages proposés, ainsi qu’une explication rapide de la méthode de résolution et un panorama des erreurs les plus fréquentes ci dessous.

Merci à tous les participants de cette édition, nous vous attendons aussi nombreux l’année prochaine pour réitérer votre succès ou prendre votre revanche !

Le bureau d’INSAlgo.


A. « Partage de butin »

Pour ce problème presque tous les participants ont compris le principe de résolution : comparer le nombre de pièces d’or nécessaire pour tout l’équipage (2* le nombre de pirates à bicornes +3* le nombre de pirates à tricornes).

La majorité des soucis sont venus du traitement des entrées / sorties, avec notamment pour beaucoup l’oubli de transformer l’entrée en format nombre.

B. « Les perroquets de Tortuga »

Problème encore bien réussi dans l’ensemble, même si certains tests étaient plus difficiles à passer. Il s’agissait ici de calculer pour chaque dresseur le nombre de perroquets que l’on pouvait acheter, en tenant bien compte des règles de la division entière.

Deux obstacles principaux : d’abord pour le jeu de test n°2 on trouvait un cas où deux dresseurs arrivaient à égalité, ce qui devait être géré en tenant compte de l’énoncé. Ensuite pour le jeu n°3 les performances étaient beaucoup réduites pour les participants qui ont choisi de stocker toutes les données plutôt que de les traiter « à la volée ».

C. « Tempête en mer »

Ce problème a arrêté la majorité des participants. La difficulté ici était double : il fallait trouver comment évaluer une répartition des chapeaux (Est ce qu’elle couvre tout le pont?), et comment générer intelligemment ces répartitions pour ne pas perdre de temps.

Beaucoup de difficultés de compréhension de l’énoncé dans ce problème, en particulier pour la signification de la taille des chapeaux. Les cas limites étaient également compliqués à gérer correctement, notamment le cas où un chapeau recouvre plusieurs positions et les début et fin du pont .

Pour passer les performances il fallait proposer un backtracking optimisé et ainsi éviter de perdre du temps à évaluer des combinaisons inutiles.

D. « L’alphabet pirate »

Il y avait plusieurs manières d’aborder ce problème, passant toutefois toutes par la programmation dynamique. Des algorithmes connus pouvaient être modifiés pour les besoins du problème: distance de Levenshtein, Longest Common Subsequence… Notre solution utilise un algorithme basé sur une Longest Increasing Subsequence, qui a l’avantage de satisfaire le problème dans sa forme la plus classique. Tout algorithme de complexité  O(Nlog(N)) ou O(N²) était accepté, y compris pour les tests de performances.

Evidemment un gros avantage ici pour les participants qui ont reconnu le problème comme étant une LIS malgré les changements dans l’ordre des caractères. Ce bouleversement de l’alphabet a donc plus posé soucis pour réfléchir à la solution que pour la coder, l’astuce la plus populaire étant d’utiliser une table associative pour se ramener dans le cas classique.

E. « Carte au trésor »

Cet exercice est une manipulation d’arbres : cela était volontairement indiqué de manière implicite afin de valoriser une étude approfondie du problème. Une fois le problème bien compris l’algorithme posait normalement assez peu de difficulté : pour chaque nœud on évalue combien d’or on peut remonter des nœuds fils, et on applique cela récursivement avec une approche bottom-up (en commençant par les feuilles de l’arbre et en remontant). Une approche top-down pouvait aussi fonctionner.

La difficulté ici était dans le temps nécessaire à bien cerner tous les paramètres du problème, afin de ne pas se lancer dans des solutions inutilement complexe en devant gérer des cycles par exemple.

F. « Deux bateaux, un équipage »

Dernier problème, au delà de la difficulté très peu de participants ont eu le temps de l’aborder sérieusement. Cet exercice pouvait se ramener à un problème de sac à dos modifié pour prendre en compte les binômes de rivaux, et se résolvait donc à l’aide de la programmation dynamique.

La composante « sac à dos » du problème n’aura pas échappé aux participants les plus avertis, en revanche l’astuce pour intégrer les rivaux à l’algorithme classique est restée un mystère pour l’immense majorité d’entre eux.


Quelques statistiques sur la réussite des problèmes par les participants :

Laisser un commentaire

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