Rencontre #18: Diviser pour régner

La série de problèmes de cette semaine peuvent être résolus avec des approches de type diviser pour régner. Ce type d’algorithme séparent le problème à résoudre en plusieurs sous-problèmes résolus récursivement, puis rassemblent les résultats pour calculer la réponse au problème original.

Ressources

Voici quelques ressources qui pourront vous aider pour les problèmes.

• “Problem Solving Paradigms”, section “Divide and Conquer” dans le cours de programmation compétitive dispensé par Bjarki Ágúst Guðmundsson.
• Section 3.3 de “Competitive Programming” par S. Halim et al.
• Section 12.3 de “Programmation efficace” par C. Dürr et J.-J. Vie, utile en particulier pour le dernier problème.
• Section 15.4.2 de “Guide to Competitive Programming” par A. Laaksonen.

Problèmes

Les problèmes suivants sont triés par ordre croissant de difficulté.

1. “Out of Sorts” — Si on exécute une recherche binaire dans un tableau non-trié, combien de valeurs sont impossibles à retrouver?
2. “Batmanacci” — Calculez la valeur de la \(k\)-ème lettre du \(n\)-ème mot dans la séquence des mots de Fibonacci.
3. “Firefly” — Une luciole doit traverser en ligne droite horizontale une séquence d’obstacles verticaux. À quelle hauteur doit-on placer la luciole pour qu’elle croise le moins d’obstacles possible?
4. “Room Painting” — On souhaite acheter de la peinture de plusieurs couleurs à une compagnie qui la vend dans des contenants de taille fixe. Étant données les quantités de peinture souhaitées, combien de peinture sera gâchée au minimum?
5. “Closest Pair” — Identifiez rapidement la paire de points la plus rapprochée parmi un ensemble de points dans le plan.