Optimisations Algorithmiques et Structures de Données Avancées pour la Programmation Compétitive
Gestion des Cycles de Trafic et Arbre de Segment
Pour déterminer le temps minimal requis pour atteindre l'école depuis chaque intersection, le traitement doit s'effectuer en ordre inverse, du nœud final vers la source. L'état des feux de signalisation étant périodique, le temps d'arrivée à un point donné peut être réduit modulo $T$, où $T$ repr ...
Publié le 18 septembre à 16h35
Optimisation de la puissance de combat dans un arbre de relations maître-disciple
On a un groupe de combattants organisés en un arbre, où chaque combattant a un maître (sauf le chef). Chaque combattant a une certaine puissance de combat. Le but est d'inviter certains combattants pour maximiser la somme de leur puissance, tout en respectant la contrainte que si un maître est invité, aucun de ses disciples ne peut l'être.
Form ...
Publié le 13 août à 06h44
Techniques Avancées de Programmation Dynamique pour l'Algorithmique de Compétition
Coloriage de Parenthèses (DP par intervalles)
Ce problème classique de programmation dynamique par intervalles nécessite d'abord d'identifier les paires de parenthèses correspondantes à l'aide d'une pile. Pour un intervalle $[l, r]$, le coloriage n'a de sens que si les parenthèses sont appariées. Nous définissons l'état $f(l, r, c_1, c_2)$ comm ...
Publié le 2 juin à 01h40