Analyse de Problèmes de Programmation Compétitive : Combinatoire, Arbres et Segments
Problème 1 : Sommes de Sous-ensembles (Collection)
L'objectif est de calculer le produit de toutes les sommes possibles de sous-ensembles, chacune élevée à la puissance de sa fréquence d'apparition. Le cœur du problème repose sur un sac à dos (knapsack) pour compter ces occurrences.
Soit $f[j]$ le nombre de façons d'obtenir une somme $j$. En ra ...
Publié le 19 juillet à 11h03
Tri Topologique par BFS et DFS avec Détection de Cycles
Introduction au tri topologique : Deux approches principales existent : l'algorithme de Kahn (basé sur BFS) et la méthode DFS. Leur objectif est d'ordonner les nœuds dans un graphe dirigé acyclique (DAG), offrant souvent plusieurs solutions valides. Ces algorithmes identifient également la présence de cycles.
Principe de l'algorithme de Kahn (B ...
Publié le 20 juin à 19h52