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.
“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?
“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?
“Closest Pair” — Identifiez rapidement la paire de points la plus rapprochée parmi un ensemble de points dans le plan.