L'Atelier Monstre

Problème A : Validation de sous-chaîne de mot de passe L'énoncé demande s'il est possible de modifier un mot de passe de longueur $m$ pour qu'il devienne une sous-chaîne d'une chaîne cible de longueur $n$. Puisque nous pouvons modifier n'importe quel caractère du mot de passe (sans changer sa longueur), la seule contrainte réelle est la dimensi ...

L'arbre de segments (Segment Tree) est une structure de données avancée, basée sur le principe de diviser pour régner. Il s'agit d'une structure arborescente binaire principalement conçue pour résoudre des problèmes d'intervalle ou de plage. Cette structure permet de maintenir des variables qui satisfont la propriété d'associativité (comme le m ...

Principe fondamental Transformer un arbre en une séquence linéaire où n'importe quel chemin correspond à au plus O(log n) segments consécutifs. Définitions essentielles Fils lourd : enfant dont la sous-arbre contient le plus de nœuds Fils léger : tout enfant n'étant pas fils lourd Arête lourde : reliant un nœud à son fils lourd Arête légère : ...