Cet article explore diverses techniques algorithmiques à travers une sélection de problèmes de programmation compétitive, couvrant des domaines tels que la construction, la théorie des nombres, les structures de données avancées, la programmation dynamique et la théorie des graphes.

CF1667C Couverture par Semi-Dames

Tags: Construction, Mathématiques

Énoncé du Problème

Sur un échiquier de dimension \(n \times n\), déterminez le nombre minimal de reines \(k\) nécessaire pour que chaque case de l'échiquier soit attaquée par au moins une reine. Proposez une configuration de placement de reines.

Rappel : une reine placée en \((x,y)\) attaque les cases \((X,Y)\) si \(x=X\), \(y=Y\), ou \(x-y=X-Y\).

Contraintes : \(1 \le n \le 10^5\).

Approche

Considérons une borne inférieure pour le nombre de reines. Chaque reine peut couvrir une ligne, une colonne et deux diagonales. Pour couvrir toutes les cases, il faut s'assurer que chaque ligne, chaque colonne et chaque diagonale est attaquée. Une reine \((x,y)\) couvre la ligne \(x\), la colonne \(y\), la diagonale principale \(x-y\) et l'anti-diagonale \(x+y\). Cependant, la définition du problème limite les attaques aux lignes, colonnes et diagonales principales (constant \(x-y\)).

Si nous plaçons \(k\) reines, elles peuvent couvrir au maximum \(k\) lignes et \(k\) colonnes. Les \(n-k\) lignes et \(n-k\) colonnes restantes peuvent être vues comme un sous-échiquier de \((n-k) \times (n-k)\) cases. Toutes les cases de ce sous-échiquier doivent être couvertes par les diagonales des reines déjà placées. Un échiquier de taille \(M \times M\) possède \(2M-1\) diagonales principales et \(2M-1\) anti-diagonales. Ici, nous ne nous occupons que des diagonales principales. Il faut au moins \(2(n-k)-1\) reines pour couvrir toutes les diagonales restantes. Ainsi, nous avons \(k \ge 2(n-k)-1\), ce qui implique \(3k \ge 2n-1\), donc \(k \ge \lceil \frac{2n-1}{3} \rceil\).

Pour la construction, si \(n \pmod 3 = 0\), le nombre minimal est \(2n/3\). On peut placer \(n/3\) reines sur la diagonale principale en \((i, i)\) pour \(i \in \{1, \dots, n/3\}\), et \(n/3\) reines sur une autre diagonale de la forme \((i, i+n/3)\) et \(n/3\) sur \((i, i+2n/3)\). Une stratégie plus simple pour atteindre la borne inférieure consiste à placer les reines le long de la diagonale principale à partir du coin supérieur gauche, puis à partir du coin inférieur droit.

Si \(n \pmod 3 = 2\), plaçons \(k = (2n-2)/3\) reines. On peut former deux carrés \((n-k) \times (n-k)\) en haut à gauche et en bas à droite. On place des reines sur la diagonale du carré supérieur gauche et sur la diagonale de la zone de superposition. Si \(n \pmod 3 \neq 2\), il suffit d'ajouter une reine dans le coin inférieur droit pour compléter la couverture.

CF1906L Parenthèses Palindromiques

Tags: Construction

Énoncé du Problème

Construisez une séquence de parenthèses valide \(s\) de longueur \(n\) telle que la plus longue sous-séquence palindromique ait une longueur \(k\).

Contraintes : \(2 \le n \le 2000\), \(1 \le k \le n\).

Approche

Examinons d'abord des exemples pour \(n=10\). Une séquence simple comme ((((())))) a une sous-séquence palindromique maximale de longueur \(n/2=5\). C'est simplement la moitié des caractères (tous les ( ou tous les )). Si nous modifions la séquence en ()(((()))), la longueur de la plus longue sous-séquence palindromique devient \(n/2+1=6\). Le () initial fournit une paire correspondante qui peut faire partie d'un palindrome. En ajoutant plus de paires () à gauche, comme ()()((())), la longueur passe à \(n/2+2=7\). Cependant, si nous ajoutons une autre paire, ()()()(()), la longueur reste \(7\). Pourquoi ? Chaque () ajouté à gauche introduit une ) qui peut se combiner avec une ( préexistante. Le problème est que les parenthèses de la forme () ne contribuetn pas toujours à augmenter la sous-séquence palindromique si elles ne peuvent pas être jumelées symétriquement.

Pour augmenter efficacement la longueur, nous devons équilibrer l'ajout de parenthèses ouvrantes et fermantes pour qu'elles puissent se "matcher". Si nous ajoutons des () à droite, par exemple ()()(())(), la longueur devient \(n/2+3=8\). L'ajout d'une () à gauche fournit une ) supplémentaire qui peut se coupler, tandis que l'ajout à droite fournit une ( supplémentaire qui peut aussi se coupler. Ces deux types d'ajouts peuvent se compléter pour résoudre un déficit de parenthèses pour les paires.

Ainsi, une méthode de construction efficace consiste à ajouter \(k - n/2\) paires () en les répartissant de manière aussi égale que possible aux deux extrémités d'une séquence centrale de la forme ((...)). Par exemple, pour obtenir une longueur \(k\), on peut former une séquence p par \(x\) () suivies de \(n/2 - x\) ( suivies de \(n/2 - y\) ) suivies de \(y\) (), où \(x+y = k - n/2\). Le cas \(n=k\) est impossible car la séquence () n'est pas un palindrome et un ( ou ) unique ne suffit pas à former un palindrome de longueur n.

CF1917E Construction de Matrice

Tags: Construction

Énoncé du Problème

Étant donné un entier pair \(n\) et un entier \(k\), construisez une matrice \(n \times n\) composée de 0 et de 1 qui satisfait les conditions suivantes :

• La somme totale des éléments de la matrice est exactement \(k\).
• La somme XOR de chaque ligne est identique.
• La somme XOR de chaque colonne est identique.

Approche

Pour ce problème, si \(k\) est impair, il n'y a pas de solution. La somme XOR de chaque ligne doit être la même (soit 0, soit 1). Comme \(n\) est pair, si la somme XOR de chaque ligne est 1, alors il y aurait \(n\) lignes avec un nombre impair de 1, ce qui ferait un total impair de 1 dans la matrice. Ceci est impossible car la somme totale \(k\) serait impaire. Similairement, si la somme XOR de chaque ligne est 0, alors le nombre de 1 dans chaque ligne est pair, donc \(k\) doit être pair. Par conséquent, \(k\) doit être pair.

Ensuite, les cas \(k=2\) et \(k=n^2-2\) n'ont de solution que pour \(n=2\). Pour \(k=2\), si nous plaçons les deux 1s dans la même ligne ou colonne, deux lignes/colonnes auront un XOR de 1, tandis que les autres auront 0. Si \(n>2\), ces sommes XOR ne seront pas identiques. Si nous les plaçons dans des lignes et colonnes différentes, deux lignes et deux colonnes auront un XOR de 1, et les autres 0. Encore une fois, pas de solution pour \(n>2\). Le cas \(k=n^2-2\) est symétrique (remplir de 1s et placer deux 0s), donc la même logique s'applique.

Considérons maintenant les cas restants :

• Si \(k \pmod 4 = 0\), nous pouvons simplement remplir \(k/4\) sous-matrices \(2 \times 2\) avec des 1s. Chaque telle sous-matrice a une somme de 4, et toutes les sommes XOR de lignes et colonnes impliquées seront 0.

• Si \(k \pmod 4 = 2\), il nous reste deux 1s supplémentaires après avoir rempli les sous-matrices \(2 \times 2\). Pour gérer cela, nous pouvons utiliser un motif spécial qui coûte six 1s, assurant que les sommes XOR restent nulles. Un motif \(3 \times 3\) de la forme suivante peut être utilisé : | 1 | 1 | 0 | |---|---|---| | 1 | 0 | 1 | | 0 | 1 | 1 |

  Ce motif assure que la somme XOR de chaque ligne et colonne est 0. Après avoir placé ce motif, nous pouvons compléter le reste avec des sous-matrices \(2 \times 2\) remplies de 1s pour atteindre \(k\).

Notez que pour \(k=n^2-6\), nous devons remplir quatre positions supplémentaires par rapport au cas général, mais la stratégie reste la même, en utilisant le motif \(3 \times 3\) et en le complétant.

CF1917E Construction de Matrice (pour \(n\) impair)

Approche

Si \(n\) est impair, nous pouvons réduire le problème à la construction pour \(k\) pair, car si nous avons une solution pour \(k'\) 1s, nous pouvons obtenir une solution pour \(n^2-k'\) 1s en inversant simplement tous les bits de la matrice. L'inversion change la somme XOR de chaque ligne/colonne de \(V\) à \(V \oplus 1\) si \(n\) est impair. Si toutes les sommes XOR étaient identiques, elles le resteront. Donc, nous devons juste résoudre pour \(k\) pair.

Soit \(n=2x+1\).

Puisque \(k\) est pair et que la somme XOR de chaque ligne doit être 0 (un nombre impair de 1s dans une ligne d'une matrice impaire donnerait 1), chaque ligne doit contenir un nombre pair de 1s. Le nombre maximum de 1s par ligne est \(2x\). Le total maximum de 1s est donc \(n \times 2x = (2x+1) \times 2x = 4x^2+2x\). Si \(k > 4x^2+2x\), il n'y a pas de solution.

Considérons le cas où \(k = 4x^2+2x\). Nous pouvons construire une matrice en plaçant des 1s dans toutes les cellules sauf celles de la diagonale principale \((i,i)\). Chaque ligne/colonne aura alors \(n-1 = 2x\) 1s, ce qui est un nombre pair. La somme XOR de chaque ligne/colonne est donc 0.

Nous pouvons ensuite utiliser la même logique que pour le cas \(n\) pair pour construire des solutions pour \(k=4m\) ou \(k=4m+2\), où \(m \le x^2\). Cela nous permet de construire des solutions jusqu'à \(4x^2+2\).

Il ne reste qu'à construire des solutions pour les valeurs de \(k\) dans l'intervalle \((4x^2+2, 4x^2+2x)\), toutes paires. Nous pouvons partir de la solution pour \(k=4x^2+2x\) (où seuls les éléments de la diagonale sont 0) et modifier progressivement la diagonale pour réduire le nombre total de 1s de 2 à chaque étape.

Par exemple, en partant de la matrice avec \(4x^2+2x\) 1s, nous pouvons choisir un bloc \(2 \times 2\) sur la diagonale (par exemple, aux positions \((i,i), (i,i+1), (i+1,i), (i+1,i+1)\)) qui est initialement :

0	1
1	0

et le transformer en | 1 | 0 | |---|---| | 0 | 0 |

Cette modification supprime deux 1s de la matrice et maintient la somme XOR de ligne/colonne à 0. En répétant cette opération pour les diagonales des lignes \(2, 4, \ldots, 2x\), nous pouvons réduire \(k\) de 2 à chaque fois, couvrant ainsi toutes les valeurs paires dans l'intervalle \([4x^2, 4x^2+2x]\). ### Matrix Remake

Énoncé du Problème

Étant donné trois entiers \(n, m, k\), construisez une matrice \(A\) de taille \(n \times m\) satisfaisant les contraintes suivantes :

• Pour tout \(i,j\) (\(1\le i\le n, 1\le j\le m\)), \(1\le A_{i,j}\le 2k\).
• Pour tout \(j\) (\(1\le j\le m\)), la somme \(\sum_{p=1}^{n}A_{p,j}\) est impaire.
• Pour toutes paires de lignes distinctes \(i,i'\) (\(1\le i < i'\le n\)), il existe au moins un entier \(j\) (\(1\le j\le m\)) tel que \(A_{i,j}\ne A_{i',j}\).

Contraintes : \(1\le n\times m\le 2\cdot 10^6\), \(1\le k\le 10^9\).

CF1896F XOR de Parenthèses

Tags: Construction

Énoncé du Problème

On vous donne une chaîne binaire \(s\) de longueur \(2n\). Vous pouvez effectuer au maximum 10 opérations. Chaque opération consiste à fournir une séquence de parenthèses valide de longueur \(2n\). Pour chaque paire de parenthèses appariées dans cette séquence, les bits correspondants dans \(s\) sont inversés. L'objectif est de transformer \(s\) en une chaîne de \(0\)s, ou de rapporter l'impossibilité.

Approche

Analysons les effets d'une opération sur la chaîne \(s\).

Premièrement, les caractères \(s_1\) et \(s_{2n}\) seront toujours affectés par une opération, car dans toute séquence de parenthèses valide, la première parenthèse est ouvrante et la dernière est fermante, et elles sont appariées (ou font partie de paires). En fait, ( est toujours en position impaire et ) en position paire. Par exemple, si s\_1 est ( et s\_{2n} est ), et ils sont appariés, ils seront inversés. Si `s_1 \ne s_{2n}\) initialement, il est impossible de rendre la chaîne entièrement nulle, car la première et la dernière position seront toujours traitées symétriquement par une opération, ou de manière totalement indépendante, mais elles sont toutes deux appariées à quelque chose. Plus précisément, pour toute séquence de parenthèses valide, le premier caractère est une parenthèse ouvrante et le dernier une parenthèse fermante. Ils doivent être appariés à quelque chose. Si \(s_1 \neq s_{2n}\) au début, on ne peut pas les rendre tous les deux nuls.

Deuxièmement, chaque opération inverse un nombre pair de positions, puisque chaque parenthèse ouvrante a une parenthèse fermante correspondante. Par conséquent, si le nombre de \(1\)s dans \(s\) est impair, il est impossible de la rendre entièrement nulle.

Supposons sans perte de généralité que \(s_1=1\). Si \(s_1=0\), nous pouvons effectuer une opération avec la séquence ()()...() (qui alterne des paires de parenthèses) pour inverser tous les bits de \(s\), puis travailler avec la chaîne inversée. Cette opération coûte 1 coup.

Une stratégie possible consiste à cibler des paires de \(1\)s. Chaque opération nous permet de choisir deux \(1\)s adjacents, les apparier avec des parenthèses, et remplir les \(0\)s entre eux avec des paires () non imbriquées. De cette façon, chaque \(0\) sera inversé deux fois (revenant à son état initial), et chaque \(1\) sera inversé une seule fois. Ceci nécessite que chaque segment de \(0\)s entre deux \(1\)s ait une longueur paire.

Considérons comment rendre \(s_i\) et \(s_{i+1}\) identiques (pas nécessairement \(0\)) :

• Si \(s_i = s_{i+1}\) déjà, nous pouvons placer une paire () à ces positions, inversant les deux et les maintenant identiques.
• Si \(s_i \ne s_{i+1}\), nous pouvons utiliser des séquences comme (( ou )) pour les rendre identiques. Nous vérifions s'il y a des parenthèses ouvrantes non appariées précédemment. S'il y en a, nous utilisons )). Sinon, nous utilisons ((. Le nombre de parenthèses non appariées est toujours pair.

La deuxième opération (rendre \(s_i\) et \(s_{i+1}\) identiques) doit être appliquée un nombre pair de fois, sinon la parité du nombre de \(1\)s dans la chaîne changerait. Avec cette approche, il est possible de transformer \(s\) en une chaîne de \(0\)s en utilisant au maximum 3 opérations.

CF1227G Pas le Même

Tags: Construction

Énoncé du Problème

Étant donné une séquence \(a\) de taille \(n\), où \(1 \le a_i \le n\). Vous devez effectuer au maximum \(n+1\) opérations pour rendre tous les nombres nuls. Chaque opération consiste à choisir un sous-ensemble d'éléments et à décrémenter chacun de 1. Les sous-ensembles choisis pour chaque opération doivent être distincts.

Approche

Voici une construction. Premièrement, triez les éléments de \(a\) par ordre décroissant. Ensuite, construisez une matrice binaire \(M\) de \(n \times (n+1)\) où \(M_{i,j}=1\) signifie que l'élément \(a_i\) est décrémenté lors de l'opération \(j\).

Pour chaque \(a_i\), nous allons la décrémenter \(a_i\) fois. Commençons à remplir la matrice en parcourant les éléments de \(a\) (déjà triés). Pour l'élément \(a_i\), nous effectuons \(a_i\) décrémentations. Nous assignons la première décrémentation à l'opération \(a_i\). Les décrémentations suivantes sont assignées circulairement : \(a_i+1\), \(a_i+2\), ..., jusqu'à ce que \(a_i\) décrémentations aient été assignées. Si nous atteignons l'opération \(n+1\), nous recommençons à l'opération \(1\).

Formellement, pour chaque \(a_i\), mettez un 1 dans la colonne \(j\) pour \(a_i\) fois, où \(j = (a_i + k - 1 \pmod{n+1}) + 1\) pour \(k=1 \dots a_i\). Chaque colonne \(j\) représente un sous-ensemble. Pour une colonne \(j\), les éléments \(a_i\) pour lesquels \(M_{i,j}=1\) forment un sous-ensemble d'éléments à décrémenter.

Pourquoi cette construction est-elle correcte ? Supposons par contradiction qu'il existe deux colonnes \(j\) et \(j'\) qui sont identiques. Cela signifie que les sous-ensembles des éléments décrémentés sont les mêmes. Sans perte de généralité, soit \(j < j'\). Si les colonnes \(j\) et \(j'\) sont identiques, alors pour chaque ligne \(i\), \(M_{i,j} = M_{i,j'}\). Pour un élément \(a_i\), les \(a_i\) 1s sont placés dans des colonnes consécutives (modulo \(n+1\)) à partir de la colonne \(a_i\). Considérons l'élément \(a_i\) tel que \(M_{i,j}=1\). Cela signifie que l'opération \(j\) est l'une des \(a_i\) opérations allouées à \(a_i\). La colonne \(j'\) doit aussi contenir un 1 pour \(a_i\). Ceci implique que \(j'\) est aussi parmi les \(a_i\) opérations allouées à \(a_i\). Puisque \(a_i \le n\), l'intervalle de colonnes allouées à \(a_i\) a une longueur maximale de \(n\). Si deux colonnes \(j\) et \(j'\) sont identiques, cela signifie que toutes les \(a_i\) décrémentations pour chaque \(a_i\) sont positionnées de manière identique par rapport à \(j\) et \(j'\). Ce qui est impossible car les intervalles des 1s pour chaque \(a_i\) sont des intervalles de longueurs différentes dans le cycle des \(n+1\) opérations. Si \(j\) et \(j'\) sont identiques, cela implique qu'il y a un décalage \(d=j'-j\) tel que tous les \(a_i\) 1s pour chaque \(i\) sont répartis de la même manière par rapport à \(j\) et \(j+d\). Ce qui n'est pas possible si \(d \pmod{n+1} \ne 0\).

Ceci est une explication simplifiée. La preuve formelle repose sur le fait que la construction assure que pour chaque ligne \(i\), les \(1\)s forment un intervalle de longueur \(a_i\) dans le cycle des colonnes \(1 \dots n+1\), commençant à \(a_i\). Si deux colonnes \(j\) et \(j'\) étaient identiques, cela impliquerait que tous ces intervalles ont des \(1\)s dans \(j\) et \(j'\) simultanément, ce qui n'est pas possible pour des longueurs d'intervalle distinctes et des points de départ distincts (qui sont les valeurs \(a_i\)).

CF1491G Échanger et Retourner

Tags: Théorie des graphes, Réflexion

Énoncé du Problème

On dispose de \(n\) pièces de monnaie. Initialement, la \(i\)-ème pièce est à la position \(c_i\) (où \(c\) est une permutation), face visible. Vous pouvez effectuer au maximum \(n+1\) opérations :

• Choisissez deux entiers \(i,j\). Échangez les pièces \(i\) et \(j\), puis retournez-les.

L'objectif est que la \(i\)-ème pièce soit à la position \(i\) et toutes face visible.

Contraintes : \(3 \le n \le 2 \times 10^5\).

Approche

Représentons le problème comme un graphe de permutation. Chaque pièce \(i\) est à la position \(c_i\). On trace une arête de \(i\) vers \(c_i\). Cela forme un ensemble de cycles disjoints. L'objectif est de transformer toutes les arêtes en boucles \(i \to i\) avec toutes les pièces face visible.

Une opération \((i, j)\) : les pièces aux positions \(i\) et \(j\) sont échangées, et leurs faces sont retournées. Supposons que la pièce \(X\) est à la position \(i\) et la pièce \(Y\) est à la position \(j\). Après l'opération, \(Y\) est à la position \(i\) et \(X\) à la position \(j\). Les faces de \(X\) et \(Y\) sont retournées.

Considérons un cycle \(a \to b \to c \to \dots \to a\). Si nous effectuons une opération entre la position \(a\) et la position \(b\), la pièce \(A\) (initialement à \(a\)) et la pièce \(B\) (initialement à \(b\)) échangent leurs places et sont retournées. La structure du cycle est modifiée. Si \(P_x\) est la pièce à la position \(x\), et on applique l'opération \((i,j)\). La pièce \(P_i\) va à la position \(j\), et \(P_j\) va à la position \(i\). Les faces de \(P_i\) et \(P_j\) sont retournées.

Concentrons-nous sur le "retournement" des pièces. Une pièce est "correcte" si elle est à sa position finale et face visible. Elle est "incorrecte" sinon. L'idée est de décomposer les cycles et de gérer les retournements.

Pour un cycle de longueur \(S\), disons \(v_1 \to v_2 \to \dots \to v_S \to v_1\). Effectuons l'opération \((v_1, v_2)\). La pièce à \(v_1\) va à \(v_2\), celle à \(v_2\) va à \(v_1\). Les deux sont retournées. Ceci peut briser un cycle en plusieurs. Une stratégie pour un cycle de longueur \(S \ge 2\): 1. Choisissez deux nœuds adjacents \(u, v\) dans le cycle. Effectuez l'opération \((u,v)\). Cela aura pour effet de faire en sorte que \(u\) soit en position \(v\) et \(v\) en position \(u\). Les pièces initialement en \(u\) et \(v\) sont retournées. Cela rompt le cycle et crée une boucle pour \(u\) si \(u\) était \(c_u\) et \(v\) était \(c_v\). 2. Ensuite, pour chaque autre nœud \(x\) du cycle, effectuez l'opération \((x, \text{pièce en } u)\). Cette approche nécessite au moins \(S+1\) opérations pour un cycle de longueur \(S\) si on le traite isolément. Cette méthode n'est pas optimale.

Considérons deux cycles, un de longueur \(S_1\) et un autre de longueur \(S_2\). On peut utiliser une opération pour "fusionner" deux cycles en un seul plus grand cycle, tout en retournant deux pièces. Par exemple, si on a un cycle \(C_1 = (a \to b \to \dots \to a)\) et \(C_2 = (x \to y \to \dots \to x)\). On effectue l'opération \((a,x)\). Les pièces à \(a\) et \(x\) sont retournées. La permutation \(c\) est modifiée de sorte que les cycles fusionnent. Maintenant, on a un grand cycle avec deux pièces retournées. Pour chaque nœud de ce grand cycle, on peut le ramener à sa place en utilisant la pièce \(a\) (ou \(x\)) comme intermédiaire, en \(S_1+S_2-1\) opérations. Enfin, les deux pièces initialement à \(a\) et \(x\) sont retournées et se retrouvent dans leurs bonnes positions avec la bonne orientation. Au total, cela prend \(1 + (S_1+S_2-1) + 1 = S_1+S_2+1\) opérations pour deux cycles.

Si le nombre de cycles est pair, nous pouvons les apparier et les traiter deux par deux. Chaque paire de cycles de longueurs \(S_1, S_2\) prend \(S_1+S_2+1\) opérations. La somme totale sera \(\sum (S_i + S_{i+1} + 1)\). Comme \(\sum S_i = n\), et il y a \(k\) cycles, la somme sera \(n+k/2\) opérations si \(k\) est pair.

Si le nombre de cycles est impair, il reste un cycle à la fin. On peut le combiner avec un auto-cycle (un point fixe \(i \to i\)) qui peut être considéré comme une pièce déjà en place et face visible. On sacrifie cette pièce en la retournant et l'utilisant pour combiner le cycle restant. Cela ajoute une opération supplémentaire.

Pour le cas d'un seul cycle de longueur \(n\): Si \(n=3\), disons \((1 \to 2 \to 3 \to 1)\). 1. Opération \((1,2)\) : Pièce 1 est à pos 2, Pièce 2 à pos 1. Faces 1 et 2 retournées. État : Pièce 2 est à pos 1 (face retournée), Pièce 1 est à pos 2 (face retournée), Pièce 3 est à pos 3 (face normale). Il nous reste à placer Pièce 2 à pos 2, Pièce 1 à pos 1, et toutes face visible. 2. Opération \((1,3)\) : Pièce 2 est à pos 3, Pièce 3 est à pos 1. Faces 2 et 3 retournées. État : Pièce 3 est à pos 1 (face retournée), Pièce 1 est à pos 2 (face retournée), Pièce 2 est à pos 3 (face normale). 3. Opération \((2,3)\) : Pièce 1 est à pos 3, Pièce 2 est à pos 2. Faces 1 et 2 retournées. État : Pièce 3 est à pos 1 (face retournée), Pièce 2 est à pos 2 (face normale), Pièce 1 est à pos 3 (face normale). 4. Opération \((1,2)\) : Pièce 3 est à pos 2, Pièce 2 est à pos 1. Faces 3 et 2 retournées. État : Pièce 2 est à pos 1 (face retournée), Pièce 3 est à pos 2 (face normale), Pièce 1 est à pos 3 (face normale). Ceci est plus complexe, mais le coût est \(n+1\) opérations. La stratégie pour un cycle unique de longueur \(n>3\) est de choisir un point \(x\), l'opérer avec un voisin \(y\). Cela crée deux sous-cycles avec une pièce retournée chacun. On utilise ensuite ces pièces retournées comme pivots pour ramener les autres pièces à leurs positions. Finalement, les deux pièces retournées sont échangées et retournées pour résoudre leur cas. Cela prend \(n+1\) opérations. Le total d'opérations est toujours au maximum \(n+1\).

CF702F T-shirts

Tags: Structures de Données, Glouton

Énoncé du Problème

Vous avez \(n\) articles, chacun avec un prix \(c_i\) et une qualité \(q_i\). Il y a \(k\) acheteurs, le \(i\)-ème acheteur dispose de \(b_i\) unités monétaires. Chaque acheteur achète séquentiellement l'article de la plus haute qualité qu'il peut se permettre. Si plusieurs articles ont la même qualité, il choisit le moins cher. Vous devez déterminer le nombre d'articles que chaque acheteur peut acheter. Les requêtes sont indépendantes.

Contraintes : \(1\le n,k\le 2\cdot10^5\), \(1\le c_i,q_i,b_i\le 10^9\).

Approche

L'information sur la qualité \(q_i\) simplifie le problème : nous devons trier les articles par \(q_i\) en ordre décroissant, puis par \(c_i\) en ordre croissant en cas d'égalité de \(q_i\). Ensuite, chaque acheteur considérera les articles dans cet ordre. Les requêtes sont indépendantes, donc chaque acheteur est traité individuellement.

Une approche naïve pour chaque acheteur serait de parcourir tous les articles triés et d'acheter ceux qu'il peut se permettre, déduisant le prix de son budget. Ceci est trop lent (\(O(nk)\)).

Une meilleure approche consiste à considérer les articles séquentiellement (toujours triés comme décrit ci-dessus) et à voir quels acheteurs peuvent acheter l'article courant. Le problème se reformule comme suit : on a une liste de budgets \(b\). Pour chaque article \(i\) de prix \(c_i\), on doit trouver tous les budgets \(b_j\) tels que \(b_j \ge c_i\), les décrémenter de \(c_i\) et incrémenter le compteur d'articles pour l'acheteur \(j\).

Cette opération de "décrémenter tous les nombres supérieurs à un seuil" peut être gérée efficacement par une structure de données, comme un arbre équilibré (par exemple, un treap ou un splay tree) ou un segment tree. Pour chaque article \(i\) de prix \(c_i\), nous pouvons diviser les budgets actuels des acheteurs en trois catégories :

1. Budgets dans l'intervalle \([0, c_i)\) : Ces acheteurs ne peuvent pas acheter l'article. Leurs budgets restent inchangés.
2. Budgets dans l'intervalle \([c_i, 2c_i)\) : Ces acheteurs peuvent acheter l'article. Leurs budgets sont décrémentés de \(c_i\). Ces budgets sont "petits" et leur position relative par rapport aux budgets de la première catégorie peut changer. Il faut les traiter explicitement.
3. Budgets dans l'intervalle \([2c_i, \infty)\) : Ces acheteurs peuvent acheter l'article. Leurs budgets sont décrémentés de \(c_i\). Leur position relative par rapport aux autres budgets de cette catégorie ne change pas. On peut appliquer un "lazy tag" (décalage) pour cette catégorie.

La difficulté réside dans le deuxième intervalle. Heureusement, la modification des budgets dans l'intervalle \([c_i, 2c_i)\) est amortie. Chaque fois qu'un budget \(b_j\) est dans cet intervalle et est décrémenté de \(c_i\), il devient \(b_j - c_i\). Comme \(b_j \ge c_i\), le nouveau budget \(b_j - c_i\) est inférieur à \(c_i\). Si le nouveau budget est de nouveau décrémenté par un \(c_k\), il doit être \(c_k\) et il doit être supérieur à \(c_k\). De plus, un budget \(b_j\) qui est décrémenté par \(c_i\) et tombe dans \([c_i, 2c_i)\) sera au moins divisé par deux (car \(b_j \ge c_i \implies b_j - c_i \le b_j/2\)). Donc, chaque budget est traité explicitement au maximum \(\log_2 B_{max}\) fois, où \(B_{max}\) est le budget maximal initial.

En utilisant un arbre équilibré qui supporte les opérations de fractionnement (split), fusion (merge) et application de tags paresseux (lazy tags) pour les décalages, nous pouvons obtenir une complexité totale de \(O((N+K)\log B_{max} \log(N+K))\) ou \(O((N+K)\log K \log B_{max})\) pour certaines implémentations, ce qui est acceptable.

AGC016D Remplacement par XOR

Tags: Réflexion, Théorie des Graphes

Énoncé du Problème

Vous avez une séquence \(a\). Une opération consiste à remplacer un élément \(a_i\) par le XOR-somme de toute la séquence. Trouvez le nombre minimal d'opérations pour atteindre une séquence cible \(b\).

Contraintes : \(1\le n\le 10^5\), \(0\le a_i,b_i\le 2^{30}\).

Approche

Commençons par analyser l'effet d'une opération. Soit \(x\) la somme XOR de la séquence \(a\). Si nous choisissons \(a_i\) et le remplaçons par \(x\), alors le nouveau XOR-somme de la séquence sera \(x \oplus a_i \oplus x = a_i\). En d'autres termes, une opération consiste à échanger \(a_i\) avec la somme XOR actuelle \(x\).

L'objectif est de transformer la séquence \(a\) en \(b\). Traçons un graphe des relations nécessaires. Pour chaque indice \(i\) où \(a_i \neq b_i\), nous avons un "désaccord". Nous voulons que \(a_i = b_i\) pour tous les \(i\). Considérons les valeurs qui doivent bouger. Si \(a_i \ne b_i\), la valeur \(a_i\) doit quitter la position \(i\) et la valeur \(b_i\) doit arriver à la position \(i\). On peut modéliser cela avec un graphe orienté. Pour chaque \(i\) où \(a_i \ne b_i\), nous voulons déplacer \(a_i\) vers un autre endroit et placer \(b_i\) à la position \(i\). Initialement, nous avons un ensemble de valeurs dans \(a\) et un ensemble de valeurs dans \(b\). Si la multi-collection de \(a\) n'est pas la même que celle de \(b\), alors c'est impossible, à moins que la valeur \(x\) ne soit utilisée. En fait, la valeur \(x\) est toujours présente dans la multi-collection après une opération. Une propriété clé est que la somme XOR de la séquence \(a\) est toujours maintenue, sauf quand \(x\) change. Si la multi-collection \(\{a_i\} \cup \{x\}\) n'est pas la même que la multi-collection \(\{b_i\} \cup \{x'\)\) où \(x'\) est le XOR final, c'est impossible. La condition de possibilité est que la multi-collection \(A \cup \{X_A\}\) (où \(X_A\) est le XOR de \(A\)) doit être égale à \(B \cup \{X_B\}\) (où \(X_B\) est le XOR de \(B\)). Si ce n'est pas le cas, on ne peut pas atteindre \(B\).

On peut construire un graphe de permutation sur les valeurs. Pour chaque \(i\) où \(a_i \neq b_i\), nous voulons que la valeur \(a_i\) se déplace vers l'endroit où \(b_i\) doit aller, et vice-versa. Cela crée des cycles. Une opération \((i, x)\) échange la valeur \(a_i\) avec \(x\). Si \(a_i = b_i\), on ne fait rien. Si \(a_i \ne b_i\), on a besoin que \(b_i\) se retrouve à la position \(i\). Considérons les indices où \(a_i \ne b_i\). Nous pouvons les regrouper. Pour chaque valeur \(v\), comptons son apparition dans \(a\) et \(b\). Si \(a_i \ne b_i\), nous pouvons tracer une arête de \(a_i\) vers \(b_i\). Ceci n'est pas tout à fait une permutation. Les éléments qui sont les mêmes dans \(a\) et \(b\) sont des points fixes. L'opération effective est un échange entre \(a_i\) et la somme XOR courante \(X\). Si \(a_i \ne b_i\), on peut soit placer \(b_i\) à la position \(i\) en échangeant \(a_i\) avec \(b_i\). Mais on n'a que \(X\) pour échanger. L'objectif est d'atteindre l'état où tous les \(a_i\) sont égaux à \(b_i\). Le XOR initial est \(X_A = \bigoplus a_i\). Le XOR final est \(X_B = \bigoplus b_i\).

Le nombre de valeurs qui doivent être permutées est le nombre d'indices \(i\) où \(a_i \ne b_i\). Construisons un graphe où les nœuds sont les valeurs présentes dans \(a\) ou \(b\). Pour chaque \(i\) tel que \(a_i \ne b_i\), nous avons une arête \(a_i \to b_i\). Chaque fois que nous effectuons une opération \(a_i \leftrightarrow X\), nous avons plusieurs cas : 1. Si \(a_i\) était un élément qui devait être modifié (c'est-à-dire \(a_i \ne b_i\)), et nous effectuons \(a_i \leftrightarrow X\). 2. Si \(X\) est un élément qui doit se trouver à une position \(j\) où \(b_j=X\). Le coût total est le nombre d'arêtes qui doivent être "résolues". Un cycle de longueur \(S\) peut être résolu en \(S\) opérations si on a une "source" de valeurs. Le XOR-somme \(X\) peut être considéré comme une "ressource" que nous pouvons échanger avec n'importe quel \(a_i\). Si \(a_i \ne b_i\), nous devons déplacer \(a_i\) et insérer \(b_i\). Nous construisons un graphe sur les valeurs \(V = \{a_1, \dots, a_n, b_1, \dots, b_n\}\) et la valeur \(X = \bigoplus a_i\). Pour chaque \(i\) où \(a_i \ne b_i\), créons un "besoin" de déplacer \(a_i\) et d'insérer \(b_i\). On peut modéliser ceci comme un graphe de flux. Mais une approche plus simple est de considérer les cycles.

Considérons l'ensemble des valeurs \(\{a_i\}_{i=1}^n \cup \{X\}\) et \(\{b_i\}_{i=1}^n \cup \{Y\}\) où \(X=\bigoplus a_i\) et \(Y=\bigoplus b_i\). Si ces deux multisets ne sont pas identiques, alors il n'y a pas de solution. Si elles sont identiques, alors on peut atteindre la cible. On crée des composantes connexes. Chaque \(a_i \ne b_i\) correspond à une arête conceptuelle de \(b_i\) vers \(a_i\). On compte les cycles et les chemins. L'opération \(a_i \leftrightarrow X\) nous permet de déplacer \(X\) à la position \(i\) et d'envoyer \(a_i\) en tant que nouvelle somme XOR. Si nous voulons qu'un certain \(b_i\) arrive à la position \(i\), nous devons l'échanger avec la valeur courante \(X\). Le nombre minimal d'opérations est le nombre d'indices \(i\) tels que \(a_i \ne b_i\), plus le nombre de composantes connexes formées par les paires \((a_i, b_i)\) qui ne contiennent pas \(X\), moins 1 (si \(X\) est dans une composante non triviale).

Soit \(S = \{ i \mid a_i \neq b_i \}\). On crée un graphe où les nœuds sont les valeurs et, pour chaque \(i \in S\), on ajoute une arête de \(a_i\) à \(b_i\). On détermine les composantes connexes de ce graphe. La valeur \(X_{init} = \bigoplus a_i\) est importante. Chaque arête \(a_i \to b_i\) doit être "résolue". On peut résoudre une arête \(v \to w\) en échangeant la position \(i\) (où \(a_i=v\)) avec \(X\), de sorte que \(X\) prend la place de \(v\), et \(v\) devient le nouveau \(X\). On souhaite que \(b_i\) prenne la place de \(a_i\). On peut échanger \(a_i\) avec \(X\). Le coût est 1. La nouvelle somme XOR est \(a_i\). Le nombre minimal d'opérations est le nombre d'arêtes dans le graphe \(\bigcup_{i \in S} (a_i, b_i)\) plus le nombre de composantes connexes ne contenant pas \(X_{init}\), moins 1 si \(X_{init}\) est dans une composante non triviale. Si \(X_{init}\) n'est égal à aucun des \(a_i\) ou \(b_i\), il est une sorte de "joker" pour une des composantes. S'il n'y a pas de \(a_i\) ou \(b_i\) égal à \(X_{init}\) qui fait partie de ces composantes, alors une opération supplémentaire est nécessaire pour y "introduire" \(X_{init}\). Le nombre de composantes connexes est count(cc) où chaque cc est \(C_j\). Le coût est \(\sum_{j} (size(C_j) - 1)\) (pour chaque cycle, on a besoin d'une opération de moins que le nombre de nœuds). Non, la formule est : Nombre de positions \(i\) telles que \(a_i \neq b_i\) + Nombre de composantes connexes qui ne contiennent pas \(X\) dans leur support de valeurs. Si \(X\) lui-même n'est pas présent comme valeur dans \(a\) ou \(b\), alors il faut une opération supplémentaire pour "l'activer".

La formule est : le nombre d'indices \(i\) où \(a_i \neq b_i\), plus le nombre de composantes connexes dans le graphe \(G' = (V, E)\) où \(V=\{a_i\} \cup \{b_i\}\) et \(E=\{(a_i, b_i) \mid a_i \neq b_i\}\), moins 1 si la valeur \(X\) appartient à une de ces composantes connexes et qu'elle n'est pas un point fixe.

CF1713F Tableau Perdu

Tags: Construction, Mathématiques

Énoncé du Problème

On vous donne un tableau \(a\) indexé de 1 à \(n\). Une matrice \(b\) de taille \((n+1) \times (n+1)\) indexée de 0 est générée comme suit :

• Pour \(0 \le i \le n\), \(b_{i,0} = 0\).
• Pour \(1 \le i \le n\), \(b_{0,i} = a_i\).
• Pour \(1 \le i, j \le n\), \(b_{i,j} = b_{i,j-1} \oplus b_{i-1,j}\).

On vous donne les valeurs de la dernière colonne : \(b_{1,n}, b_{2,n}, \ldots, b_{n,n}\). Reconstruisez le tableau \(a\) satisfaisant les conditions, ou signalez l'impossibilité.

Approche

La relation de récurrence \(b_{i,j} = b_{i,j-1} \oplus b_{i-1,j}\) est une relation de récurrence de "chemin sur une grille" classique pour la somme XOR. En utilisant les conditions aux frontières \(b_{i,0}=0\) et \(b_{0,i}=a_i\), nous pouvons exprimer \(b_{i,j}\) comme une somme XOR de termes \(a_k\). Plus précisément, \(b_{i,j}\) est la somme XOR des \(a_k\) pour lesquels le chemin de \((0,k)\) à \((i,j)\) contribue à \(b_{i,j}\) via un nombre impair de chemins de \((0,k)\) à \((i,j)\) avec des pas vers le bas et vers la droite. Le nombre de chemins de \((0,k)\) à \((i,j)\) est \(\binom{(i-0)+(j-k)}{i-0} = \binom{i+j-k}{i}\).

En utilisant le théorème de Lucas, \(\binom{N}{K} \pmod 2 = 1\) si et seulement si \(K\) est un sous-ensemble binaire de \(N\) (c'est-à-dire que pour chaque bit \(m\), si le \(m\)-ième bit de \(K\) est 1, alors le \(m\)-ième bit de \(N\) est aussi 1). La relation peut être exprimée comme \(b_{i,j} = \bigoplus_{k=1}^j (\binom{i+j-k}{i} \pmod 2) \cdot a_k\).

Nous sommes intéressés par la dernière colonne \(b_{i,n}\). On peut reformuler les indices pour plus de commodité. Par exemple, indexer \(a\) de 0 à \(n-1\) et les \(b_{i,n}\) de 0 à \(n-1\). Alors, \(b_{i,n} = \bigoplus_{k=0}^{n-1} (\binom{i+(n-1-k)}{i} \pmod 2) \cdot a_{k+1}\). La relation \(\binom{N}{K} \pmod 2 = 1\) si et seulement si \((N \text{ AND } K) = K\) est cruciale. Ceci est une transformation linéaire par rapport à l'opération XOR, souvent appelée la transformation de Walsh-Hadamard ou plus spécifiquement la transformation de somme de sous-ensembles / somme de sur-ensembles (Subset/Superset Sum Convolution) sur les indices binaires.

En effet, la relation \(b_{i,j} = b_{i,j-1} \oplus b_{i-1,j}\) correspond à une convolution de type "somme de sous-ensembles" ou "somme de sur-ensembles" dans un contexte où les indices sont des différences. Pour des indices \(u, v\), si \(u \text{ AND } v = v\), alors \((u,v)\) contribue. La relation finale entre \(a\) et la dernière colonne \(b_{\cdot,n}\) est une transformation de ce type. Pour retrouver \(a\) à partir de \(b_{\cdot,n}\), nous devons appliquer la transformation inverse. Heureusement, pour l'opération XOR, la transformation inverse d'une somme de sous-ensembles est la somme de sous-ensembles elle-même (et de même pour la somme de sur-ensembles). Ainsi, il suffit d'appliquer deux fois la transformation de somme de sous-ensembles ou de sur-ensembles appropriée (une fois pour les indices \(i\) et une fois pour les indices \(n-j\)) pour retrouver le tableau \(a\).

La complexité de cette approche est \(O(N \log N)\) pour les transformations de sous-ensembles/sur-ensembles (par exemple, Fast Walsh-Hadamard Transform pour les convolutions XOR).

CF2021E Village Numérique

Tags: Programmation Dynamique, Optimisation de DP, Somme de Minkowski, Arbre de Kruskal Rebuild, Glouton

Énoncé du Problème

On vous donne un graphe avec \(n\) sommets et \(m\) arêtes, chaque arête ayant un poids. Vous devez sélectionner \(k\) sommets spéciaux. Ensuite, on vous donne \(q\) sommets "critiques", et chaque sommet critique doit être assigné à un sommet spécial par un chemin. Le poids d'un sommet critique est défini comme le poids maximal de l'arête sur le chemin qui le relie à son sommet spécial. Minimisez la somme des poids de tous les sommets critiques. Ce problème doit être résolu pour chaque \(k=1, 2, \dots, n\).

Contraintes :

• E1 : \(1 \le n,m \le 500\)
• E2 : \(1 \le n,m \le 5000\)
• E3 : \(1 \le n,m \le 2 \times 10^5\)

Approche

La minimisation du poids maximal sur un chemin suggère l'utilisation d'un Arbre de Kruskal Rebuild (Kruskal MST). Construisons l'arbre couvrant minimal du graphe. Ensuite, transformons-le en un arbre de Kruskal Rebuild. Dans cet arbre, les nœuds feuilles sont les sommets originaux du graphe. Les nœuds internes représentent des arêtes de l'arbre couvrant minimal, et le poids de chaque nœud interne est le poids de l'arête correspondante. Le chemin entre deux sommets originaux \(u,v\) dans le graphe, avec un maximum d'arête minimal, est le poids du plus haut ancêtre commun dans l'arbre de Kruskal Rebuild.

Avec cet arbre, le problème se ramène à : pour chaque nœud feuille (sommet critique), assigner un sommet spécial (qui est aussi une feuille) dans son sous-arbre, ou un ancêtre de son sous-arbre. Le coût d'assigner un sommet critique \(u\) à un sommet spécial \(s\) hors de son sous-arbre est le poids du plus bas ancêtre commun (LCA) entre \(u\) et \(s\).

Nous définissons un programme dynamique : soit \(dp_{u,j}\) le coût minimal pour couvrir tous les sommets critiques dans le sous-arbre de \(u\) en utilisant exactement \(j\) sommets spéciaux dans ce sous-arbre. La transition pour un nœud interne \(u\) avec ses enfants \(ls\) (left child) et \(rs\) (right child) est :

dp<sub>u, x+y</sub> = min(dp<sub>ls, x</sub> + dp<sub>rs, y</sub> + coût_supplémentaire)

Le coût supplémentaire est ajouté si un sous-arbre n'a pas de sommet spécial et doit être couvert par un sommet spécial externe au coût \(w_u\) (le poids du nœud \(u\)).

dp<sub>u, x+y</sub> = min {
    dp<sub>ls, x</sub> + dp<sub>rs, y</sub> + tot<sub>ls</sub> * w<sub>u</sub>  (si x=0 et y>0)
    dp<sub>ls, x</sub> + dp<sub>rs, y</sub> + tot<sub>rs</sub> * w<sub>u</sub>  (si x>0 et y=0)
    dp<sub>ls, x</sub> + dp<sub>rs, y</sub>                        (sinon)
}

où \(tot_i\) est le nombre de sommets critiques dans le sous-arbre de \(i\). Les valeurs initiales sont \(dp_{feuille, 0} = \text{nombre de critiques dans la feuille} \times w_{parent\_de\_feuille}\) et \(dp_{feuille, 1} = 0\).

Pour E2 (\(N=5000\)), la DP en \(O(N^2)\) est réalisable. La fusion des DP d'enfants prend \(\text{taille_sous_arbre_gauche} \times \text{taille_sous_arbre_droit}\) pour chaque nœud. La somme totale peut être \(O(N^2)\).

Pour E3 (\(N=2 \times 10^5\)), \(O(N^2)\) est trop lent. Il faut remarquer que chaque fonction \(dp_u\) (où \(dp_u(j) = dp_{u,j}\)) est une fonction convexe. La somme de Minkowski peut être utilisée pour combiner des fonctions convexes efficacement. La somme de Minkowski de deux fonctions convexes \(f\) et \(g\) est \( (f \boxplus g)(k) = \min_{i+j=k} (f(i)+g(j)) \). Pour \(dp_u\) c'est la somme de Minkowski de \(dp_{ls}\) et \(dp_{rs}\). Cette opération peut être faite en \(O(taille_gauche + taille_droite)\) si les fonctions sont représentées par leurs pentes. Une file de priorité peut être utilisée pour maintenir les pentes (ou les différences). La complexité de cette optimisation est \(O(N \log^2 N)\).

Alternativement, une approche gloutonne couplée à une structure de données telle qu'un Leftist Tree (arbre penché) peut résoudre le problème en \(O(N \log N)\) après une transformation de problème.

Implémentation (Kruskal Rebuild Tree + Convex Hull Trick / Leftist Tree)

Le code fourni utilise une approche similaire à la fusion de Dijkstra ou une file de priorité pour maintenir les valeurs des pentes de la DP convexe. Chaque nœud \(u\) de l'arbre de Kruskal Rebuild a une file de priorité qui stocke les "pentes" de sa fonction de coût. Lorsque deux sous-arbres sont fusionnés (par une arête de poids \(w\)), on met à jour les coûts. Pour une solution \(dp_u(j)\) du sous-arbre \(u\), si \(j\) sommets spéciaux sont choisis, le coût de tous les points critiques est \(dp_u(j)\). Si aucun sommet spécial n'est choisi (\(j=0\)), le coût est la somme de tous les points critiques du sous-arbre fois \(w_u\). Chaque fonction de coût \(dp_u\) est stockée comme une collection de points \((j, dp_{u,j})\). La file de priorité pour chaque ensemble \(id[u]\) stocke les coûts supplémentaires pour choisir le \(j\)-ième sommet spécial, triés par ordre croissant. La fusion de deux ensembles \(u\) et \(v\) consiste à prendre l'ensemble le plus petit et à le vider dans le plus grand. C'est l'essence du DSU (Disjoint Set Union) avec union par taille/rang, combiné avec une file de priorité.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <numeric>

// Type alias pour les entiers longs
typedef long long valeur_longue;

// Valeur d'infini pour les coûts
const valeur_longue INFINI = 1e18; // Augmenté pour éviter les débordements potentiels

// Nombre maximal de nœuds
const int MAX_NOEUDS = 200005;

// Variables globales
int nb_noeuds, nb_aretes, nb_points_critiques;
// identifiant[i] : l'ID de la composante connexe à laquelle le nœud i appartient actuellement
int identifiant[MAX_NOEUDS];
// est_critique[i] : true si le nœud i est un point critique, false sinon
bool est_critique[MAX_NOEUDS];
// parent[i] : parent du nœud i dans le DSU
int parent[MAX_NOEUDS];
// taille_composante[i] : nombre de nœuds dans la composante connexe i
int taille_composante[MAX_NOEUDS];
// taille_critiques[i] : nombre de points critiques dans la composante connexe i
int taille_critiques[MAX_NOEUDS];
// cout_total_critiques[i] : somme des couts des points critiques (ajustés) dans la composante i
valeur_longue cout_total_critiques[MAX_NOEUDS];
// files_priorite[i] : file de priorité pour la composante connexe i, stocke les couts marginaux
std::priority_queue<valeur_longue, std::vector<valeur_longue>, std::greater<valeur_longue> > files_priorite[MAX_NOEUDS];

// Structure pour représenter une arête
struct Arete {
    int u, v, poids;
    // Surcharge de l'opérateur < pour trier les arêtes par poids
    bool operator <(const Arete &autre) const {
        return poids < autre.poids;
    }
} liste_aretes[MAX_NOEUDS];

// Recherche du parent d'un élément dans le DSU
int trouver_parent(int i) {
    if (parent[i] == i)
        return i;
    return parent[i] = trouver_parent(parent[i]);
}

// Fusionne deux composants connexes
void fusionner_composantes(int u, int v) {
    // S'assurer que u est la composante avec la plus grande file de priorité
    if (files_priorite[identifiant[u]].size() < files_priorite[identifiant[v]].size()) {
        std::swap(u, v);
    }
    // Déplacer les éléments de la file de priorité de v vers u
    while (!files_priorite[identifiant[v]].empty()) {
        files_priorite[identifiant[u]].push(files_priorite[identifiant[v]].top());
        files_priorite[identifiant[v]].pop();
    }
    // Mettre à jour l'identifiant de la composante fusionnée
    identifiant[v] = identifiant[u];
}

// Fonction principale de résolution pour un cas de test
void resoudre_cas_test() {
    scanf("%d %d %d", &nb_noeuds, &nb_aretes, &nb_points_critiques);

    // Initialisation pour chaque cas de test
    for (int i = 1; i <= nb_noeuds; i++) {
        est_critique[i] = false;
        while (!files_priorite[i].empty()) {
            files_priorite[i].pop();
        }
    }

    // Lecture des points critiques
    for (int i = 1, x; i <= nb_points_critiques; i++) {
        scanf("%d", &x);
        est_critique[x] = true;
    }

    // Lecture des arêtes
    for (int i = 1; i <= nb_aretes; i++) {
        scanf("%d %d %d", &liste_aretes[i].u, &liste_aretes[i].v, &liste_aretes[i].poids);
    }
    // Tri des arêtes par poids croissant pour Kruskal
    std::sort(liste_aretes + 1, liste_aretes + nb_aretes + 1);

    // Initialisation du DSU et des structures pour chaque nœud
    for (int i = 1; i <= nb_noeuds; i++) {
        parent[i] = i;
        taille_composante[i] = 1;
        taille_critiques[i] = est_critique[i];
        files_priorite[identifiant[i] = i].push(0); // Coût initial de 0 pour 1 sommet spécial
        cout_total_critiques[i] = 0; // Somme initiale de 0
    }

    // Algorithme de Kruskal pour construire l'arbre de Kruskal Rebuild
    for (int i = 1; i <= nb_aretes; i++) {
        int racine_u = trouver_parent(liste_aretes[i].u);
        int racine_v = trouver_parent(liste_aretes[i].v);

        if (racine_u == racine_v) {
            continue; // Arête crée un cycle, ignorer
        }

        // Si les deux racines sont différentes, fusionner les composantes
        // Ajustement des coûts dans les files de priorité avant la fusion
        valeur_longue cout_racine_u = files_priorite[identifiant[racine_u]].top();
        files_priorite[identifiant[racine_u]].pop();
        valeur_longue ajustement_u = (valeur_longue)taille_critiques[racine_u] * liste_aretes[i].poids - cout_total_critiques[racine_u];
        files_priorite[identifiant[racine_u]].push(cout_racine_u - ajustement_u);
        cout_total_critiques[racine_u] += ajustement_u;

        valeur_longue cout_racine_v = files_priorite[identifiant[racine_v]].top();
        files_priorite[identifiant[racine_v]].pop();
        valeur_longue ajustement_v = (valeur_longue)taille_critiques[racine_v] * liste_aretes[i].poids - cout_total_critiques[racine_v];
        files_priorite[identifiant[racine_v]].push(cout_racine_v - ajustement_v);
        cout_total_critiques[racine_v] += ajustement_v;

        // Fusionner les files de priorité et les informations du DSU
        fusionner_composantes(racine_u, racine_v);
        parent[racine_u] = racine_v; // Mettre à jour le parent DSU

        // Mettre à jour la taille et le nombre de critiques de la nouvelle composante
        taille_composante[racine_v] += taille_composante[racine_u];
        taille_critiques[racine_v] += taille_critiques[racine_u];
        cout_total_critiques[racine_v] += cout_total_critiques[racine_u];
    }

    // Le nœud racine de l'arbre de Kruskal Rebuild est la racine de la composante contenant le nœud 1
    int racine_finale = trouver_parent(1);
    valeur_longue cumul_min_cost = 0;

    // Calculer les réponses pour k=1, 2, ..., n
    for (int k_val = 1; k_val <= nb_noeuds; k_val++) {
        cumul_min_cost += files_priorite[identifiant[racine_finale]].top();
        files_priorite[identifiant[racine_finale]].pop();
        printf("%lld ", cout_total_critiques[racine_finale] + cumul_min_cost);
    }
    printf("\n");
}

// Fonction main
int main() {
    int nb_tests;
    scanf("%d", &nb_tests);
    while (nb_tests--) {
        resoudre_cas_test();
    }
    return 0;
}

CF2003F Tortue et Trois Séquences

Tags: Programmation Dynamique, Optimisation de DP, Randomisation (Color-Coding)

Énoncé du Problème

Vous avez trois séquences : \(a_1, \ldots, a_n\), \(b_1, \ldots, b_n\), et \(c_1, \ldots, c_n\). Vous devez choisir une sous-séquence d'indices \(p_1, p_2, \ldots, p_m\) de \(1, \ldots, n\) telle que :

• \(a_{p_1} \le a_{p_2} \le \cdots \le a_{p_m}\) (la sous-séquence \(a\) est non décroissante).
• Tous les \(b_{p_i}\) sont distincts.

Trouvez la valeur maximale de \(\sum_{i = 1}^m c_{p_i}\).

Approche

Ce problème est une variation du problème de la plus longue sous-séquence croissante, avec des contraintes supplémentaires. La condition \(a_{p_1} \le \ldots \le a_{p_m}\) suggère de trier les éléments par \(a_i\) d'abord. La condition "tous les \(b_{p_i}\) sont distincts" ajoute une complexité, car cela ressemble à un problème de correspondance ou de sélection d'éléments distincts.

Une approche de programmation dynamique serait de trier les éléments par \(a_i\). Soit \(dp[i]\) la somme maximale de \(c_j\) en terminant la sous-séquence par l'élément \(i\). Le défi est la condition \(b_{p_i}\) distincts. Cela implique que nous ne pouvons pas simplement utiliser la valeur \(b_i\) comme état, car nous aurions besoin de connaître toutes les valeurs \(b\) utilisées précédemment. On peut utiliser une structure de données, comme un arbre de Fenwick ou un segment tree, pour suivre les maximums des \(dp\) valeurs pour différents \(b_j\) déjà utilisés. Cependant, l'intervalle de valeurs de \(b_j\) peut être grand. Une technique de compression de coordonnées pourrait être nécessaire pour les \(b_j\).

Après le tri par \(a_i\), l'itération à travers les éléments nous permet d'assurer la condition non décroissante de \(a\). Pour chaque élément \(i\), on cherche un \(j

Ce problème peut également être résolu avec une DP sur profil et une optimisation complexe, ou des techniques de randomisation comme le color-coding pour diviser le problème en sous-problèmes gérables.

CF208E Cousins de Sang / Cnoi2019 Arbre de Cèdre

Tags: DFS, Différences sur Arbre

Énoncé du Problème

Vous avez un arbre. Il y a deux types de requêtes :

• Trouver le \(k\)-ème ancêtre d'un nœud \(u\).
• Compter le nombre de descendants de \(u\) qui sont au \(k\)-ème niveau de profondeur (c'est-à-dire qui ont \(u\) comme \(k\)-ème ancêtre).

Les deux types de requêtes doivent être résolus en temps et en espace \(O(N+Q)\).

Approche

Nous pouvons traiter toutes les requêtes hors ligne.

Pour la première question : trouver le \(k\)-ème ancêtre de \(u\). Lors d'un parcours en profondeur (DFS) de l'arbre, nous maintenons un tableau ou une pile des ancêtres du nœud courant. Si le nœud courant \(x\) est à la profondeur \(d\), alors son \(k\)-ème ancêtre est l'élément à l'indice \(d-k\) dans ce tableau/pile. Nous pouvons stocker \(fa[dep] = x\) pour le \(x\) à la profondeur \(dep\). Lors du parcours, si une requête \((u, k)\) demande le \(k\)-ème ancêtre de \(u\), et que nous sommes sur \(u\), nous pouvons immédiatement trouver \(fa[dep_u - k]\).

Pour la deuxième question : compter le nombre de descendants de \(u\) qui sont au \(k\)-ème niveau de profondeur. Cela peut être résolu en utilisant une technique de différences sur l'arbre. Nous pouvons combiner les requêtes : pour un nœud \(u\), nous voulons savoir combien de ses descendants sont à la profondeur \(dep_u + k\). Pendant le DFS, nous maintenons un tableau count\_at\_depth\[d\] qui stocke le nombre de nœuds visités jusqu'à présent qui sont à la profondeur \(d\). Pour une requête \((u, k)\), quand nous entrons dans le sous-arbre de \(u\), nous enregistrons l'état actuel de count\_at\_depth. Après avoir visité tout le sous-arbre de \(u\), nous refaisons une lecture de count\_at\_depth. La différence count\_at\_depth\[dep\_u+k\] (après) - count\_at\_depth\[dep\_u+k\] (avant) nous donne le nombre de descendants de \(u\) à la profondeur \(dep_u+k\). Pour optimiser, nous pouvons utiliser un mécanisme de requêtes hors ligne. Chaque requête \((u, k)\) est stockée avec \(u\). 1. Un premier DFS pour précalculer les ancêtres (pour les requêtes de type 1) et pour préparer les requêtes de type 2. 2. Un second DFS pour traiter les requêtes de type 2. Pour chaque nœud \(x\) à la profondeur \(dep\):

• Lorsque nous visitons \(x\), nous incrémentons count\_at\_depth\[dep\].
• Avant de visiter les enfants de \(x\), pour chaque requête \((u, k)\) où \(u\) est le nœud \(x\), nous enregistrons la valeur actuelle de count\_at\_depth\[dep+k\].
• Après avoir visité tous les enfants de \(x\), pour chaque requête \((u, k)\) où \(u\) est le nœud \(x\), nous prenons la nouvelle valeur de count\_at\_depth\[dep+k\] et calculons la différence avec la valeur enregistrée. Cette différence est la réponse pour la requête.

Ceci est une approche classique. La complexité en temps est \(O(N+Q)\) car chaque nœud et chaque requête est traité un nombre constant de fois. La complexité spatiale est \(O(N+Q)\) pour stocker le graphe, les requêtes et le tableau count\_at\_depth.

Implémentation

#include <iostream>
#include <vector>
#include <utility> // Pour std::pair
#include <algorithm> // Pour std::fill

const int TAILLE_MAX_NOEUDS = 1e6 + 5; // Taille maximale pour les nœuds (N)

// Variables globales
int nb_noeuds, nb_requetes;
int ancetre_a_profondeur[TAILLE_MAX_NOEUDS]; // Stocke le nœud à une profondeur donnée dans le chemin courant
int compteur_profondeur[TAILLE_MAX_NOEUDS]; // Compte les nœuds à chaque profondeur
int resultats_requetes[TAILLE_MAX_NOEUDS]; // Stocke les réponses pour chaque requête
std::vector<int> adjacence[TAILLE_MAX_NOEUDS]; // Liste d'adjacence pour l'arbre
std::vector<std::pair<int, int> > requetes_ancetre[TAILLE_MAX_NOEUDS]; // {k, id_requete} pour les ancêtres
std::vector<std::pair<int, int> > requetes_descendant[TAILLE_MAX_NOEUDS]; // {profondeur_cible, id_requete} pour les descendants

// DFS pour trouver les k-èmes ancêtres et préparer les requêtes de descendants
void parcourir_arbre_ancetre(int noeud_courant, int profondeur_actuelle) {
    ancetre_a_profondeur[profondeur_actuelle] = noeud_courant; // Enregistrer le nœud actuel à sa profondeur

    // Traiter les requêtes d'ancêtres pour le nœud_courant
    for (const auto& req : requetes_ancetre[noeud_courant]) {
        int k_ancetre = req.first;
        int id_req = req.second;
        if (profondeur_actuelle >= k_ancetre) {
            // Le k-ème ancêtre existe
            resultats_requetes[id_req] = ancetre_a_profondeur[profondeur_actuelle - k_ancetre];
        } else {
            // Le k-ème ancêtre n'existe pas (par ex. pour k=0, c'est le nœud lui-même, mais dans ce cas, k est l'écart de profondeur)
            // Ou si on veut un ancêtre à une profondeur négative par rapport à la racine (implicitement ici, on veut le nœud à la profondeur k)
            // Le problème est de compter les descendants d'un nœud u qui ont u comme k-ème ancêtre,
            // donc ils sont à profondeur (profondeur_u + k). On n'utilise pas cette partie du code pour l'ancêtre direct ici.
            // Cette partie du code a été mal interprétée dans l'original.
            // Le code original utilise "in[x]" pour les requêtes sur x, mais ces requêtes sont sur les DESCENDANTS.
            // Donc 'in[a].push_back(make_pair(b, i))' signifie: pour le nœud 'a', je veux trouver un descendant 'b' niveaux plus profond.
            // La logique 'que[fa[dep - p.first]].push_back' est pour le COUNT des descendants.
            // Je dois adapter le code pour correspondre à la description des requêtes 1 et 2.

            // Le code original traite les requêtes (u,k) en 'in[a].push_back(make_pair(b, i))'
            // comme "combien de descendants de 'a' sont à profondeur (profondeur_a + b)".
            // Donc 'b' est la différence de profondeur (k-ème enfant).
            // Le nœud lui-même est considéré à profondeur 0 relative.
            // Si profondeur_actuelle - req.first < 0, cela signifie que le k-ème ancêtre est au-delà de la racine, donc n'existe pas.
            // Je vais ignorer cette partie, car le problème semble mélanger deux fonctions pour le même DFS.
            // Je vais réécrire le code avec une interprétation plus claire.
        }
    }
    
    // Ajout des requêtes de descendants à traiter plus tard avec les différences
    // req.first est la différence de profondeur 'k'
    for (const auto& req : requetes_descendant[noeud_courant]) {
        int profondeur_cible = profondeur_actuelle + req.first;
        int id_req = req.second;
        // On stocke les requêtes pour le nœud 'noeud_courant' sur la profondeur cible
        // que[parent_kth_descendant].push_back({profondeur_cible, id_req})
        // En fait, 'que' dans l'original est utilisé pour marquer une requête (profondeur, id_req)
        // qui doit être calculée pour un certain ancêtre.
        // Ici, j'utilise 'requetes_ancetre' comme des requêtes de comptage.
        // La première requête : u, k -> k-ème ancêtre de u.
        // La seconde requête : u, k -> nombre de descendants de u à profondeur (profondeur_u + k).

        // Pour la première requête, on peut la traiter directement dans ce DFS.
        // Pour la deuxième requête, on stocke la requête (profondeur_cible, id_req) dans une liste attachée au nœud 'noeud_courant'
        // qu'on traitera dans le deuxième DFS.
        requetes_ancetre[noeud_courant].push_back({profondeur_cible, id_req}); // Utilisons cette liste pour les requêtes de descendants
                                                                               // où 'k_ancetre' devient 'profondeur_cible'
    }

    // Parcourir les enfants
    for (int enfant : adjacence[noeud_courant]) {
        parcourir_arbre_ancetre(enfant, profondeur_actuelle + 1);
    }
}

// DFS pour calculer le nombre de k-èmes descendants en utilisant des différences sur l'arbre
void parcourir_arbre_descendant(int noeud_courant, int profondeur_actuelle) {
    // Pour toutes les requêtes attachées au noeud_courant (qui sont en fait des requêtes de comptage de descendants)
    // On retire la valeur avant d'incrémenter compteur_profondeur[profondeur_actuelle]
    for (const auto& req : requetes_ancetre[noeud_courant]) { // Utilisation des requetes_ancetre comme requetes_comptage
        int profondeur_cible = req.first;
        int id_req = req.second;
        if (profondeur_cible < TAILLE_MAX_NOEUDS) { // Éviter l'accès hors limites
            resultats_requetes[id_req] -= compteur_profondeur[profondeur_cible];
        }
    }

    compteur_profondeur[profondeur_actuelle]++; // Incrémenter le compteur pour la profondeur actuelle

    // Parcourir les enfants
    for (int enfant : adjacence[noeud_courant]) {
        parcourir_arbre_descendant(enfant, profondeur_actuelle + 1);
    }

    // Après avoir visité tous les enfants, on ajoute les valeurs
    for (const auto& req : requetes_ancetre[noeud_courant]) {
        int profondeur_cible = req.first;
        int id_req = req.second;
        if (profondeur_cible < TAILLE_MAX_NOEUDS) {
            resultats_requetes[id_req] += compteur_profondeur[profondeur_cible];
        }
    }
}


int main() {
    scanf("%d %d", &nb_noeuds, &nb_requetes);

    // Construction de l'arbre
    for (int i = 2, parent_val; i <= nb_noeuds; i++) {
        scanf("%d", &parent_val);
        adjacence[parent_val].push_back(i);
    }

    // Lecture et stockage des requêtes
    // Le code original : in[a].push_back(make_pair(b, i));
    // C'est la requête pour 'a', et 'b' est le 'k' dans "k-ième descendant"
    // 'que' dans l'original est utilisé pour stocker les requêtes de descendants pour un certain ancêtre.
    // 'dfs1' dans l'original fait un parcours pour les requêtes sur les ancêtres, et stocke les requêtes de comptage
    // pour 'que[fa[dep - p.first]]'. Donc 'p.first' est 'k' (la profondeur relative).
    // Mon interpretation du code original pour les requêtes :
    // - Première type de requête : u, k. Demander le k-ième ancêtre de u.
    // - Deuxième type de requête : u, k. Demander le nombre de descendants de u qui sont au k-ème niveau (profondeur relative k par rapport à u).
    //   Le code d'origine ne prend pas la première requête. Il traite seulement le second type de requête.
    //   Je vais donc réécrire la logique pour correspondre à la description du problème.
    //   La requête 'in[a].push_back(make_pair(b, i))' dans l'original signifie:
    //   "Pour le nœud 'a', je veux trouver combien de ses descendants sont 'b' niveaux plus bas."

    for (int i = 1, u_node, k_depth_diff; i <= nb_requetes; i++) {
        scanf("%d %d", &u_node, &k_depth_diff);
        // Ici, 'requetes_descendant' stocke {k_depth_diff, id_requete} pour le noeud 'u_node'
        requetes_descendant[u_node].push_back({k_depth_diff, i});
    }

    // Premier DFS pour collecter les informations sur les ancêtres et stocker les requêtes de comptage
    parcourir_arbre_ancetre(1, 0); // La racine est 1, profondeur 0

    // Deuxième DFS pour traiter les requêtes de comptage
    parcourir_arbre_descendant(1, 0);

    // Afficher les résultats
    for (int i = 1; i <= nb_requetes; i++) {
        // Le code original retourne ans[i]-1, ce qui suggère qu'il compte le nœud u lui-même.
        // Si la définition du k-ième descendant est un nœud à (profondeur_u + k),
        // et qu'on ne veut pas compter le nœud u, alors -1 est correct.
        printf("%d ", resultats_requetes[i] - 1); // -1 car il semble que le nœud u lui-même est compté si k=0
    }
    printf("\n");

    return 0;
}

CF2021D Boss, assoiffé

Tags: Programmation Dynamique

Énoncé du Problème

Étant donné une matrice \(A\) de taille \(n \times m\). Pour chaque ligne \(i\) de la matrice, vous devez choisir un intervalle \([l_i, r_i]\) et obtenir un profit de \(\sum_{j=l_i}^{r_i} A_{i,j}\). Les intervalles choisis doivent satisfaire les conditions suivantes :

• Pour \(2 \le i \le n\), les intervalles \([l_{i-1},r_{i-1}]\) et \([l_i,r_i]\) doivent se croiser (avoir au moins un élément en commun).
• Pour \(2 \le i \le n\), l'intervalle \([l_{i-1},r_{i-1}]\) ne doit pas contenir \([l_i,r_i]\).

Maximisez la somme des profits obtenus.

Approche

Ce problème est une application de la programmation dynamique sur des intervalles. Pour chaque ligne, nous devons choisir un intervalle optimal, en tenant compte des contraintes avec la ligne précédente. Soit \(dp[i][j][k]\) le profit maximum jusqu'à la ligne \(i\), où l'intervalle choisi pour la ligne \(i\) est \([j, k]\).

Les transitions pour \(dp[i][j][k]\) seraient basées sur \(dp[i-1][j'][k']\) pour tous les \([j',k']\) qui satisfont les conditions d'intersection et de non-contenance. Les préfixes sommes (ou sommes d'intervalles) peuvent être précalculés pour obtenir rapidement le profit d'un intervalle \([j,k]\) pour une ligne donnée.

Les contraintes d'intersection et de non-contenance peuvent être exprimées comme suit pour les intervalles \([l_{i-1},r_{i-1}]\) et \([l_i,r_i]\) : 1. Intersection : \(l_i \le r_{i-1}\) et \(l_{i-1} \le r_i\). 2. Non-contenance : Il faut que \([l_i,r_i]\) ne soit pas un sous-intervalle de \([l_{i-1},r_{i-1}]\). Cela signifie que soit \(l_i < l_{i-1}\), soit \(r_i > r_{i-1}\).

La DP directe avec l'état \(dp[i][j][k]\) est \(O(N \cdot M^4)\), ce qui est trop lent. Il faut optimiser les transitions. Les conditions d'intersection et de non-contenance peuvent être complexes. L'optimisation pourrait consister à ne pas stocker explicitement \(j\) et \(k\) dans l'état, mais plutôt les caractéristiques de l'intervalle de la ligne précédente qui sont pertinentes pour la ligne actuelle. Par exemple, stocker le profit maximal pour une ligne \(i-1\) qui se termine à \(r_{i-1}\) et commence à \(l_{i-1}\).

On peut reformuler la DP. Pour chaque ligne \(i\), on peut calculer le meilleur profit pour un intervalle \([l,r]\) en se basant sur les informations agrégées de la ligne \(i-1\). Soit \(dp[i][r]\) le profit maximal jusqu'à la ligne \(i\) où l'intervalle de la ligne \(i\) se termine à \(r\). On devrait aussi considérer le début \(l\). \(dp[i][l][r]\) est le profit maximal en ayant choisi \([l,r]\) pour la ligne \(i\). Pour calculer \(dp[i][l][r]\), on doit considérer \(\max(dp[i-1][l'][r'])\) pour tous les \([l',r']\) valides. Cela peut être optimisé avec des structures de données telles qu'un segment tree qui maintient les \(dp[i-1][l'][r']\) valeurs pour une \(i\) et différentes \(l', r'\) ou une DP bidimensionnelle avec des optimisations du style Convex Hull Trick ou Divide and Conquer Optimization. Une technique courante pour ces problèmes est de transformer le problème de choisir un intervalle \([l_i,r_i]\) en choisir un \(l_i\) et un \(r_i\). La dépendance d'une ligne à l'autre peut être traitée par des scans de gauche à droite ou de droite à gauche. Le problème est relativement complexe et nécessite des techniques d'optimisation de DP avancées, souvent avec l'aide de structures de données.

CF1707E Remplacer

Tags: Binary Lifting, Réflexion

Énoncé du Problème

Étant donnée une séquence \(a\) de longueur \(n\), où \(1 \le a_i \le n\). On définit une fonction binaire \(f\) comme suit : \[f((l,r)) = (\min\{a_l,\ldots,a_r\},\max\{a_l,\ldots,a_r\}) \quad (l \leq r)\] Vous devez répondre à \(q\) requêtes. Chaque requête donne un intervalle \((l_i,r_i)\) et demande le nombre minimal d'appels à \(f\) (c'est-à-dire \((l,r) \rightarrow f((l,r))\)) nécessaires pour transformer \((l_i,r_i)\) en \((1,n)\). Si c'est impossible, affichez \(-1\).

Approche

Soit \(f^k(l,r)\) l'intervalle résultant après \(k\) applications de la fonction \(f\) sur \((l,r)\). Nous cherchons le plus petit \(k\) tel que \(f^k(l,r) = (1,n)\). Puisque le nombre d'applications peut être grand, la technique de "binary lifting" (exponentiation binaire sur les fonctions) est appropriée. Nous précalculons \(f^{2^k}(l,r)\) pour différentes valeurs de \(k\). Pour chaque requête \((l,r)\), nous commençons par \(k\) le plus grand, et si \(f^{2^k}(l,r)\) est différent de \((1,n)\) et est plus "progressif" (par exemple, couvre plus de terrain), nous appliquons cette transformation et décrémentons \(k\). Cela nous donnera le nombre minimal d'étapes en \(O(\log N)\) pour chaque requête.

Cependant, le précalcul de \(f^k(l,r)\) pour tous les \(O(N^2)\) intervalles est trop coûteux. L'astuce réside dans une propriété cruciale : si un intervalle \([L,R]\) est la réunion de deux intervalles \([L_1,R_1]\) et \([L_2,R_2]\) qui se chevauchent (c'est-à-dire \([L_1,R_1] \cup [L_2,R_2] = [L,R]\) et \([L_1,R_1] \cap [L_2,R_2] \ne \emptyset\)), alors \(f^k([L_1,R_1]) \cup f^k([L_2,R_2]) = f^k([L,R])\). Cette propriété peut être prouvée par induction. Elle implique que nous n'avons pas besoin de calculer \(f^k\) pour tous les intervalles. Il suffit de précalculer \(f^k(i, i+1)\) pour tous les \(i\) de \(1\) à \(n-1\).

Pour chaque \(k\) et chaque \(i\), nous stockons l'intervalle \((L, R)\) qui est \(f^{2^k}(i, i+1)\). Pour une requête \((l,r)\), nous voulons trouver \(f^{2^k}(l,r)\). Nous pouvons le construire en prenant l'union des \(f^{2^k}(i,i+1)\) pour \(i \in [l, r-1]\). L'union de nombreux intervalles peut être coûteuse. Cependant, l'union des intervalles \([L_i,R_i]\) est simplement \((\min L_i, \max R_i)\). Donc, pour obtenir \(f^{2^k}(l,r)\), nous devons trouver \(\min_{j=l}^{r-1} (f^{2^k}(j,j+1)_L)\) et \(\max_{j=l}^{r-1} (f^{2^k}(j,j+1)_R)\). Ces minimums et maximums sur des intervalles peuvent être calculés rapidement en utilisant des requêtes de type RMQ (Range Minimum/Maximum Query), par exemple avec un Sparse Table.

L'algorithme final : 1. Précalculer \(f^0(i, i+1) = (i, i+1)\). 2. Pour \(k\) de \(0\) à \(\log N\): Pour chaque \(i\) de \(1\) à \(n-1\): Soit \((L_1, R_1) = f^{2^k}(i, i+1)\). Soit \((L_2, R_2) = f^{2^k}(i+1, i+2)\). Alors \(f^{2^{k+1}}(i, i+1) = (\min(L_1, L_2), \max(R_1, R_2))\). Non, ce n'est pas correct. \(f^{2^{k+1}}(i,i+1) = f^{2^k}(f^{2^k}(i,i+1))\). Ceci peut être calculé par une DP pour \((L_i^p, R_i^p)\) représentant \(f^{2^p}(i, i+1)\). Alors \((L_i^{p+1}, R_i^{p+1}) = (\min_{j=L_i^p}^{R_i^p-1} L_j^p, \max_{j=L_i^p}^{R_i^p-1} R_j^p)\). Ceci est une RMQ sur des intervalles d'indices. La construction d'une Sparse Table pour chaque niveau \(p\) prend \(O(N)\). Au total \(O(N \log N)\) pour le précalcul.

Pour chaque requête \((l,r)\): Appliquer le binary lifting. Soit \((cl, cr) = (l,r)\) et \(ans=0\). Pour \(p\) de \(\log N\) à \(0\): Si on applique \(f^{2^p}\) à \((cl, cr)\), on obtient \((nl, nr)\). On calcule \((nl,nr)\) comme \(\min_{j=cl}^{cr-1} L_j^p\) et \(\max_{j=cl}^{cr-1} R_j^p\). Si \((nl, nr)\) n'est pas \((1,n)\) et \((nl,nr)\) est "plus grand" que \((cl,cr)\) (e.g., \(nl\) plus petit ou \(nr\) plus grand, ou il englobe plus de terrain), on met à jour \((cl,cr) = (nl,nr)\) et \(ans += 2^p\). Si après tous les liftings, \((cl,cr) = (1,n)\), alors \(ans\) est la réponse. Sinon, \(-1\).

Le coût total est \(O(N \log N)\) pour le précalcul et \(O(Q \log^2 N)\) pour les requêtes (chaque requête nécessite \(O(\log N)\) étapes de binary lifting, et chaque étape de lifting nécessite une RMQ sur un intervalle, soit \(O(\log N)\) avec Sparse Table, ou \(O(1)\) avec RMQ précalculée).

CF1771F Hossam et Requête de Minimum par Intervalle

Tags: Arbre de Segments Persistant, Randomisation

Énoncé du Problème

Étant donnée une séquence \(a\), et \(q\) requêtes, trouvez le plus petit nombre qui apparaît un nombre impair de fois dans l'intervalle \([l,r]\).

Approche

La condition "apparaît un nombre impair de fois" est un signe typique pour l'utilisation de l'opération XOR. Si nous assignons un poids aléatoire \(w_x\) à chaque nombre \(x\), alors la somme XOR des poids de tous les nombres dans un intervalle \([l,r]\) sera non nulle si et seulement s'il existe au moins un nombre qui apparaît un nombre impair de fois dans cet intervalle. Si le XOR sum est 0, alors tous les nombres apparaissent un nombre pair de fois (avec une probabilité très élevée).

L'idée est d'utiliser un Arbre de Segments Persistant (PST). Un PST peut gérer des requêtes de somme sur des intervalles de valeurs, en supportant les modifications de points. Nous construisons un PST où chaque nœud représente un intervalle de valeurs possibles, et chaque chemin de la racine à une feuille représente la somme XOR des poids aléatoires pour les nombres dans l'intervalle correspondant de l'array original \(a\). Plus précisément, on construit un PST sur les indices de \(a\). Chaque version du PST (pour un préfixe \(a[1 \dots i]\)) représente les XOR-sommes des poids aléatoires des nombres dans ce préfixe. Pour un intervalle \([l,r]\), la somme XOR peut être obtenue en faisant XOR la version \(r\) du PST avec la version \(l-1\).

Pour répondre à la requête "le plus petit nombre qui apparaît un nombre impair de fois" : 1. Attribuez un poids aléatoire \(W_v\) (un entier long aléatoire, par exemple, 64 bits) à chaque valeur \(v\) qui apparaît dans la séquence \(a\). 2. Construisez un PST. Chaque nœud de l'arbre couvre un intervalle de valeurs \([X_{min}, X_{max}]\). Chaque feuille représente une valeur unique. Un nœud stocke la somme XOR des poids \(W_v\) des valeurs \(v\) dans son intervalle d'indices. 3. Pour chaque position \(i\) de la séquence \(a\), construisez une nouvelle version du PST en y ajoutant \(W_{a_i}\). Si \(a_i\) est une valeur qui était déjà présente, nous devons d'abord la retirer (XOR son poids) puis l'ajouter. Cela peut être géré en stockant les positions précédentes de chaque valeur. Plus simplement, un PST peut être construit pour les préfixes de \(a\). Chaque nœud de la PST représente un intervalle de VALEURS. Dans la version \(k\) du PST, le chemin jusqu'à une feuille val contient la somme XOR des poids aléatoires pour les occurrences de val dans a\[1...k\]. 4. Pour une requête \([l,r]\), on veut le plus petit \(v\) tel que XOR\_sum\_v(a\[l...r\]) != 0. On peut utiliser le PST pour interroger la somme XOR sur l'intervalle de valeurs \([1, V_{max}]\). Si cette somme XOR est non nulle, il existe au moins une valeur qui apparaît un nombre impair de fois. 5. Effectuez une recherche binaire sur l'intervalle de valeurs \([1, V_{max}]\). Si l'intervalle \([1, mid]\) a une somme XOR non nulle, alors le plus petit nombre est dans \([1, mid]\). Sinon, il est dans \([mid+1, V_{max}]\). Cette recherche binaire sur le PST prend \(O(\log V_{max})\) temps.

La probabilité d'erreur avec un poids aléatoire est très faible. Si on utilise plusieurs hachages aléatoires (par exemple, 2 ou 3), la probabilité d'erreur devient négligeable. Complexité : \(O((N+Q)\log V_{max})\) pour la construction du PST et les requêtes.

CF1746F Kazaee

Tags: Structures de Données, Randomisation

Énoncé du Problème

Vous devez supporter deux types d'opérations sur une séquence \(a\) :

• 1 i x : Mettre \(a_i\) à \(x\).
• 2 l r k : Demander si toutes les nombres dans l'intervalle \([l,r]\) apparaissent un nombre de fois qui est un multiple de \(k\).

Approche

Le problème de vérifier si toutes les fréquences sont des multiples de \(k\) est difficile à faire de manière déterministe avec des mises à jour rapides. La randomisation est la clé ici.

Assignons un nombre aléatoire \(R_x\) (par exemple, un entier long 64-bit) à chaque valeur \(x\) possible. Pour une requête 2 l r k, nous voulons vérifier si la fréquence de chaque nombre \(v\) dans \([l,r]\), notée \(count(v)\), est un multiple de \(k\). Si \(count(v)\) est un multiple de \(k\) pour tous les \(v\), alors la somme \(\sum_{v} count(v) \cdot R_v\) sera un multiple de \(k\). Si la somme \(\sum_{v} count(v) \cdot R_v\) est un multiple de \(k\), cela ne garantit pas que chaque \(count(v)\) est un multiple de \(k\). Cependant, si les \(R_v\) sont choisis aléatoirement et uniformément dans un grand intervalle, la probabilité que cette somme soit un multiple de \(k\) par accident est faible (\(1/k\)).

Pour augmenter la précision, nous pouvons répéter cette procédure plusieurs fois avec des ensembles de poids aléatoires différents. Par exemple, si nous utilisons 30 ensembles de poids aléatoires, la probabilité d'une fausse positive devient \((1/k)^{30}\), ce qui est très faible même pour \(k=2\).

Maintenant, comment maintenir la somme \(\sum_{v \in a[l \dots r]} R_v\) sous des mises à jour de points et des requêtes d'intervalle ? C'est un problème standard de segment tree. Chaque nœud de l'arbre stocke la somme des poids aléatoires pour l'intervalle qu'il couvre. 1. 1 i x : Mettre \(a_i\) à \(x\). Pour mettre à jour \(a_i\) à \(x\), nous devons soustraire \(R_{a_i^{\text{old}}}\) de la somme de tous les nœuds de segment tree contenant l'indice \(i\), puis ajouter \(R_x\). Cela prend \(O(\log N)\). 2. 2 l r k : Demander si toutes les fréquences sont des multiples de \(k\). Nous interrogeons le segment tree pour la somme \(S_{l,r} = \sum_{j=l}^r R_{a_j}\). Cela prend \(O(\log N)\). Si \(S_{l,r} \pmod k = 0\), nous répondons "Oui". Sinon, nous répondons "Non".

Comme nous devons répéter ceci 30 fois, la complexité totale sera \(O((N+Q) \cdot \text{nombre_de_repetition} \cdot \log N)\). Avec un nombre_de_repetition constant (par exemple 30 ou 60), c'est efficace.

CF1136E Nastya n'a pas écrit de Légende

Tags: Structures de Données, Arbre de Segments

Énoncé du Problème

Vous avez un tableau \(a\) de longueur \(n\) et un tableau \(k\) de longueur \(n-1\). Vous devez supporter 2 types d'opérations :

1. + i x : Affecte \(a_i \gets a_i + x\). Ensuite, si \(a_{i+1} < a_i + k_i\), alors \(a_{i+1} \gets a_i + k_i\) et l'indice effectif \(i\) est incrémenté à \(i+1\). Ce processus se répète tant que la condition est vraie.
2. s l r : Affiche la somme \(\sum_{j=l}^r a_j\).

Approche

Analysons l'opération de propagation : \(a_{j+1} < a_j + k_j \implies a_{j+1} \gets a_j + k_j\). Cette condition peut être réécrite : \(a_{j+1} - k_j < a_j\). Définissons une nouvelle séquence \(b_i = a_i - \sum_{p=1}^{i-1} k_p\). Soit \(K_i = \sum_{p=1}^{i-1} k_p\) (avec \(K_1=0\)). Donc \(b_i = a_i - K_i\). Alors la condition \(a_{j+1} - k_j < a_j\) devient \(a_{j+1} - (K_{j+1} - K_j) < a_j\). C'est équivalent à \(a_{j+1} - K_{j+1} < a_j - K_j\). Donc, la condition \(b_{j+1} < b_j\) déclenche la mise à jour \(b_{j+1} \gets b_j\). Cette observation est cruciale : lors d'une mise à jour, la valeur \(b_i\) est incrémentée. Puis, si \(b_{i+1} < b_i\), \(b_{i+1}\) est mis à jour à \(b_i\), puis \(b_{i+2}\) est mis à jour à \(b_{i+1}\) s'il est plus petit, et ainsi de suite. Cela signifie qu'un bloc de \(b_j\) à partir de \(i\) (disons jusqu'à \(J\)) sera mis à jour à la valeur de \(b_i\) (la nouvelle valeur de \(b_i\)). Plus précisément, si \(b_{i+1}\) est mis à jour à \(b_i\), il devient égal à \(b_i\). Ensuite, si \(b_{i+2} < b_{i+1}\) (maintenant égal à \(b_i\)), \(b_{i+2}\) est mis à jour à \(b_i\). Cela continue jusqu'à ce que \(b_J \ge b_{J-1}\) ou que nous atteignions la fin du tableau. Ainsi, l'opération + i x revient à : 1. Mettre à jour \(a_i \gets a_i + x\), ce qui implique \(b_i \gets b_i + x\). 2. Trouver l'indice maximal \(J \ge i\) tel que pour tout \(j \in [i, J]\), la nouvelle valeur de \(b_j\) devrait être la nouvelle valeur de \(b_i\). Ceci est équivalent à trouver le plus grand \(J\) tel que \(b_J < b_i^{\text{new}}\) (avant les mises à jour en cascade) pour tous les \(j \in [i+1, J]\). 3. Affecter la nouvelle valeur de \(b_i\) à tout l'intervalle \([i, J]\). Puisque les valeurs \(b_j\) sont mises à jour en cascade à la valeur de \(b_i\), et que \(b_i\) augmente, cela crée des segments où \(b_j\) est constant. Un segment tree (arbre de segments) peut gérer cela. Le segment tree stockera les valeurs \(b_i\). Pour l'opération de type 1 : 1. Calculez la nouvelle valeur de \(b_i\). 2. Effectuez une recherche binaire sur le segment tree pour trouver le plus grand indice \(J\) tel que \(b_J^{\text{old}} < b_i^{\text{new}}\). Cela peut être fait avec une requête sur l'arbre de segments. Le segment tree doit supporter les requêtes de maximum sur un intervalle, pour trouver le premier \(b_j \ge b_i^{\text{new}}\) à partir de \(i\). 3. Effectuez une mise à jour d'affectation d'intervalle sur \([i, J]\) dans le segment tree, en mettant tous les \(b_j\) de cet intervalle à \(b_i^{\text{new}}\). Les mises à jour par affectation d'intervalle et les requêtes de maximum sont des opérations standards pour un segment tree avec lazy propagation. Pour l'opération de type 2 (s l r) : Nous voulons calculer \(\sum_{j=l}^r a_j\). Puisque \(a_j = b_j + K_j\), la somme est \(\sum_{j=l}^r (b_j + K_j) = \sum_{j=l}^r b_j + \sum_{j=l}^r K_j\). La somme \(\sum_{j=l}^r K_j\) peut être précalculée (sommes de préfixes des \(k_j\)). La somme \(\sum_{j=l}^r b_j\) peut être obtenue par une requête de somme d'intervalle sur le segment tree. La complexité de chaque opération est \(O(\log N)\).

CF2025F Choisissez vos Requêtes

Tags: Réflexion, Théorie des Graphes

Énoncé du Problème

Initialement, vous avez \(n\) variables \(a_1, a_2, \ldots, a_n\) toutes à 0. Vous avez \(q\) opérations. Chaque opération donne deux indices \(x, y\). Vous devez choisir soit \(a_x\) soit \(a_y\) et l'incrémenter de 1 ou le décrémenter de 1. Vous devez vous assurer qu'à tout moment, la valeur de chaque variable reste non négative. Minimisez la somme de toutes les variables après \(q\) opérations.

Approche

Visualisons chaque opération \((x,y)\) comme une arête non orientée entre les nœuds \(x\) et \(y\) dans un graphe. À chaque opération, nous devons "orienter" cette arête : soit elle va de \(x\) à \(y\), et nous incrémentons/décrémentons \(a_y\), soit elle va de \(y\) à \(x\), et nous incrémentons/décrémentons \(a_x\). La contrainte \(a_i \ge 0\) à tout moment est importante. Cependant, le problème demande de minimiser la somme finale, ce qui est généralement atteint avec des valeurs finales de 0 ou 1. Si on incrémente \(a_i\), et il reste \(a_i=0\) à la fin, c'est optimal. Si on décrémente \(a_i\), et \(a_i\) est déjà 0, c'est impossible. Donc, il faut choisir d'incrémenter \(a_i\) pour maintenir \(a_i \ge 0\).

Considérons la valeur finale de chaque \(a_i\). Si une variable \(a_i\) est effectée \(D_i\) fois (où \(D_i\) est le degré d'entrée du nœud \(i\) si on pense aux arêtes orientées), alors sa valeur finale sera \(D_i \pmod 2\). Ceci est dû au fait que chaque paire d'opérations (incrémenter puis décrémenter, ou vice versa) s'annule si on ne se soucie pas de l'ordre. Mais on se soucie de l'ordre à cause de la contrainte de non-négativité. Si \(a_i\) a une entrée, on incrémente. Si elle a une autre entrée, on incrémente encore. Mais on peut aussi décrémenter. La condition de non-négativité force l'incrémentation si \(a_i=0\). L'objectif est de minimiser \(\sum a_i\). Si \(a_i\) est affecté \(D_i\) fois, sa valeur finale sera 1 si \(D_i\) est impair, et 0 si \(D_i\) est pair, sous des choix optimaux d'incrémentations/décrémentations pour maintenir la non-négativité. Par exemple, si on a trois opérations sur \(a_x\): \((x,y_1), (x,y_2), (x,y_3)\). On oriente vers \(x\). 1. \(a_x \gets a_x+1\) (maintenant 1). 2. \(a_x \gets a_x+1\) (maintenant 2). 3. \(a_x \gets a_x-1\) (maintenant 1). La valeur finale est 1.

Donc, le problème se réduit à minimiser le nombre de nœuds dont le degré d'entrée est impair. On peut traiter chaque composante connexe du graphe séparément. Pour chaque composante connexe, la somme des degrés de tous les nœuds est pair (somme des degrés = 2 * nombre d'arêtes). Si un nœud a un degré impair, pour qu'il devienne pair, il faut que d'autres nœuds changent leur parité. Dans un graphe non orienté, le nombre de sommets de degré impair est toujours pair. Ici, nous orientons les arêtes. Pour chaque arête \((x,y)\), elle contribue à un degré d'entrée de \(x\) ou de \(y\). Le degré d'entrée total pour tous les nœuds sera \(q\).

On peut atteindre une solution où au plus un nœud par composante connexe a un degré d'entrée impair. Construisons un arbre couvrant (DFS tree) pour chaque composante connexe. Pour toutes les arêtes de l'arbre qui ne sont pas des arêtes de l'arbre couvrant (back-edges), orientons-les arbitrairement. Par exemple, orientons-les vers le parent de l'arête. Ensuite, pour les arêtes de l'arbre couvrant, nous parcourons l'arbre de bas en haut (des feuilles vers la racine). Pour un nœud non-racine \(u\), et son parent \(p\), l'arête \((u,p)\) est la seule arête non encore orientée qui connecte \(u\) à l'extérieur de son sous-arbre. Le degré d'entrée de \(u\) (par les arêtes déjà orientées) est calculé. Si ce degré d'entrée est impair, nous orientons l'arête \((u,p)\) vers \(p\) (vers le parent), de sorte que \(u\) n'ait pas de degré d'entrée supplémentaire. Si le degré d'entrée de \(u\) est pair, nous orientons l'arête \((u,p)\) vers \(u\), de sorte que \(u\) ait un degré d'entrée supplémentaire et devienne impair. En remontant l'arbre de cette façon, tous les nœuds non-racines peuvent être forcés à avoir un degré d'entrée pair. La parité du degré d'entrée de la racine est alors déterminée par tous les choix faits pour ses enfants. Au final, seule la racine de chaque composante connexe peut potentiellement avoir un degré d'entrée impair.

La somme minimale des variables est donc le nombre de composantes connexes qui ont une racine avec un degré d'entrée impair.

CF1929F Sasha et l'Arbre Binaire de Recherche de Mariage

Tags: Combinatoire, Structures d'Arbre

Énoncé du Problème

Étant donné un arbre binaire de recherche (BST) où certains nœuds ont déjà une valeur attribuée, comptez le nombre de façons d'attribuer des valeurs (dans l'intervalle \([1,c]\)) aux nœuds restants. Contraintes : \(1 \le n \le 2 \times 10^5\), \(1 \le c \le 10^9\).

Approche

La propriété fondamentale d'un arbre binaire de recherche est que l'ordre des nœuds lors d'un parcours in-order (gauche, racine, droite) est un ordre croissant de leurs valeurs. Si nous effectuons un parcours in-order sur l'arbre donné, nous obtenons une séquence de nœuds. Certains de ces nœuds ont déjà une valeur, d'autres sont vides (valeur \(-1\)). Les valeurs des nœuds non vides forment une sous-séquence croissante dans la séquence in-order.

Considérons la séquence in-order. Nous avons des segments de nœuds non attribués (valeur \(-1\)). Soit un tel segment \([L, R]\) dans la séquence in-order. Soit \(V_{left}\) la valeur du nœud non-vide immédiatement avant \(L\) (si \(L\) n'est pas le premier nœud), et \(V_{right}\) la valeur du nœud non-vide immédiatement après \(R\) (si \(R\) n'est pas le dernier nœud). Les valeurs attribuées aux nœuds dans le segment \([L, R]\) doivent être strictement croissantes et comprises entre \(V_{left}\) et \(V_{right}\) (exclusif). Si \(L\) est le premier nœud, \(V_{left}\) peut être considéré comme 0. Si \(R\) est le dernier nœud, \(V_{right}\) peut être considéré comme \(c+1\).

Le problème se réduit à : combien de façons y a-t-il de choisir \(k\) nombres strictement croissants dans l'intervalle \((A, B)\) ? C'est un problème de combinaisons avec répétition, ou plus simplement, une combinaison. Si nous devons choisir \(k\) nombres strictement croissants \(x_1 < x_2 < \dots < x_k\) tels que \(A < x_1\) et \(x_k < B\), alors nous devons choisir \(k\) nombres distincts dans l'ensemble \(\{A+1, \ldots, B-1\}\). La taille de cet ensemble est \((B-1) - (A+1) + 1 = B-A-1\). Le nombre de façons de choisir \(k\) nombres distincts dans un ensemble de taille \(N'\) est \(\binom{N'}{k}\).

Donc, pour un segment de \(-1\)s de longueur \(len\) entre deux valeurs \(V_{left}\) et \(V_{right}\), le nombre de façons de les remplir est \(\binom{V_{right} - V_{left} - 1}{len}\). Le coût total est le produit de ces nombres de façons pour tous les segments de \(-1\)s. Les factorielles et leurs inverses modulo un grand nombre premier doivent être précalculés pour calculer \(\binom{N}{K}\) rapidement. Le nombre maximal de \(N\) peut être \(c\), mais le nombre maximal de \(len\) est \(n\). Puisque la somme des longueurs de tous les segments de \(-1\)s est au maximum \(n\), le calcul total des combinaisons prend \(O(N \log MOD)\) ou \(O(N)\) après précalcul des factorielles. La complexité totale est dominée par le parcours in-order \(O(N)\) et les calculs combinatoires \(O(N)\).

CF848C Au Revoir Souvenir

Tags: Structures de Données, Arbre d'Arbres, Décomposition par Blocs, Mo, Diviser pour Régner (CDQ)

Énoncé du Problème

Étant donnée une séquence \(a\) de longueur \(n\), où \(a_i\) représente la couleur du \(i\)-ème élément. La contribution d'une couleur dans un intervalle \([l,r]\) est définie comme la différence entre la dernière et la première apparition de cette couleur dans cet intervalle. Vous devez supporter deux types d'opérations : mise à jour d'un point (changer la couleur de \(a_i\)) et requête d'intervalle (somme des contributions de toutes les couleurs dans \([l,r]\)).

Contraintes : \(n,m \le 10^5\).

Approche

Le calcul direct de la contribution de chaque couleur dans un intervalle \([l,r]\) est difficile. Transformons la contribution. Pour une couleur donnée \(C\), si elle apparaît aux indices \(idx_1 < idx_2 < \dots < idx_p\) dans l'intervalle \([l,r]\), sa contribution est \(idx_p - idx_1\). Ceci peut être réécrit comme \((idx_p - idx_{p-1}) + (idx_{p-1} - idx_{p-2}) + \dots + (idx_2 - idx_1)\). Chaque terme \((idx_{j+1} - idx_j)\) est la distance entre deux apparitions consécutives de la même couleur. Soit \(prev_i\) l'indice de l'occurrence précédente de la même couleur que \(a_i\), si elle existe, et 0 sinon. Alors, la contribution totale est \(\sum_{i=l}^r (i - prev_i)\) pour tous les \(i\) tels que \(l \le prev_i < i \le r\) et \(a_{prev_i} = a_i\). Cette reformulation transforme le problème en une requête de somme sur des paires \((prev_i, i)\) où \(prev_i \ge l\), \(i \le r\), et \(a_i\) a une occurrence précédente à \(prev_i\).

Ceci est un problème de comptage de points dans une région 2D avec des mises à jour de points et des requêtes de région. Pour chaque paire \((prev_i, i)\) valide, nous avons un point \((prev_i, i)\) avec une valeur \(i - prev_i\). Une requête \([l,r]\) demande la somme des valeurs de tous les points \((x,y)\) tels que \(l \le x < y \le r\). C'est un problème de requête de somme rectangulaire.

Les solutions pour ce type de problème incluent :

1. **Arbre d'arbres (Segment Tree of Segment Trees)** : Un segment tree externe sur la première dimension (\(prev_i\)) et un segment tree interne sur la deuxième dimension (\(i\)). Chaque nœud de l'arbre externe contient un arbre interne qui gère les points de sa plage. Les mises à jour et requêtes sont en \(O(\log^2 N)\). La mémoire est \(O(N \log N)\) pour les versions persistantes ou \(O(N)\) si les arbres internes sont construits à la volée.
2. **Décomposition par Blocs (Square Root Decomposition)** : Divisez le tableau en \(\sqrt{N}\) blocs. Chaque bloc gère ses propres points. Les requêtes traversent les blocs. Les mises à jour prennent \(O(\sqrt{N})\) et les requêtes \(O(\sqrt{N})\). Complexité totale \(O((N+M)\sqrt{N})\).
3. **Hors ligne : Mo's Algorithm** : Si toutes les requêtes sont connues à l'avance et il n'y a pas de mises à jour de points, Mo's Algorithm peut résoudre cela en \(O((N+M)\sqrt{N})\). Avec des mises à jour de points, Mo's peut être étendu à \(O((N+M)N^{2/3})\).
4. **Hors ligne : Diviser pour Régner (CDQ Divide and Conquer)** : CDQ est une technique pour les problèmes de comptage 2D/3D. Elle peut traiter les mises à jour et les requêtes ensemble en \(O((N+M)\log N)\) en réduisant le problème à des sous-problèmes plus petits, puis en utilisant des structures de données simples comme des arbres de Fenwick.

Étant donné \(N, M \le 10^5\), une solution en \(O(\log^2 N)\) par requête/mise à jour est souvent attendue (arbre d'arbres ou segment tree 2D), ou une solution en \(O((N+M)\log N)\) pour une approche hors ligne comme CDQ.

CF364D Ghd

Tags: Randomisation, Brute Force

Énoncé du Problème

Étant donné un multiset \(A = \{a_1, a_2, \ldots, a_n\}\) de taille \(n\) (\(1 \le n \le 10^6\), \(1 \le a_i \le 10^{12}\)), trouvez la valeur maximale du plus grand commun diviseur (GCD) de tous les éléments d'un sous-ensemble dont la taille est strictement supérieure à \(n/2\).

Approche

Le problème demande le GCD maximal d'un sous-ensemble majoritaire. Si le sous-ensemble majoritaire existe et a un GCD \(G\), alors au moins \(\lfloor n/2 \rfloor + 1\) éléments du multiset \(A\) sont des multiples de \(G\). L'idée est d'utiliser la randomisation. Puisqu'il y a plus de \(n/2\) éléments qui sont multiples du GCD recherché, si nous choisissons un élément \(a_p\) au hasard dans \(A\), la probabilité que \(a_p\) fasse partie de ce sous-ensemble majoritaire est supérieure à \(1/2\).

L'algorithme proposé est le suivant : 1. Répétez un processus \(K\) fois (par exemple, \(K=10\) ou \(K=20\)) : a. Choisissez un indice \(p\) aléatoirement et uniformément dans \([1, n]\). b. Pour l'élément \(a_p\) choisi, trouvez tous ses diviseurs. La factorisation d'un nombre jusqu'à \(10^{12}\) peut être lente, mais trouver tous ses diviseurs peut être fait en \(O(\sqrt{a_p})\) ou plus rapidement en \(O(d(a_p))\) où \(d(a_p)\) est le nombre de diviseurs de \(a_p\). Les nombres avec le plus de diviseurs autour de \(10^{12}\) ont environ \(d(a_p) \approx 1344\) diviseurs (ex: \(720720^2\)). c. Pour chaque diviseur \(D\) de \(a_p\), comptez combien d'éléments dans le multiset \(A\) sont multiples de \(D\). Pour ce faire, il faut parcourir tout le tableau \(A\), ce qui est \(O(N)\). d. Si le nombre de multiples de \(D\) est \(\ge \lfloor n/2 \rfloor + 1\), alors \(D\) est un candidat valide pour le GCD. Mettez à jour le maximum GCD trouvé jusqu'à présent. 2. Le maximum parmi tous les candidats trouvés est la réponse.

La complexité de cette approche pour une seule itération est \(O(d(a_p) \cdot N)\) si on parcourt \(A\) pour chaque diviseur. C'est trop lent. Optimisation : Pour chaque \(a_p\) choisi : 1. Trouvez tous les diviseurs de \(a_p\). Stockez-les dans une liste. 2. Pour chaque diviseur \(D\), comptez son nombre d'occurrences comme GCD. 3. Pour chaque \(D\), on compte combien d'éléments \(a_j\) sont multiples de \(D\). C'est le même problème de comptage que ci-dessus. Mais on peut trier les diviseurs en ordre décroissant. Pour un \(a_p\) choisi : 1. Trouvez tous les diviseurs de \(a_p\), triez-les du plus grand au plus petit. 2. Pour chaque diviseur \(D\), parcourez le tableau \(A\) pour compter le nombre \(count_D\) d'éléments \(a_j\) tels que \(a_j \pmod D = 0\). Si \(count_D \ge \lfloor n/2 \rfloor + 1\), alors \(D\) est un candidat. Le premier \(D\) trouvé (le plus grand) est le meilleur pour ce \(a_p\). Ceci est \(O(d(a_p) + d(a_p) \cdot N)\), toujours trop lent.

Une meilleure optimisation pour l'étape 1.c : Pour un \(a_p\) choisi : 1. Trouvez tous les diviseurs de \(a_p\). Stockez-les dans une liste divisors\_list. 2. Pour chaque élément \(a_j\) dans \(A\), testez si \(a_j\) est divisible par les diviseurs de divisors\_list. Au lieu de parcourir \(A\) pour chaque diviseur, on peut parcourir \(A\) une seule fois et pour chaque \(a_j\), on trouve \(\text{GCD}(a_j, a_p)\) et on l'ajoute à une structure qui agrège les GCD. Une façon plus efficace pour l'étape 1.c: Pour un \(a_p\) choisi : 1. Obtenez tous les diviseurs de \(a_p\). 2. Pour chaque \(a_j \in A\), si \(a_j\) est un multiple de \(D\), incrémentez un compteur pour \(D\). Ceci est \(O(d(a_p) \cdot N)\) encore. L'astuce est de NE PAS parcourir \(A\) pour chaque diviseur. Au lieu de cela, pour chaque élément \(a_j\) du tableau, vérifiez si \(a_j\) est un multiple du diviseur \(D\). Pour un \(a_p\) choisi, on compte le nombre de multiples pour tous ses diviseurs : 1. Obtenez tous les diviseurs \(D_1, \dots, D_k\) de \(a_p\). 2. Pour chaque \(a_i \in A\), calculez \(g = \text{GCD}(a_i, a_p)\). On incrémente un compteur pour \(g\). 3. Ensuite, on utilise le principe d'inclusion-exclusion pour trouver, pour chaque diviseur \(D\) de \(a_p\), le nombre d'éléments de \(A\) qui sont des multiples de \(D\). Pour cela, on parcourt les diviseurs \(D\) de \(a_p\) du plus grand au plus petit. Pour chaque \(D\), le nombre d'éléments de \(A\) qui sont des multiples de \(D\) est la somme des compteurs pour tous les multiples de \(D\) parmi les diviseurs de \(a_p\). Cela prend \(O(d(a_p)^2)\) pour l'inclusion-exclusion et \(O(N \log a_{max})\) pour les GCD. Ou \(O(N \cdot d(a_p))\) pour une approche plus directe.

En pratique, \(d(X)\) est de l'ordre de \(X^{1/3}\) pour des nombres élevés. Un nombre avec \(10^{12}\) peut avoir au maximum environ 60 000 diviseurs. Le nombre d'itérations \(K\) est faible (par exemple, 10-20). La probabilité de ne pas choisir un élément du sous-ensemble majoritaire après \(K\) essais est \((1/2)^K\). Pour \(K=20\), c'est \(\approx 10^{-6}\). Pour un \(a_p\) choisi: 1. Trouver tous les diviseurs de \(a_p\), les trier. Cela prend \(O(\sqrt{a_p})\) pour les trouver et \(O(d(a_p) \log d(a_p))\) pour trier. 2. Pour chaque diviseur \(D\), compter le nombre d'éléments dans \(A\) qui sont multiples de \(D\). Pour faire cela efficacement, on ne parcourt pas \(A\) pour chaque \(D\). Plutôt, on a une std::map<long int="" long=""> counts qui, pour chaque \(D\), stocke le nombre d'éléments de \(A\) qui sont multiples de \(D\). Parcourir \(A\). Pour chaque \(a_j\), et pour chaque diviseur \(D\) de \(a_p\), si \(a_j \pmod D = 0\), incrémente \(counts[D]\). C'est \(O(N \cdot d(a_p))\), encore trop. Finalement, l'approche la plus efficiente par itération est : 1. Choisir \(a_p\). 2. Lister ses diviseurs. 3. Pour chaque diviseur \(D\), il faut savoir combien de \(a_i\) de l'input sont divisibles par \(D\). On peut trier l'input \(A\). Ou, on a une map std::map<long int="" long=""> freq\_divisors. Pour chaque \(a_j \in A\), on calcule \(\text{GCD}(a_j, a_p)\). C'est pas ça. L'approche standard est : pour un \(a_p\) choisi aléatoirement: 1. Obtenir les diviseurs de \(a_p\). 2. Pour chaque \(a_j\) dans le *tableau original A*, trouver \(\text{gcd_val} = \text{GCD}(a_j, a_p)\). 3. Pour chaque diviseur \(D\) de \(a_p\), créer un compteur \(cnt[D]\) et l'incrémenter pour chaque \(a_j\) tel que \(\text{GCD}(a_j, a_p)\) est un multiple de \(D\). 4. Ensuite, on utilise le principe d'inclusion-exclusion sur les diviseurs de \(a_p\) pour déduire les bons comptages. C'est encore \(O(N \cdot \text{log}(a_p))\) pour la boucle principale + \(O(d(a_p)^2)\) ou \(O(d(a_p) \log d(a_p))\) pour la passe sur les diviseurs.

Une complexité viable serait \(O(K \cdot (\sqrt{a_{max}} + N \log d(a_p)))\). En réalité, \(O(K \cdot (\sqrt{a_{max}} + N + d(a_{max}) \cdot \log d(a_{max})))\) est la complexité pratique pour trouver les diviseurs, puis compter les occurrences et finalement faire la "DP sur diviseurs". La complexité de l'étape de comptage d'occurrences pour tous les diviseurs d'un \(a_p\) est le goulot d'étranglement. Une solution pratique utilise souvent la structure des diviseurs.

CF1334F Fonction Étrange

Tags: Programmation Dynamique, Structures de Données

Énoncé du Problème

On définit une fonction \(f\) : \(f(x)\) est la sous-séquence des éléments \(x_i\) tels que \(x_i > \max\{x_1, x_2, \ldots, x_{i-1}\}\) (c'est-à-dire les éléments qui sont des maximums de préfixes stricts). Étant donné deux séquences \(a\) et \(b\), vous pouvez supprimer certains éléments de \(a\). La suppression de \(a_i\) coûte \(p_i\). Vous devez trouver le coût minimal pour que \(f(a) = b\), ou signaler l'impossibilité.

Contraintes : \(1\le n\le 5\cdot 10^5\).

Approche

Le problème de minimiser le coût de suppression est équivalent à maximiser le profit des éléments conservés. Les profits \(p_i\) peuvent être négatifs, ce qui signifie qu'il peut être avantageux de supprimer un élément même s'il ne viole aucune contrainte, s'il a un coût \(p_i < 0\).

Nous utilisons la programmation dynamique. Soit \(dp[j]\) le profit maximal pour former la séquence \(b\) jusqu'à \(b_j\). Pour construire la sous-séquence \(f(a)\) qui égale \(b\), nous devons trouver des éléments dans \(a\) qui correspondent aux éléments de \(b\) et respectent la condition de maximum de préfixe strict. Tri des éléments de \(a\) par valeur ou par indice est la première considération. Nous allons parcourir la séquence \(a\) de gauche à droite, en essayant de construire \(f(a)\).

Soit \(dp[idx\_b]\) le profit maximal après avoir fait correspondre \(b_{idx\_b}\) avec un \(a_i\). Pour chaque \(a_i\), nous avons deux choix : le supprimer ou le conserver. Si nous supprimons \(a_i\), le coût est \(p_i\). Si \(p_i\) est négatif, le "coût" de suppression est un gain \(|p_i|\). Si \(p_i\) est positif, c'est une perte \(p_i\). Si nous conservons \(a_i\), il peut potentiellement devenir un élément de \(f(a)\). Pour qu'il le devienne, \(a_i\) doit être strictement supérieur à tous les éléments conservés avant lui. Si \(a_i\) ne fait pas partie de \(f(a)\), il est considéré comme supprimé implicitement si \(p_i > 0\), et son profit n'est pas ajouté. Si \(p_i < 0\), il doit être supprimé explicitement.

Considérons la DP avec l'état \(dp[j]\) comme le coût maximal pour faire correspondre \(b_j\) comme le \(j\)-ième élément de \(f(a)\), en utilisant un préfixe de \(a\). Pour chaque \(a_i\), on parcourt les éléments de \(b\).

• Cas 1 : \(a_i < b_j\). Si on conserve \(a_i\), il ne peut pas être \(b_j\), et il ne peut pas être un maximum strict de préfixe pour \(b_j\) (car \(b_j\) doit être plus grand). On doit le supprimer. Le coût est \(p_i\).
• Cas 2 : \(a_i = b_j\). Si on conserve \(a_i\), il peut correspondre à \(b_j\). On cherche alors un \(k < i\) où \(a_k\) correspond à \(b_{j-1}\) et \(a_k < a_i\). La valeur de \(a_i\) contribue au profit (si \(p_i > 0\)). Si \(p_i < 0\), on doit le supprimer. Le profit est \(p_i + \max_{k 1. Cas 3 : \(a_i > b_j\). Si on conserve \(a_i\), il ne peut pas correspondre à \(b_j\). Il ne peut pas non plus être un maximum de préfixe pour un \(b_k, k \le j\). Il peut être un maximum de préfixe pour un \(b_k, k > j\), mais ce n'est pas le cas que nous traitons ici. Donc, il doit être supprimé. Le coût est \(p_i\).

L'état DP devrait être \(dp[j]\) : le coût maximal pour que \(f(a') = b[1 \dots j]\), où \(a'\) est une sous-séquence de \(a[1 \dots i]\). Il faut connaître la valeur du dernier élément de \(f(a')\) pour vérifier la condition de maximum strict. Cela rend la DP \(O(N \cdot M)\), où \(M\) est la longueur de \(b\), ce qui est trop lent car \(M\) peut être \(N\). Il faut optimiser la recherche du maximum précédent.

Optimisation avec une structure de données : On peut utiliser un segment tree ou un arbre de Fenwick pour stocker les valeurs \(dp[j]\). Pour chaque \(a_i\), on calcule une nouvelle valeur \(dp\_new[j]\). Soit \(P[j]\) le profit maximal pour avoir une sous-séquence \(b[1 \dots j]\) comme \(f(a)\) en utilisant un préfixe de \(a\) jusqu'à \(i-1\). Quand on considère \(a_i\): 1. **Ne pas prendre \(a_i\)** : Si \(p_i > 0\), cela coûte \(p_i\). On ajoute \(p_i\) à toutes les valeurs \(P[j]\). Si \(p_i < 0\), on ne le supprime pas, donc il ne coûte rien. Mais s'il était sélectionné, il serait un coût négatif. 2. **Prendre \(a_i\)** : Si \(a_i\) doit correspondre à \(b_j\), on cherche \(P[j-1]\). La logique est que tous les \(a_k\) avec \(k \text{last_element}\) et \(a_k \neq b_x\) sont traités comme supprimés. Nous allons itérer \(i\) de 1 à \(n\). Maintenons un segment tree qui stocke pour chaque \(j\) (indice de \(b\)) la valeur \(dp[j]\) (profit maximal pour avoir fait correspondre \(b_j\)). Pour chaque \(a_i\): a. Le coût de supprimer \(a_i\) (si \(p_i > 0\)) est ajouté à tous les \(dp[j]\) existants. (Mise à jour d'intervalle sur le segment tree). Si \(p_i < 0\), cela signifie qu'il est "libre" de ne pas être choisi, donc il ne doit pas ajouter de coût à tout le monde. Seuls les \(dp[j]\) qui ne prennent pas cet \(a_i\) comme maximum strict le payent. b. Si \(a_i\) est égal à un certain \(b_j\). Si \(p_i > 0\), on doit le payer. Si \(p_i < 0\), on est payé. Calculer \(new\_dp[j] = (\text{profit des éléments avant } a_i \text{ qui forment } b[1 \dots j-1]) + p_i\). Cela implique un maximum sur un certain intervalle. La condition \(a_i > \max\{x_1, \ldots, x_{i-1}\}\) est la plus difficile. Pour chaque \(a_i\), on maintient l'information du maximum des \(dp[j']\) pour \(j' < j\) où \(b_{j'} < a_i\). Cela peut être fait avec un segment tree. Un point dans le segment tree correspond à un \(b_j\). Pour chaque \(a_i\), nous mettons à jour les \(dp[j]\) : 1. Tous les \(dp[k]\) pour \(b_k < a_i\) sont mis à jour avec \(dp[k] = \max(dp[k], \text{quelque_chose})\). 2. Le coût \(p_i\) est ajouté à tous les \(dp[k]\) pour \(b_k \ge a_i\). (Propagation lazy sur segment tree). 3. Si \(a_i = b_j\), on essaie de mettre à jour \(dp[j]\) avec \(\max(dp[j-1]) + p_i\). Le \(\max(dp[j-1])\) est la valeur maximale des \(dp[j']\) où \(j'\) est le plus grand indice de \(b\) tel que \(b_{j'} < a_i\). L'algorithme se déroule comme suit : - Initialiser un segment tree sur les indices de \(b\) (de 0 à \(M\)). \(dp[0]=0\), les autres à \(-\infty\). - Pour \(i = 1 \dots n\): - Appliquer un décalage \(p_i\) sur l'intervalle \([0, \text{pos}(a_i)-1]\) du segment tree (où \(\text{pos}(v)\) est l'indice de \(v\) dans \(b\). Si \(v\) n'est pas dans \(b\), alors \(v\) ne peut pas correspondre à un \(b_j\).). - Pour l'élément \(a_i\): - Si \(a_i\) est une valeur qui apparaît dans \(b\), disons \(a_i=b_j\). Alors on peut potentiellement former \(b[1 \dots j]\) avec \(a_i\) comme dernier élément. Le profit pour \(dp[j]\) serait \(p_i\) plus le profit maximal pour avoir formé \(b[1 \dots j-1]\) en utilisant des éléments plus petits que \(a_i\). Cette valeur peut être trouvée en interrogeant le segment tree sur l'intervalle \([0, j-1]\) pour trouver le maximum. On met à jour \(dp[j] = \max(dp[j], \text{query_max}(0, j-1) + p_i)\). Le segment tree doit gérer les mises à jour de points, les mises à jour de plages (addition) et les requêtes de maximum de plages. Le temps est \(O(N \log M)\). ### CF1773I Deviner la Factorielle Interactive

Tags: Brute Force, Problème Interactif

Énoncé du Problème

Vous devez trouver un nombre \(n\) (\(1 \le n \le 5982\)). Vous pouvez effectuer au maximum 10 requêtes. Chaque requête consiste à demander la \(x\)-ième décimale de \(n!\).

Approche

Le nombre \(n\) est relativement petit (\(n \le 5982\)). La contrainte principale est le nombre très limité de requêtes (10). L'idée est de précalculer les factorielles de tous les nombres de 1 à 5982. Comme ces nombres peuvent être très grands, nous devons stocker leurs représentations en chaîne de caractères (ou de grandes entiers). Par exemple, \(5982!\) est un nombre avec environ \(21600\) chiffres.

Ensuite, pour chaque requête, nous demandons une décimale spécifique \(x\). Le but est de choisir les décimales \(x\) de manière stratégique pour distinguer les valeurs de \(n\) restantes. À chaque étape, nous avons un ensemble de valeurs de \(n\) possibles. Nous voulons faire une requête qui divise cet ensemble en sous-ensembles aussi équilibrés que possible. Par exemple, la première requête pourrait être la 1000ème décimale (ou toute autre position pertinente). On analyse les chiffres à une certaine position \(x\) pour toutes les factorielles précalculées. On choisit la position \(x\) qui a la plus grande diversité de chiffres ou qui permet de distinguer le plus grand nombre de \(n\) distincts.

Algorithme : 1. Précalculer \(n!\) pour \(n=1, \ldots, 5982\). Stocker chaque \(n!\) sous forme de chaîne de caractères. 2. Maintenir un ensemble possible\_n des valeurs de \(n\) qui n'ont pas encore été éliminées (initialement \(\{1, \ldots, 5982\}\)). 3. Pour chaque requête (jusqu'à 10 fois) : a. Pour chaque position \(x\) (par exemple, \(x\) allant de 0 à 21600), et pour chaque chiffre \(d \in \{0, \ldots, 9\}\), comptez combien de \(n \in \text{possible_n}\) ont le chiffre \(d\) à la position \(x\). b. Choisissez la position \(x^*\) et le chiffre \(d^*\) qui maximisent la division (par exemple, minimiser la taille du plus grand sous-ensemble après la requête). Ou, plus simple : choisissez \(x^*\) qui a le plus grand nombre de chiffres distincts parmi les \(n \in \text{possible_n}\). c. Envoyez la requête pour la \(x^*\)-ième décimale. Recevez la réponse \(R\). d. Mettez à jour possible\_n pour inclure seulement les \(n\) pour lesquels le \(x^*\)-ième décimale de \(n!\) est \(R\). e. Si possible\_n contient un seul élément, c'est la réponse.

Détails d'implémentation : - Les positions des décimales sont comptées à partir de la droite (unités = position 0). La \(x\)-ième décimale de \(n!\) signifie souvent le \(x\)-ième chiffre en partant de la gauche. Clarifions : "la \(x\)-ème décimale" signifie généralement la \(x\)-ème position en partant de la gauche. - La première requête peut être fixée à une position qui garantit une bonne division. Des tests montrent que demander une position comme 2000 ou 3000 (en partant de la gauche) est efficace. - Seules les premières milliers de décimales sont nécessaires. La plupart des nombres auront des chiffres distincts dans les premières 5000 positions.

CF351C Jeff et Parenthèses

Tags: Programmation Dynamique, Exponentiation Matricielle

Énoncé du Problème

Construisez une séquence de parenthèses valide de longueur \(n \times m\). À la position \(i\), placer une parenthèse ouvrante a un coût \(a_{i \pmod n}\), et une parenthèse fermante a un coût \(b_{i \pmod n}\). Minimisez le coût total de construction de la séquence de parenthèses.

Contraintes : \(1\le n\le 10^5\), \(1\le m\le 10^7\).

Approche

Ce problème est une variation du problème de génération de parenthèses valides avec des coûts. La longueur totale est \(N = n \times m\). Un problème de parenthèses valides peut être résolu avec un parcours de profondeur (DFS) ou une programmation dynamique où l'état est \((i, j)\), représentant la position actuelle \(i\) et le nombre de parenthèses ouvrantes non appariées \(j\).

Soit \(dp[i][j]\) le coût minimal pour construire un préfixe de longueur \(i\) avec \(j\) parenthèses ouvrantes non appariées. Les transitions sont : 1. Placer ( à la position \(i\): \(dp[i][j+1] = \min(dp[i][j+1], dp[i-1][j] + a_{i \pmod n})\). 2. Placer ) à la position \(i\): \(dp[i][j-1] = \min(dp[i][j-1], dp[i-1][j] + b_{i \pmod n})\). (Nécessite \(j > 0\)). La valeur \(j\) (nombre de parenthèses ouvrantes non appariées) ne peut pas dépasser \(N/2\). Ici, \(j\) peut aller jusqu'à \(n\). Le coût est \(O(N \cdot n)\) si on fait une DP directe. Avec \(N = n \cdot m\), c'est \(O(n^2 m)\), ce qui est trop lent pour \(m=10^7\).

Cependant, les coûts \(a_{i \pmod n}\) et \(b_{i \pmod n}\) se répètent tous les \(n\) positions. Cela suggère une optimisation par exponentiation matricielle. On peut définir un vecteur colonne \(V_i\) où \(V_i[j] = dp[i][j]\). La transition de \(V_{i-1}\) à \(V_i\) peut être représentée par une matrice \(T_i\). Puisque les coûts \(a\) et \(b\) se répètent, la matrice de transition \(T_i\) est la même pour \(i\) et \(i+n\). On peut calculer la matrice de transition pour un bloc de \(n\) positions. Soit \(M_{start\_j, end\_j}\) le coût minimal pour passer de \(start\_j\) parenthèses ouvrantes à \(end\_j\) parenthèses ouvrantes sur un bloc de \(n\) positions. On peut construire une matrice \(T\) de taille \((n+1) \times (n+1)\) où \(T[j_1][j_2]\) est le coût minimal pour passer de \(j_1\) parenthèses ouvrantes à \(j_2\) parenthèses ouvrantes sur \(n\) positions. Cette matrice \(T\) peut être calculée par une DP auxiliaire en \(O(n^3)\) : Soit \(C[k][j]\) le coût minimal pour passer de 0 parenthèses ouvrantes à \(j\) parenthèses ouvrantes après \(k\) étapes dans le bloc de \(n\). Pour calculer \(T\), on considère tous les états de départ \(j_1\) et d'arrivée \(j_2\) sur une période de \(n\) étapes. \(T[j_1][j_2] = \min_{j_{1, \dots, n-1}} (\sum \text{coûts des transitions})\). C'est une DP en \(O(n^3)\) pour la matrice, puis une exponentiation matricielle en \(O(n^3 \log m)\). Avec \(n=10^5\), \(O(n^3 \log m)\) est encore trop lent. Cela convient pour \(n\) petit, par exemple \(n \le 100\). Pour \(n=10^5\), une solution différente est nécessaire.

CF351C Jeff et Parenthèses (Optimisé)

Tags: Optimisation de DP

Énoncé du Problème

Les contraintes du problème précédent sont modifiées : \(1\le n\le 10^5\), \(1\le m\le 10^9\).

Approche

Les contraintes accrues \(n=10^5\) et \(m=10^9\) rendent l'exponentiation matricielle en \(O(n^3 \log m)\) impraticable. Nous avons besoin d'une solution en \(O(n \log n)\) ou \(O(n \log^2 n)\).

Le fait que la longueur totale \(N = n \times m\) puisse être gigantesque, mais que la période \(n\) soit "relativement" petite, est la clé. Le programme dynamique reste le même : \(dp[i][j]\) est le coût minimal pour un préfixe de longueur \(i\) avec \(j\) parenthèses ouvrantes non appariées. Les transitions sont : \(dp[i][j+1] = \min(dp[i][j+1], dp[i-1][j] + a_{i \pmod n})\) \(dp[i][j-1] = \min(dp[i][j-1], dp[i-1][j] + b_{i \pmod n})\) Les valeurs \(dp[i][j]\) sont des fonctions convexes de \(j\). La somme de Minkowski de deux fonctions convexes reste convexe. Les transitions ajoutent un coût constant ou décalent la fonction. La DP pour un bloc de \(n\) étapes, calculant \(T[j_1][j_2]\), peut être optimisée. Plutôt que de construire une matrice dense, on peut utiliser le fait que les fonctions \(dp[i][j]\) sont convexes. La fonction \(f_i(j) = dp[i][j]\) peut être représentée par ses pentes. Une transition d'un état à l'autre est une opération d'addition ou de min-plus convolution. La min-plus convolution de deux fonctions convexes peut être calculée en \(O(N_1+N_2)\) si elles sont représentées par leurs pentes. Pour une période de \(n\) étapes, on calcule la transformation \(f_i \to f_{i+n}\). Cette transformation peut être représentée par une fonction \(g(x) = \min_{y} (T[y][x] + \text{current_cost}(y))\). Les valeurs \(dp[j]\) sont les minimums sur les chemins dans un DAG de longueur \(n\). Un algorithme de type Dijkstra ou SPFA sur la fonction \(dp[j]\) par période de \(n\) peut être envisagé. Par exemple, \(dp[0][j]\) est l'état initial. Ensuite, on calcule \(dp[1][j]\), etc., jusqu'à \(dp[n-1][j]\). On peut utiliser un deque pour optimiser le calcul du minimum dans la convolution. Une approche avec Convex Hull Trick (CHT) ou Li Chao Tree peut être utilisée si la DP est de la forme \(dp[j] = \min(dp[k] + A \cdot k + B)\). La complexité \(O(N \log N)\) pour \(m\) grand est possible si la fonction de transition peut être appliquée \(m\) fois via une sorte de "multiplication" rapide de fonctions convexes. C'est une optimisation avancée de DP.

CF1380F Addition Étrange

Tags: Matrices, Structures de Données, DP Dynamique (DDP)

Énoncé du Problème

Pour des entiers non négatifs \(a,b\), leur "addition étrange \(\oplus\)" est définie comme suit : 1. Écrire \(a,b\) l'un au-dessus de l'autre, alignés par les chiffres les moins significatifs. 2. Additionner chaque paire de chiffres. 3. Concaténer les résultats de chaque chiffre, du plus significatif au moins significatif, pour obtenir \(a \oplus b\).

Exemple : \(a=1, b=2 \implies a \oplus b = "3"\). \(a=10, b=2 \implies a \oplus b = "12"\) (car \(1+0=1\) et \(0+2=2\)). Vous avez une chaîne de \(n\) chiffres \(c\) (\(0\sim 9\)). Il y a \(m\) opérations : - x d : Remplacer le \(x\)-ème chiffre de \(c\) par \(d\). Après chaque opération, affichez le nombre de paires ordonnées \((a,b)\) d'entiers non négatifs telles que \(a \oplus b = c\).

Approche

L'addition étrange signifie que s'il y a \(k\) chiffres, \(c_k c_{k-1} \dots c_0\), alors chaque paire de chiffres \(a_i, b_i\) de \(a\) et \(b\) (avec des zéros non significatifs si nécessaire) s'additionne pour donner le chiffre ou les deux chiffres de \(c\) à cette position. Par exemple, si \(c = "12"\), cela peut être \(a_0+b_0=1\) et \(a_1+b_1=2\) (produisant "12"), ou \(a_0+b_0=12\) (produisant "12"). Il n'y a pas de retenue entre les positions des chiffres. Si \(a_i+b_i = D\), et \(D \ge 10\), alors \(c\) à cette position aura les chiffres de \(D\). Donc, si \(c_i\) est un seul chiffre (0-9), il doit être le résultat de \(x+y=c_i\). Il y a \(c_i+1\) paires \((x,y)\) pour cela (de \((0,c_i)\) à \((c_i,0)\)). Si \(c_i c_{i+1}\) est un résultat à deux chiffres, par exemple \(c_i = 1\) et \(c_{i+1} = d\), cela signifie que \(x+y = 10+d\). Le nombre de paires \((x,y)\) pour \(x+y=V\) est \(V+1\) pour \(V<10\) et \(19-V\) pour \(V \ge 10\). Donc pour \(10+d\), c'est \(19-(10+d) = 9-d\).

Définissons un programme dynamique : \(dp[i]\) est le nombre de façons de former le préfixe \(c[1 \dots i]\) de la chaîne \(c\). Pour calculer \(dp[i]\) : 1. Le chiffre \(c_i\) est le résultat d'une somme à un chiffre \(x+y=c_i\). Il y a \(c_i+1\) façons. Cela ajoute \((c_i+1) \cdot dp[i-1]\) à \(dp[i]\). 2. Si \(c_{i-1}\) est '1', alors \(c_{i-1}c_i\) peut être le résultat d'une somme à deux chiffres \(x+y = 10+c_i\). Il y a \(9-c_i\) façons. Cela ajoute \((9-c_i) \cdot dp[i-2]\) à \(dp[i]\) (car \(c_{i-1}\) et \(c_i\) sont "consommés" ensemble).

La relation de récurrence est : \(dp[i] = (c_i+1) \cdot dp[i-1] + ([c_{i-1}=1] \cdot (9-c_i) \cdot dp[i-2])\). Conditions initiales : \(dp[0]=1\), \(dp[-1]=1\) (pour permettre \(dp[1]\) si \(c_0\) n'est pas 1, ou \(dp[0]\) si \(c_{-1}c_0\) est une paire).

Ceci est une DP linéaire. Chaque mise à jour x d change \(c_x\). Cela affecte \(dp[x]\) et \(dp[x+1]\). Si nous voulons la réponse après chaque mise à jour, nous ne pouvons pas refaire la DP à chaque fois. Cette récurrence peut être exprimée sous forme matricielle : \[ \begin{pmatrix} dp_i \\ dp_{i-1} \end{pmatrix} = \begin{pmatrix} c_i+1 & [c_{i-1}=1](9-c_i) \\ 1 & 0 \end{pmatrix} \begin{pmatrix} dp_{i-1} \\ dp_{i-2} \end{pmatrix} \] Non, c'est l'inverse : \[ \begin{pmatrix} dp_i \\ dp_{i-1} \end{pmatrix} = \begin{pmatrix} c_i+1 & [c_{i-1}=1](9-c_i) \\ 1 & 0 \end{pmatrix}^T \begin{pmatrix} dp_{i-1} \\ dp_{i-2} \end{pmatrix} \] Ou plus simplement : \[ (dp_i, dp_{i-1}) = (dp_{i-1}, dp_{i-2}) \times \begin{pmatrix} c_i+1 & 1 \\ [c_{i-1}=1](9-c_i) & 0 \end{pmatrix} \] Nous devons calculer le produit de \(n\) matrices \(2 \times 2\). Chaque matrice dépend des chiffres \(c_i\) et \(c_{i-1}\). Quand \(c_x\) est mis à jour, cela change la matrice \(M_x\) (dépend de \(c_x\)) et \(M_{x+1}\) (dépend de \(c_x\)). Un Segment Tree peut maintenir le produit de matrices sur des intervalles. Chaque nœud de l'arbre de segments stockera le produit des matrices de sa plage. Une mise à jour de point dans la séquence \(c\) implique la mise à jour de deux matrices dans le segment tree, ce qui coûte \(O(\log N)\) pour reconstruire les produits. Une requête de produit sur tout l'intervalle \([1, n]\) coûte \(O(\log N)\). La complexité totale est \(O((N+M)\log N)\).

CF1957F Désaccord de Fréquence

Tags: Randomisation, Arbre de Segments Persistant, Binary Lifting

Énoncé du Problème

Étant donné un arbre de \(n\) nœuds (\(1 \le n \le 10^5\)), chaque nœud ayant une couleur. Vous avez \(q\) requêtes. Chaque requête donne quatre nœuds \(u_1,v_1,u_2,v_2\) et un entier \(k\) (\(1 \le k \le 10\)). Trouvez \(k\) couleurs telles que la fréquence d'apparition de cette couleur sur le chemin de \(u_1\) à \(v_1\) est différente de sa fréquence sur le chemin de \(u_2\) à \(v_2\).

Approche

Ce problème combine des chemins sur un arbre, des fréquences de couleurs et une condition de "différence" qui est difficile à gérer directement. La randomisation, comme dans les problèmes précédents, est un excellent candidat.

Assignons un hachage aléatoire \(H_c\) à chaque couleur \(c\). Pour un chemin \(P\), nous pouvons calculer la somme XOR des hachages des couleurs présentes sur ce chemin. Soit \(XOR_P = \bigoplus_{c \in \text{path P}} H_c\). Si \(XOR_{P_1} \ne XOR_{P_2}\), il existe une couleur qui apparaît un nombre impair de fois plus souvent sur un chemin que sur l'autre (ou une couleur qui apparaît un nombre pair de fois sur un chemin et impair sur l'autre). Ce n'est pas suffisant. On veut que les fréquences soient différentes. Pour chaque couleur \(c\), assignons un hachage aléatoire \(H_c\). Alors, la somme pondérée \(\sum_{i \in P} H_{color(i)}\) est une valeur pour le chemin. La somme des fréquences de chaque couleur \(c\) multipliée par son hachage \(H_c\) est \(\sum_{c} freq_c(P) \cdot H_c\). Si \(\sum_{c} freq_c(P_1) \cdot H_c \ne \sum_{c} freq_c(P_2) \cdot H_c\), alors il existe au moins une couleur \(c\) dont \(freq_c(P_1) \ne freq_c(P_2)\). Si les \(H_c\) sont choisis aléatoirement, la probabilité d'une collision (les sommes sont égales alors que les fréquences sont différentes) est très faible.

Pour calculer \(\sum_{i \in P} H_{color(i)}\) sur un chemin d'arbre rapidement : Utilisez la décomposition en chemins lourds (HLD) ou une technique basée sur le plus bas ancêtre commun (LCA). Un chemin de \(u\) à \(v\) peut être décomposé en chemin de \(u\) à \(\text{LCA}(u,v)\) et de \(v\) à \(\text{LCA}(u,v)\). On peut utiliser un arbre de Fenwick ou un segment tree sur les temps d'entrée/sortie d'un DFS de l'arbre pour les requêtes de chemins. Pour la somme des hachages sur un chemin \((u,v)\), c'est \(\text{sum_pref}[u] \oplus \text{sum_pref}[v] \oplus \text{sum_pref}[\text{LCA}(u,v)] \oplus \text{sum_pref}[parent(\text{LCA}(u,v))]\) si on utilise des XOR-sums. Pour les sommes additives, c'est similaire : \(sum(u,v) = sum(root, u) + sum(root, v) - 2 \cdot sum(root, \text{LCA}(u,v)) + color(\text{LCA}(u,v))\). Ces sommes de préfixes peuvent être maintenues avec un Arbre de Segments ou un Arbre de Fenwick sur l'Euler Tour de l'arbre.

Pour trouver \(k\) couleurs spécifiques : 1. Choisissez \(R\) ensembles de hachages aléatoires \(H_c^{(1)}, \ldots, H_c^{(R)}\). ( \(R\) peut être 10 ou 20). 2. Pour chaque ensemble \(r\), calculez la somme pondérée \(S_1^{(r)}\) pour le chemin \((u_1,v_1)\) et \(S_2^{(r)}\) pour le chemin \((u_2,v_2)\). 3. Si \(S_1^{(r)} \ne S_2^{(r)}\) pour un ensemble \(r\), cela signifie qu'il existe une différence. Le problème demande \(k\) couleurs, pas seulement s'il y en a. Cela signifie qu'il faut les identifier.

Pour identifier les couleurs : On utilise un Arbre de Segments Persistant (PST) sur les valeurs de couleur. Chaque nœud de l'arbre stocke la somme des hachages des couleurs dans son intervalle de valeurs. Pour une requête \((u_1,v_1,u_2,v_2,k)\): 1. Calculez les chemins et leurs sommes de hachages : \(P_1 = \text{path}(u_1,v_1)\), \(P_2 = \text{path}(u_2,v_2)\). 2. Construisez un PST pour chaque chemin, représentant les fréquences des couleurs. 3. Pour trouver une couleur \(c\) telle que \(freq_c(P_1) \ne freq_c(P_2)\), on peut effectuer une recherche binaire sur le PST. Comparez la somme des hachages sur un intervalle \([1, MID]\) pour les deux chemins. Si les sommes diffèrent, la couleur est dans \([1, MID]\). Sinon, elle est dans \([MID+1, MAX\_COLOR]\). Répétez \(k\) fois. La complexité de cette approche serait \(O((N+Q)\log N \log C)\), où \(C\) est le nombre de couleurs uniques.

CF138D Monde de Darkraft

Tags: Théorie des Jeux, Programmation Dynamique

Énoncé du Problème

Vous avez un échiquier \(n \times m\) (\(1 \le n,m \le 20\)). Chaque case a une lettre (L, R, ou X). Initialement, toutes les cases sont blanches. Deux joueurs jouent à tour de rôle. À chaque tour, un joueur choisit une case blanche et : - Si la lettre est L, il noircit toutes les cases sur la diagonale allant du bas-gauche au haut-droit, ou du bas-droit au haut-gauche, jusqu'à la première case noire ou la frontière. - Si la lettre est R, il noircit toutes les cases sur la diagonale allant du haut-gauche au bas-droit, ou du haut-droit au bas-gauche. - Si la lettre est X, il noircit les deux types de diagonales. Le joueur qui ne peut plus choisir de case blanche perd. Déterminez si le premier joueur a une stratégie gagnante.

Approche

C'est un jeu impartial, qui peut être analysé avec les nombres de Grundy (ou fonction SG). Chaque état du jeu est la somme XOR des nombres de Grundy des sous-jeux. L'échiquier \(n \times m\) est petit. La clé est de comprendre comment une opération divise le jeu en sous-jeux. La particularité des mouvements est qu'ils sont diagonaux. Une transformation de coordonnées à 45 degrés peut simplifier le problème : Transformez \((i,j)\) en \((i+j, i-j)\). Ou plus généralement, \((i,j)\) en \((i+j, i-j+m)\) pour éviter les coordonnées négatives. Après cette transformation, les diagonales principales (constant \(i-j\)) deviennent des lignes horizontales, et les anti-diagonales (constant \(i+j\)) deviennent des lignes verticales. Une opération sur une case \((i,j)\) (qui devient \((x,y)\) après transformation) noircit un segment horizontal, vertical, ou les deux. Noircir un segment horizontal ou vertical divise le "rectangle" de cases blanches restantes en deux rectangles ou plus petits sous-rectangles (si on pense en termes de la grille transformée). Ce genre de jeu est un jeu Nim sur une grille où les mouvements sont des "coupes" rectangulaires. La fonction SG de ces jeux est connue. Les jeux de coupe sur une grille sont généralement calculés par DP sur des sous-rectangles. On peut diviser le problème en deux jeux indépendants : 1. Coloriez l'échiquier en noir et blanc comme un damier. Les mouvements sur les cases noires n'affectent que les cases noires, et les mouvements sur les cases blanches n'affectent que les cases blanches. (Ce n'est vrai que si les mouvements ne traversent pas de cases de couleurs différentes). Les mouvements de type L et R sont des mouvements diagonaux. Sur un damier, les cases sur une diagonale donnée sont toutes de la même couleur (si la diagonale va dans un sens) ou alternent de couleur (si elle va dans l'autre sens). Si on utilise la transformation \((i,j) \to (i+j, i-j)\), les cases avec \(i+j\) pair sont de même couleur, et les cases avec \(i+j\) impair sont de l'autre couleur. Un mouvement L (sur \(i-j\)) ou R (sur \(i+j\)) ne peut affecter que des cases d'une même parité de \(i+j\). Donc les jeux sont indépendants sur les cases avec \(i+j\) pair et \(i+j\) impair. Soit \(dp[x_1][y_1][x_2][y_2]\) le nombre de Grundy du sous-jeu défini par le rectangle des cases blanches \((x_1,y_1)\) à \((x_2,y_2)\) sur la grille transformée. Les dimensions de ce rectangle peuvent être jusqu'à \( (n+m) \times (n+m)\). Pour calculer \(dp[x_1][y_1][x_2][y_2]\) : Itérer sur toutes les cases \((x,y)\) à l'intérieur de ce rectangle. Si la case \((x,y)\) est L : On peut noircir un segment horizontal ou vertical. Ceci divise le rectangle en deux. Le nombre de Grundy de cette coupe est \(dp[x_1][y_1][x-1][y_2] \oplus dp[x+1][y_1][x_2][y_2]\). Ou \(dp[x_1][y_1][x_2][y-1] \oplus dp[x_1][y+1][x_2][y_2]\). On prend le Mex de toutes les possibilités de mouvements. La complexité de cette DP est \((N+M)^4 \times (N+M)^2\) pour calculer toutes les transitions, ce qui est trop lent. Pour ce problème, \(N,M \le 20\). La grille transformée a des dimensions autour de 40. Le nombre de Grundy peut être calculé par récursion avec mémoïsation. L'état peut être représenté par un masque de bits pour les lignes/colonnes. Les mouvements en L et R dépendent de la case choisie. Pour un jeu de type X, cela revient à prendre une case, et si elle est de couleur "paire", cela divise la grillle des cases paires en 4 sous-jeux (haut-gauche, haut-droit, bas-gauche, bas-droit), si elle est de couleur "impaire", la même chose pour les cases impaires. Le nombre de Grundy total est le XOR-somme du nombre de Grundy du sous-jeu "pair" et du sous-jeu "impair". Pour chaque sous-jeu, on calcule \(SG(mask)\) où \(mask\) est un masque de bits représentant les lignes et colonnes libres. C'est une DP par profil. L'état n'est pas un rectangle, mais un ensemble de lignes/colonnes disponibles. Une approche plus simple pour la grille \(N, M \le 20\) est de noter que les mouvements L et R sont des "coupes" le long de certaines lignes ou colonnes diagonales. On peut faire une DP sur des sous-ensembles de lignes/colonnes disponibles. Pour une grille de taille \(N \times M\), l'état peut être \(SG(mask\_rows, mask\_cols)\). La complexité serait \(2^N \cdot 2^M\), ce qui est trop grand. Mais les mouvements de type L et R ne "coupent" pas toutes les lignes/colonnes. Ils suivent les diagonales. L'état de la DP devrait être une description des frontières des régions blanches (lignes et colonnes). Le problème peut être résolu en utilisant la fonction SG pour des états définis par 4 coordonnées (pour un rectangle). Pour \(N, M \le 20\), les dimensions des rectangles sont \((i_1, j_1, i_2, j_2)\). Il y a \(N^2 M^2\) états. Chaque état requiert \(NM\) transitions. Total \(O(N^3 M^3)\). Pour le problème du damier, il y a deux jeux indépendants. Soit \(f(x_1, y_1, x_2, y_2)\) la fonction SG pour le rectangle \((x_1, y_1)\) à \((x_2, y_2)\). \[ f(x_1, y_1, x_2, y_2) = \text{MEX} \{ f(x_1, y_1, x-1, y_2) \oplus f(x+1, y_1, x_2, y_2) \mid x \in [x_1,x_2] \text{ et move est vertical} \} \cup \{ f(x_1, y_1, x_2, y-1) \oplus f(x_1, y+1, x_2, y_2) \mid y \in [y_1,y_2] \text{ et move est horizontal} \} \] Le calcul est pour les cases de même parité. Pour chaque case \((x,y)\) dans le rectangle, si elle est de type 'L' ou 'R' ou 'X', elle offre des options pour les coupes. Le premier joueur gagne si \(SG_{pair} \oplus SG_{impair} \ne 0\). Sinon, il perd. La complexité est \(O((N+M)^6)\) après la transformation, ce qui est \(40^6\), trop lent. La taille des rectangles est plutôt \(N \times M\) (maximum 20x20). La complexité de la DP est \(O((NM)^3)\) pour chaque couleur, donc \(2 \cdot (20 \cdot 20)^3 = 2 \cdot 400^3 \approx 1.28 \cdot 10^8\), ce qui peut passer. L'état doit être un rectangle de cases blanches. Pour chaque rectangle, pour chaque case de ce rectangle, le type de mouvement (L, R, X) définit les coupes possibles. Les coordonnées sont \(0 \ldots N-1\) et \(0 \ldots M-1\). La transformation est \((i,j) \to (i+j, i-j+M-1)\). Le plan est : 1. Séparer le plateau en deux jeux : cases où \(i+j\) est pair, et cases où \(i+j\) est impair. 2. Pour chaque jeu, calculer \(SG(min\_x, min\_y, max\_x, max\_y)\) pour tous les rectangles possibles. - Les \(x,y\) sont les coordonnées transformées. - Boucler sur \(min\_x, min\_y, max\_x, max\_y\). - Pour chaque rectangle, boucler sur les cases \((cur\_x, cur\_y)\) à l'intérieur. - Si la case \((cur\_x, cur\_y)\) correspond à une case originale \((i,j)\) du type correct (selon la parité de \(i+j\)) et avec une lettre (L, R, X), alors : - Si L, calculer les SG pour les divisions horizontales/verticales. - Si R, calculer les SG pour les divisions horizontales/verticales. - Si X, les deux. - Stocker le MEX de tous ces SG. 3. Le résultat est \(SG_{pair}(rect_{initial}) \oplus SG_{impair}(rect_{initial})\). Le premier joueur gagne si ce XOR-somme est non nul.