Rencontre #33: Arrays, Hachage et Piles

par Guillaume Tardif et Samuel Maltais

Lors de cette rencontre, nous poursuivrons notre exploration des problèmes liés aux arrays en introduisant deux concepts fondamentaux en programmation compétitive : le hachage et les piles. Ces outils puissants vous permettront de résoudre une variété de problèmes plus efficacement, en manipulant et en organisant les données d’une manière qui simplifie les calculs et améliore les performances. Nous explorerons les bases de ces structures, leur utilité, et comment les utiliser dans des contextes pratiques à l’aide de Python.

Introduction au Hachage (Hashing)

Le hachage est une technique utilisée pour stocker et rechercher des données de manière très efficace. En utilisant une fonction de hachage, nous pouvons convertir une entrée (comme une chaîne de caractères ou un nombre) en un index dans une table de hachage, ce qui permet un accès rapide aux données.

Introduction aux Piles (Stacks)

Une pile (stack) est une structure de données qui suit le principe "Last In, First Out" (LIFO), c’est-à-dire que le dernier élément ajouté est le premier à être retiré. Imaginez une pile d’assiettes où vous ne pouvez retirer que celle du dessus.

Problèmes

Le nombre à côté de chaque problème indique son niveau de difficulté selon Kattis.

  1. “Odd Gnome” 1.6 — Trouvez le roi dans chaque groupe de gnomes en identifiant l’unique gnome qui ne respecte pas l’ordre strictement croissant de leurs identifiants.

  2. “Conformity” 1.7 — Calculez le nombre d’étudiants ayant choisi la combinaison de cours la plus populaire parmi toutes les combinaisons sélectionnées par les étudiants.

  3. “Deduplicating Files” 3.8 — Identifiez les fichiers en double en utilisant une fonction de hachage pour détecter les doublons potentiels et réduire le nombre de comparaisons directes entre fichiers.

  4. “Teque” 4.3 — Gérez une nouvelle structure de données appelée "teque" qui permet d’insérer des éléments à l’avant, à l’arrière ou au milieu, et d’accéder rapidement aux éléments par index.

  5. “Baby Names” 5.6 — Gérez une liste de prénoms avec insertion, suppression et recherche efficaces..