Coding Contest – Solutions et explications

Coding Contest – Forum Rhône-Alpes

Solutions et explications

Bonjour à tous et merci d’avoir participé à la première édition  du Coding Contest avec le Forum Rhône-Alpes !

Vous trouverez ci dessous les explications détaillées des solutions attendues à chaque problème, ainsi qu’un résumé des erreurs les plus fréquentes.

L’intégralité de nos tests, sujets et solutions sont disponibles avec ce lien  : https://github.com/INSAlgo/forum-coding-contest-2019.

N’hésitez pas à contribuer si vous pensez avoir une solution plus performante que la nôtre ou si vous avez développé la solution dans un langage qui n’est pas déjà corrigé !


A – Winter is gone

Dans ce problème vous deviez trouver quelle était la flèche la plus proche du centre de la cible.

Pour chaque trait il fallait calculer sa distance au centre. Le problème se réduisait alors à trouver l’indice de la flèche ayant la distance la plus faible en cherchant le minimum de la liste.

La majorité des difficultés sur ce problème sont venues de la prise en main de la plateforme. Pour le reste, certains d’entre vous ont eu du mal à traiter des nombres réels, en essayant par exemple de les convertir en entier (Runtime Error).

B – Aux armes

L’objectif était de rassembler une armée plus grande que l’ennemi en appelant un minimum de vassaux.

L’idée de la résolution est la suivante : pour garantir que le nombre d’appelés est minimum il faut d’abord choisir les vassaux qui apporteront le plus de soldats. On choisit donc le vassal encore non appelé qui a le plus de troupes à chaque itération, jusqu’à surpasser l’ennemi ou les avoir tous appelés.

Les difficultés sur ce problème se sont concentrés sur le jeu de test avancé, avec quelques cas limites qu’il ne fallait pas oublier. Que se passe-t-il si on a 0 alliés par exemple?

Pour passer le jeu de test de performance on attendait un tri décroissant des vassaux par nombre de soldats. Cela permet ensuite de choisir le plus important en complexité O(1), et ramène la complexité de la solution à O(n* log(n) ).

C – L’or des Lannister

Dans ce problème on voulait former la plus haute tour « bien rangée » de lingots, ce qui se réduisait en réalité à chercher la longueur de la plus longue sous suite arithmétique.

Pour le résoudre on pouvait par exemple appliquer cette algorithme :

  • Trier la liste des tailles des lingots
  • Pour tout lingot A:
    • Pour tout lingot B qui le suit :
      • Parcourir toute la suite de la liste en cherchant à chaque fois le prochain terme de la suite que l’on veut construire, de raison = largeur(B) – largeur(A), et extraire la taille de la suite à la fin de la liste.

Pour passer les performances il fallait livrer une version optimisée de l’algorithme ci dessus, ou utiliser la programmation dynamique ( fourni en correction) en utilisant une structure de donnée adaptée.

D – Au sommet du mur

On voulait dans ce problème minimiser le danger total pour atteindre le dernier étage du mur.

L’astuce était de considérer toute la tour comme un graphe implicite en 3d , sans distinction d’étages même s’ils ne sont reliés que par un nombre réduit d’échelles. Les voisins de chaque case sont connus a priori puisqu’ils ne dépendent que du type et de la position de celle-ci.

Il fallait aussi se rendre compte que le « danger pour passer d’une case à l’autre » peut être représenté par la valeur des arrêtes entre deux cases. On cherche alors un plus court chemin du point de départ à n’importe quel escalier montant du dernier étage.

Deux niveaux de résolution étaient proposés ici:

  • Pour le premier niveau, la dangerosité de tous les étages est considérée égale à 1. Il suffit alors d’effectuer un parcours en largeur du graphe depuis la position de départ.
  • Pour le second, la dangerosité peut varier. Il faut alors implémenter un algorithme plus général de plus court chemin. L’algorithme de Dijkstra par exemple faisait l’affaire. Pour passer le jeu de test performance il fallait utiliser un tas pour gérer la file d’attente et ainsi réduire la complexité temporelle.

 

Laisser un commentaire

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