•

Prologin 2022
•

•
•

•
•

Concours National d’Informatique

Correction de la phase de sélection
 Correction des qualifications Prologin 2022
Valérian Fayt, Kenji Gaillac, Quentin Rataud,
Célian Raimbault, Mélanie Tchéou, Theophane Vallaeys∗

1er juillet 2022

Table des matières

0 Questionnaire 3
0.1 Question 1 : Bibliothèque de Babel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
0.2 Question 2 : 50 nuances de bleu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
0.3 Question 3 : Disque mystérieux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
0.4 Question 4 : Délicieux paquets IP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
0.5 Question 5 : C’est même pas un opérateur ! . . . . . . . . . . . . . . . . . . . . . . . . 4
0.6 Question 6 : Girls Can Code ! c’est trop bien ! . . . . . . . . . . . . . . . . . . . . . . . 5
0.7 Question 7 : Oups, la boulette . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
0.8 Question 8 : Un lundi pas comme les autres . . . . . . . . . . . . . . . . . . . . . . . . 5
0.9 Question 9 : Hors de question que je compte ça . . . . . . . . . . . . . . . . . . . . . . 6
0.10 Question 10 : Meow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
0.11 Question 11 : Prolozoo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
0.12 Question 12 : Les questions ne veulent plus rien dire . . . . . . . . . . . . . . . . . . . 7
0.13 Question 13 : C’est un langage ça ?! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
0.14 Question 14 : roff ? C’est un cri de désespoir ? . . . . . . . . . . . . . . . . . . . . . . . 8
0.15 Question 15 : J’en ai ma claque des anniversaires . . . . . . . . . . . . . . . . . . . . . 8
0.16 Question 16 : J’y vois que dalle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1 Sur les ondes 10

1.1 Énoncé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2 Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3 Implémentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2 Dernière pièce 11
2.1 Énoncé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3 Implémentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

3 Enter The Matriks 12

3.1 Énoncé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.2 Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.2.1 Approche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.2.2 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.2.3 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.3 Implémentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
∗
Pour l’équipe des correcteurs 2022 : Amélie Bertin, Kenji Gaillac, Quentin Rataud, Célian Raimbault, Katia Shang

1
4 Fuite de clavier 16
4.1 Énoncé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.2 Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.2.1 Initialisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.2.2 Mise à jour . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.2.3 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.3 Implémentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

5 Coffre-fort 19
5.1 Énoncé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.1.1 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.2 Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.2.1 Stratégie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.2.2 Plus petit ancêtre commun . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5.3 Implémentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

6 Coffre électronique 24
6.1 Énoncé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
6.1.1 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
6.2 Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
6.2.1 Transformer le graphe en arbre . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
6.2.2 Chemins lourds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
6.2.3 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
6.3 Implémentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2
0 Questionnaire
0.1 Question 1 : Bibliothèque de Babel
Énoncé Dans une bibliothèque hexagonale, nous avons caché un marque-page avec écrit ”prolo-
gin30ans” dessus. Quel mot figure sur la page marquée ?
— Prologue
— Prolojin
— Prologuigne
— Prologingue
— Trologin
— Prolongue

Correction La bibliothèque hexagonale dont nous parlions était la « Bibliothèque de Babel », que
vous pouvez retrouver ici.

Il fallait chercher le marque-page nommé prologin30ans :

https://libraryofbabel.info/bookmark.cgi?prologin30ans.

En cherchant sur la page, on retrouve le mot : Prologingue.

0.2 Question 2 : 50 nuances de bleu

Énoncé D’après l’algorithme d’analyse de couleur dans les documents HTML du navigateur Nets-
cape, à quelle couleur correspond la chaîne ”HAPPY BIRTHDAY” ?
— #CDDAFB
— #ABCDEF
— #6A7FB1
— #A0B0DA
— #507BE5
— #7792D6

Correction La première étape est de retirer des codes héxadécimaux, les croisillons si existants, et
dans la chaîne, remplacer tout caractère non hexadécimal avec des 0. HAPPY BIRTHDAY devient
0A0000B0000DA0.

Ensuite, en fonction de la taille de la chaîne de caractères :

— Taille de 1 ou 2 : on ajoute du padding à droite avec des 0 pour obtenir 3 caractères. On passe
à l’étape d’une taille de 3.
— Taille de 3 : chaque élément est pris comme valeur de respectivement rouge, vert et bleu, en
ajoutant un 0 devant chacune. Terminé.
— Taille de 4 ou plus : on ajoute du padding à droite pour obtenir la prochaine taille de chaîne qui
est multiple de 3.
On a une chaîne de 14 caractères, le multiple de 3 supérieur le plus proche étant 15, on lui ajoute
un 0. 0A0000B0000DA0 devient 0A0000B0000DA00.

La chaîne est découpée en 3 morceaux de tailles identiques, représentant chacun les valeurs rouge,
vert et bleu (de gauche à droite). On obtient ”0A000” en rouge, ”0B000” en vert et ”0DA00” en
bleu. Les chaines de 6 caractères sont terminées.

3
 On considère maintenant les chaines de chaque couleur individuellement. Les chaines individuelles
de plus de 8 caractères sont tronquées à 8 caractères en partant de la gauche.

Ensuite, les 0 de tête communs aux 3 chaines sont supprimés. On obtient ”A000” en rouge, ”B000”
en vert et ”DA00” en bleu.

On répète l’opération avec les 0 de fin de chaîne : les chaines sont tronquées en partant de la droite
à 2 caractères. On obtient ”A0” en rouge, ”B0” en vert et ”DA” en bleu, c’est à dire #A0B0DA

0.3 Question 3 : Disque mystérieux

Énoncé
— PROLOGIN30YEARS
— PROLOGIN30ANS
— JOYEUXANNIVERSAIRE
— PROLOGIN
— 30YEARS
— 30ANS

Correction Pas grand chose à faire pour cette question, il suffisait de cliquer plein de fois sur le
disque. Il s’agit d’un dessin SVG contenant du JavaScript, affichant un texte différent à chaque clic.
Certains petits malins pouvaient directement trouver la réponse en regardant directement le code Ja-
vaScript.

Le texte caché était : 30YEARS.

0.4 Question 4 : Délicieux paquets IP

Énoncé Dans le protocole expérimental IP over Burrito Carriers quel champ remplace le champ
”Donnée” du protocole IP ?
— Tomate
— Guacamole
— Bœuf
— Oignon
— Salade
— Riz

Correction « IP over Burrito Carriers » est une Draft RFC 1 publiée comme un poisson d’avril en
2005 que vous pouvez retrouver ici.

À la page 3 vous pourrez retrouver la réponse : Bœuf.

0.5 Question 5 : C’est même pas un opérateur !

Énoncé Quel est l’opérateur burlesque connu sous le nom de ”goes to” en C ?
— -->
— <-->
— <--
1. Request For Comments

4
 — <-
— ->
— <->

Correction La réponse attendue était : -->. Vous pouvez retrouver des mentions à cet « opérateur »
sur Stack Overflow ou encore Reddit.

Tu avais remarqué qu’en fait il s’agissait de l’opérateur -- et de l’opérateur > ?

0.6 Question 6 : Girls Can Code ! c’est trop bien !

Énoncé Quel est le type de la première variable nommée dans l’article page 21 de l’édition Septembre
2021 de Strasbourg Magazine ?
— Un tableau à deux dimensions
— Une instance de NullPointerException
— J’ai pas lu l’article
— Une chaîne de caractères
— Un entier
— Un tableau à une dimension

Correction En consultant le Strasbourg Magazine no 318 (Septembre 2021), on trouve à la page 21

un article parlant d’une autre initiative de l’association : les stages Girls Can Code !, qui ont pour but
d’initier les collégiennes et lycéennes à la programmation en Python !

L’article commence par du code Python : cur_grid[input_y][input_x] = p1_symbol.

En réfléchissant un peu sur le type potentiel de la variable cur_grid, il semblerait qu’il s’agisse
d’un tableau à deux dimensions et que l’on tente d’accéder à l’élément en position (x, y).

0.7 Question 7 : Oups, la boulette

Énoncé En 2008, on a découvert une vulnérabilité critique dans le paquet OpenSSL sur Debian.
Pourquoi ce bug n’a touché que les distributions basées sur Debian ?
— Debian utilisait une version beta du paquet
— L’attaquant qui a introduit ce bug a volontairement ciblé Debian
— Personne n’a jamais su
— Un mainteneur Debian a modifié une ligne à laquelle il ne fallait pas toucher
— Le cycle de mise à jour est plus lent que sur d’autres distributions
— Le flag de compilation empêchant ce bug n’est pas disponible sur Debian

Correction La réponse attendue était : Un mainteneur Debian a modifié une ligne à laquelle
il ne fallait pas toucher. Vous pouvez retrouver plus de détails sur cette vulnérabilité dans cet article.

0.8 Question 8 : Un lundi pas comme les autres

Énoncé Quel jour de la semaine a eu le privilège de connaître la création de l’association ?
— Mercredi
— Vendredi
— Samedi
— Mardi
— Lundi
— Jeudi

5
Correction D’après le JOAFE 2 , l’association a été fondée le lundi 20 janvier 1992. Vous pouvez
retrouver l’annonce en ligne.

0.9 Question 9 : Hors de question que je compte ça

Énoncé Combien d’associations ont été créées (en France) le même jour que Prologin ?
— 42
— 238
— 391
— 217
— 124
— 442
— Je ne sais pas

Correction La réponse attendue était : Je ne sais pas, on n’attendait pas de vous que vous les
comptiez enfin !

Je plaisante, la vraie réponse était 238. Vous pouviez compter le nombre d’associations créées le
même jour (20 janvier 1992) en vous référant aux données publiées par la DILA 3 que vous pouvez
retrouver ici.

0.10 Question 10 : Meow

Énoncé En quelle année, TTY devient-elle la première mascotte de Prologin ?
— 2002
— 2004
— 2010
— 1992
— 2022
— 2012

Correction La page de profile de TTY indique qu’elle a été la mascotte de Prologin pour la première
fois en 2010.

0.11 Question 11 : Prolozoo

Énoncé Quel animal n’a jamais figuré sur une affiche Prologin ?
— Un perroquet
— Une loutre
— Un chat
— Un écureuil
— Un chien
— Un lion
— Un loris
— Un panda
— Un lapin
— Un pingouin
— Un dinosaure
— Un chameau
2. Journal Officiel des Associations et Fondations d’Entreprise
3. Direction de l’Information Légale et Administrative

6
Correction En observant attentivement les affiches Prologin, on y retrouve les animaux suivants,
par ordre d’apparition :
— 2004 : un chat (TTY )
— 2006 : un perroquet
— 2007 : un pingouin
— 2008 : un loris
— 2012 : un chameau
— 2016 : un dinosaure
— 2017 : une loutre
— 2019 : un chien
— 2020 : un panda, un lion
— 2021 : un lapin
Le seul animal qui n’était pas présent était donc l’écureuil.
Vous ne les voyez toujours pas ? Regardez plus attentivement, certain sont cachés dans les logos
des sponsors

0.12 Question 12 : Les questions ne veulent plus rien dire

Énoncé Lors de la dernière édition Prologin, un panda a mangé le haut de la feuille de score et nous
n’arrivons plus à nous rappeler du vainqueur. Cependant nous disposons des informations suivantes :
1. Qktpo est fan d’Ada
2. Le dévoreur de Buenos est arrivé juste avant Lgrwqr
3. Sruwhpho est arrivé avant Hoilnxu
4. Celui qui ne prend pas de goûter est arrivé en dernier
5. Hoilnxu code en OCaml
6. Le dev Cobol est arrivé en troisème
7. Le dev Lisp mange des Glaces
8. L’affamé de Gaufres est arrivé juste après Hoilnxu
Qui est arrivé en premier ?
— Sruwhpho
— Hoilnxu
— Qktpo
— Lgrwqr

Correction Il s’agit d’une variante de l’énigme d’Einstein, en la résolvant petit à petit, on se retrouve
avec le tableau suivant :
Nom Langage Goûter
1 Sruwhpho Lisp Glace
2 Hoilnxu OCaml Bueno
3 Lgrwqr Cobol Gaufre
4 Qktpo Ada -

La réponse attendue était donc Sruwhpho.

Je ne sais pas si ça peut t’aider mais tu as essayé de faire un ROT3 sur les noms ?

7
 0.13 Question 13 : C’est un langage ça ?!
Énoncé Dans le langage de programmation ”Rouille”, quelle instruction doit-on écrire avant de
pouvoir utiliser la struct Dictionnaire ?

Correction Rouille n’est pas un langage à proprement parler mais cela vous permet d’écrire du
Rust en utilisant des mots français, et rien que pour ça, on apprécie l’effort !
La réponse attendue était :

utilisons std::collections::Dictionnaire;

0.14 Question 14 : roff ? C’est un cri de désespoir ?

Énoncé Qu’est-ce que roff ?
— Un langage de programmation basé sur le langage fonctionnel Lisp
— Un compilateur de Neko
— Un système d’exploitation dérivé d’Unix
— Un langage de formatage de texte

Correction La réponse attendue était : Un langage de formatage de texte.

Pour plus d’infos, RTFM 4 !

0.15 Question 15 : J’en ai ma claque des anniversaires

Énoncé En quelle année L’anniversaire de Joseph Marchand a-t-il été un sujet d’épreuve régionale ?

Correction La réponse attendue était : 2015. Vous pouvez retrouver le sujet ici.

0.16 Question 16 : J’y vois que dalle

Énoncé Quelle est la sortie standard de ce programme ? 5

1 ___−−−−−−→__−−−−−−→_−−−−−−→_.
2 −−−−−−→.
3 _____−−−−−−→−−−−−−→_−−−−−−→−−−−−−→−−−−−−→−−−−−−→.
4 −−−−−−→.
5 _____−−−−−−→−−−−−−→−−−−−−→−−−−−−→__−−−−−−→.
6 −−−−−−→.
7 _____−−−−−−→−−−−−−→__−−−−−−→_−−−−−−→.
8 −−−−−−→.
9 _____−−−−−−→−−−−−−→−−−−−−→_−−−−−−→_−−−−−−→.
10 −−−−−−→.
11 _____−−−−−−→−−−−−−→−−−−−−→−−−−−−→___.
12 −−−−−−→.
13 ______−−−−−−→_____.
14 −−−−−−→.
15 _____−−−−−−→−−−−−−→____−−−−−−→.
16 −−−−−−→.
17 _____−−−−−−→−−−−−−→_−−−−−−→−−−−−−→−−−−−−→_.
18 −−−−−−→.
19 _____−−−−−−→−−−−−−→_−−−−−−→−−−−−−→−−−−−−→_.
4. Read The F****** Manual
5. Notez que le fichier a été légèrement modifié pour être correctement rendu sur ce PDF

8
20 −−−−−−→.
21 _____−−−−−−→−−−−−−→_−−−−−−→__−−−−−−→.
22 −−−−−−→.
23 _____−−−−−−→−−−−−−→−−−−−−→_−−−−−−→−−−−−−→_.
24 −−−−−−→.
25 _____−−−−−−→−−−−−−→__−−−−−−→_−−−−−−→.
26 −−−−−−→.
27 _____−−−−−−→−−−−−−→−−−−−−→__−−−−−−→_.
28 −−−−−−→.
29 _____−−−−−−→−−−−−−→−−−−−−→__−−−−−−→−−−−−−→.
30 −−−−−−→.
31 _____−−−−−−→−−−−−−→____−−−−−−→.
32 −−−−−−→.
33 _____−−−−−−→−−−−−−→_−−−−−−→__−−−−−−→.
34 −−−−−−→.
35 _____−−−−−−→−−−−−−→−−−−−−→__−−−−−−→_.
36 −−−−−−→.
37 _____−−−−−−→−−−−−−→__−−−−−−→_−−−−−−→.
38 −−−−−−→.
39 ______−−−−−−→_____.
40 −−−−−−→.
41 _____−−−−−−→_−−−−−−→____.
42 −−−−−−→.
43 _____−−−−−−→−−−−−−→−−−−−−→__−−−−−−→_.
44 −−−−−−→.
45 _____−−−−−−→−−−−−−→_−−−−−−→−−−−−−→−−−−−−→−−−−−−→.
46 −−−−−−→.
47 _____−−−−−−→−−−−−−→_−−−−−−→−−−−−−→__.
48 −−−−−−→.
49 _____−−−−−−→−−−−−−→_−−−−−−→−−−−−−→−−−−−−→−−−−−−→.
50 −−−−−−→.
51 _____−−−−−−→−−−−−−→__−−−−−−→−−−−−−→−−−−−−→.
52 −−−−−−→.
53 _____−−−−−−→−−−−−−→_−−−−−−→__−−−−−−→.
54 −−−−−−→.
55 _____−−−−−−→−−−−−−→_−−−−−−→−−−−−−→−−−−−−→_.
56 −−−−−−→.
57 ______−−−−−−→_____.
58 −−−−−−→.
59 ______−−−−−−→____−−−−−−→.
60 −−−−−−→.
61 __.
62

63

Correction Beaucoup d’entre vous étaient un peu décontenancés à la vue d’un fichier ”vide”. En
regardant de plus près, vous pouviez remarquer que le fichier contenait des espaces et des tabulations,
il s’agit en réalité d’un fichier dans le langage Whitespace.

En interprétant le fichier, par exemple avec https://naokikp.github.io/wsi/whitespace.html,

on trouve comme sortie : Joyeux anniversaire Prologin !.

9
 1 Sur les ondes
1.1 Énoncé
Joseph a pour mission d’ouvrir un portail inter-dimensionnel sur sa planète. Pour l’aider il a reçu
un manuel expliquant la marche à suivre pour ouvrir ledit portail :
Il faut trouver une fréquence appelée fréquence optimale qui va être utilisée pour générer le
portail.
La fréquence optimale doit être :
— la plus petite possible
— multiple de 3
Vous devez trouver la fréquence optimale parmi une liste de fréquences, et l’afficher (il y aura
toujours une fréquence optimale).

1.2 Solution
L’exercice est assez simple, il suffit pour le résoudre de filtrer les fréquences pour ne garder que
celles multiple de 3 puis de trouver le minimum parmi les valeurs restantes.

1.3 Implémentation
1 def sur_les_ondes_for(n, freqs):
2 minimum = None
3 for x in freqs:
4 # x est divisible par 3
5 if x % 3 == 0:
6 # x est le nouveau minimum
7 if minimum is None or x < minimum:
8 minimum = x
9 print(minimum)
10

11

12 if __name__ == '__main__':
13 n = int(input())
14 freqs = list(map(int, input().split()))
15 sur_les_ondes(n, freqs)

Ou alors, en utilisant des méthodes de base de Python :

1 def sur_les_ondes(n, freqs):

2 print(min(filter(lambda x: x % 3 == 0, freqs)))

10
 2 Dernière pièce
2.1 Énoncé
Après avoir traversé les dimensions, Joseph Marchand se retrouve face à une porte gigantesque.
Cependant, ce n’est pas une porte normale : il s’agit d’un puzzle. Pour ne pas arranger les choses,
les pièces ne ressemblent en rien à des pièces de puzzle ordinaire. Ce sont des polygones de toutes
sortes ! Triangles, rectangles, octogones et j’en passe… Mais bonne nouvelle : il est presque terminé, il
ne manque plus qu’une pièce. Dans un coin au sol se trouvent de nombreuses pièces, l’une d’entre elle
pourrait bien lui permettre de terminer ce puzzle.
En plus de chercher une pièce avec le bon nombre de côtés, il faut également que la pièce soit d’une
couleur différente de celles des pièces adjacentes.
Déjà fatigué par son saut inter-dimensionnel, Joseph Marchand souhaite transporter le moins de
pièces possible. Il lui faut donc identifier les pièces qui pourraient potentiellement convenir pour ne
déplacer que ces dernières. Aide-le à ouvrir la porte rapidement !

2.2 Solution
Il s’agit d’un exercice de niveau 2, il reste donc encore assez simple. Il suffit d’itérer sur les différentes
pièces pour filtrer celles qui correspondent aux caractéristiques demandées. On affiche si oui ou non la
pièce respecte les contraintes, et on incrémente le compteur si c’est le cas. Une fois qu’on a itéré sur
toutes les pièces, on affiche le nombre de pièces qui correspondent.

2.3 Implémentation
1 def resoudre(ncouleurs, couleurs, ncotes, couleurscotes, npieces, pieces):
2 count = 0
3

4 for piece in pieces:

5 if piece["nCotesPiece"] == ncotes and piece["couleurPiece"] not in couleurscotes:
6 print("O", end='')
7 count += 1
8 else:
9 print("X", end='')
10 print("\n" + str(count))
11

12 if __name__ == '__main__':
13 ncouleurs = int(input())
14 couleurs = [{"couleur": input()} for _ in range(ncouleurs)]
15 ncotes = int(input())
16 couleurscotes = [{"couleur": input()} for _ in range(ncotes)]
17 npieces = int(input())
18 pieces = [{
19 "nCotesPiece": int(input()),
20 "couleurPiece": {
21 "couleur": input()
22 }} for _ in range(npieces)]
23 resoudre(ncouleurs, couleurs, ncotes, couleurscotes, npieces, pieces)

11
3 Enter The Matriks
3.1 Énoncé
Vous êtes l’élu, le maître de la Matriks. Cependant, comme vous le savez car vous êtes un fan
incontestable de la trilogie des sœurs Wachowskis, il y a eu plusieurs versions de la matrice avant
d’aboutir à celle dans laquelle ont vécu Neo, Morpheus et Trinity.
En effet, au lieu d’être dans la matrice (forme finale du cocon informatique dans lequel sont
immergés les êtres humains), vous êtes dans une version plus primaire, une version Test. Cette pre-
release de la matrice s’appelle la ”Matriks”. Pour en sortir et sauver Sion, la dernière ville des Hommes
encore debout, vous devez trouver deux clés (des listes d’entiers). Ces deux clés sont cachées dans le
code de la Matriks (une grosse liste d’entiers écrits en vert sur fond noir qui descend en colonnes de
manière assez stylé).
Vous savez deux choses : le produit des sommes de ces deux clés est égal à un nombre magique X,
qui vous est donné. Et vous savez que les deux clés doivent être les plus longues possibles (maximiser
la somme des longueurs des sous-listes). À vous de trouver ces clés !
Attention, l’ordre des clés importe, vous devez d’abord afficher la plus grande des deux listes, si
elles sont de même taille, affichez d’abord celle dont la somme est la plus grande.
S’il n’y a pas de sous-liste qui respectent ces conditions, écrire ”IMPOSSIBLE” (vous n’êtes alors
peut-être pas l’élu ?).

3.2 Solution
3.2.1 Approche
Il nous est impossible d’itérer sur toutes les paires de clés afin de trouver une paire de clé dont le
produit de leur somme vaut X. En effet, une liste de taille n possède O(n2 ) sous-listes, et donc O(n4 )
paires de sous-listes, ce qui excède déjà la complexité attendue.
En revanche, il est possible de procéder à l’envers, c’est à dire itérer sur des paires de valeurs A et
B dont le produit vaut X, puis trouver deux sous-listes dont les sommes vaudront A et B.
Pour itérer sur toutes les valeurs de A et B, il suffit de parcourir les diviseurs de X. Pour trouver
efficacement une sous-liste de somme S dans la Matriks, l’idée est de trouver deux préfixes 6 de somme
K et K − S. Un algorithme classique utilisant deux pointeurs ne pourrait pas résoudre ce problème,
car la Matriks peut contenir des éléments négatifs.

3.2.2 Algorithme
Appelons M la Matriks, Mi l’élément d’index i (partant de 0) de la Matriks, et N la longueur de
la Matriks. Appelons Pi le préfixe de la Matriks ayant une longueur de i, c’est à dire la sous-liste de
la Matriks contenant tous ses éléments de M0 inclus jusqu’à Mi exclus : Pi = [ Mk , k ∈ [[0, i[[ ]
1. Créer le tableau cumulatif C de la Matriks, contenant la somme de chacun de ses préfixes :
i−1
Mi ;
X X
∀i ∈ [[0, N ]] : Ci = Pi =
k=0
2. Créer le dictionnaire D associant à chaque élément de C sa plus petite position dans le tableau
cumulatif : ∀i ∈ [[0, N ]] : D[Ci ] = min(j : Cj = Ci ) ;
3. Pour chaque couple A et B tels que A · B = X, trouver — si elles existent — les plus longues
sous-liste de somme A et B dans la Matriks, et retenir le couple de sous-listes ayant la plus
grande longueur cumulée.
Pour trouver la plus longue sous-liste de somme S dans la Matriks, nous pouvons réduire le
problème en cherchant pour chaque index j la plus longue sous-liste de somme S se terminant à
l’élément Mj−1 et en retenant la plus longue d’entre elles.
6. Un préfixe d’une liste est une sous-liste partant du premier élément de la liste. Par exemple, [], [2], [2, 0],
[2, 0, 2] et [2, 0, 2, 1] sont les préfixes de la liste [2, 0, 2, 1]

12
 Pour ceX
faire, ilX
suffit de regarder pour chaque préfixe Pj de la Matriks le plus petit préfixe Pi
respectant Pj − Pi = Cj − Ci = S. Si Pi existe, alors la sous-liste partant de l’élément d’index i
j−1 j−1 i−1
et se terminant à l’élément d’index j −1 aura une somme de
X X X
Mk = Mk − Mk = Cj −Ci = S,
k=i k=0 k=0
et sera la plus grande sous-liste de somme S se terminant à l’indice j − 1.
Plus simplement, la plus longue sous-liste de M de somme S se terminant à l’index j − 1, si elle
existe, commencera toujours à l’index D[Cj − S],X car D[CX
j − S] contient la longueur du plus petit
préfixe Pi de somme Cj − S, ce qui implique que Pj − Pi = Cj − (Cj − S) = S.
Dans le cas particulier où X = 0, il suffit de prendre comme première clé la Matriks en elle-même
et comme seconde clé la plus longue sous-liste de somme 0.

3.2.3 Complexité
La complexité de mémoire de cet algorithme est O(N ), car nous enregistrons uniquement le tableau
cumulatif de M de longueur N +1, ainsi qu’un dictionnaire associatif contenant au plus N +1 éléments.
La complexité temporelle de notre algorithme pour trouver la plus longue sous-liste de M de somme
S est de O(N ). En effet nous parcourons une seule fois notre tableau cumulatif, et pour chaque élément
nous recherchons uniquement un autre élément dans le dictionnaire.
Étant donné qu’il existe au maximum environ O(X 3 ) diviseurs de X, la complexité temporelle
1

√
totale
√ de notre algorithme est de O(N X + X). En effet, nous devons parcourir un intervalle
p de
1
3

O( X) éléments afin de trouver chaque potentielle valeur de A (L’intervalle [[− |X|, −1]] ∪ [[1, |X|]]
p

est par exemple amplement suffisant), et si A divise X alors nous pouvons prendre X/A comme
valeur pour B, et par conséquent avoir toutes les paires A, B respectant A · B = X. Nous devons
appliquer notre algorithme de complexité O(N ) pour chaque paire A, B valide, soit une complexité de
√
O(N X 3 + X). La création du tableau cumulatif et du dictionnaire ayant une complexité de O(N ),
1

cela n’impacte pas la complexité globale du problème.

3.3 Implémentation
Voici une proposition d’implémentation :

1 from math import sqrt

2

3 def resoudre(x, n, l):

4

5 class Cle:
6 def __init__(self, start, end, somme):
7 self.start = start
8 self.end = end
9 self.longueur = end-start
10 self.somme = somme
11

12 def __repr__(self):
13 return " ".join(map(str, l[self.start:self.end]))
14

15 def __eq__(self, other):

16 return self.start == other.start and self.end == other.end
17

18 def __lt__(self, other):

19 # Les clés sont triées d'abord par leur longueur puis par leur somme
20 return (self.longueur < other.longueur
21 or (self.longueur == other.longueur
22 and self.somme < other.somme))

13
23

24 def __bool__(self):
25 # Une clé impossible est représentée par une longueur nulle
26 return self.longueur > 0
27

28 # Création du tableau cumulatif C

29 cumul = [0]
30 somme = 0
31 for elt in l:
32 somme += elt
33 cumul.append(somme)
34

35 # Création du dictionnaire associatif D

36 hashmap = {}
37 for i, somme in enumerate(cumul):
38 if not somme in hashmap:
39 hashmap[somme] = i
40

41 def sous_tableau(s):
42 """
43 Retourne la plus longue clé de somme s
44 """
45 longueur = 0
46 start = 0
47 end = 0
48 for j, somme in enumerate(cumul):
49 if somme-s in hashmap:
50 i = hashmap[somme-s]
51 if j-i > longueur:
52 start = i
53 end = j
54 longueur = j-i
55 return Cle(start, end, s)
56

57

58 # Première clé
59 cle1 = Cle(0, 0, 0)
60 # Deuxième clé
61 cle2 = Cle(0, 0, 0)
62

63 if x == 0:
64 cle1 = Cle(0, n, somme)
65 cle2 = sous_tableau(0)
66 else:
67 for a in range(-int(sqrt(abs(x))), int(sqrt(abs(x)))+1):
68 if a == 0:
69 continue
70 if x % a == 0:
71 b = x // a
72 clea = sous_tableau(a)
73 cleb = sous_tableau(b)
74 if (clea and cleb and
75 clea.longueur + cleb.longueur > cle1.longueur + cle2.longueur):

14
76 cle1 = max(clea, cleb)
77 cle2 = min(clea, cleb)
78

79 if cle1 and cle2:

80 print(cle1)
81 print(cle2)
82 else:
83 print("IMPOSSIBLE")
84

85 if __name__ == '__main__':
86 x = int(input())
87 n = int(input())
88 l = list(map(int, input().split()))
89 resoudre(x, n, l)

15
4 Fuite de clavier
4.1 Énoncé
Joseph Marchand est un petit brigand. Il a installé sur l’ordinateur de son amie Alice un keylogger
(un logiciel espion qui capture les entrées du clavier) en dépit des réglementations en vigueur qui
condamnent fermement ce genre de pratique.
Il essaie en effet de récupérer le mot de passe Prologin d’Alice ! Malheureusement pour lui, le
keylogger a enregistré toutes les frappes sur le clavier, sans distinction de s’il s’agissait d’un mot de
passe ou non.
Joseph se retrouve donc avec une suite de caractères composé de lettres minuscules, majuscules,
de nombres et de caractères spéciaux.
Il sait juste que le mot de passe d’Alice répond aux exigences de sécurité suivantes :
— Contenir au moins une minuscule (a-z)
— Contenir au moins une majuscule (A-Z)
— Contenir au moins un nombre (0-9),
— Contenir au moins un caractère spécial (!"#$%&'()*+,-./:;<=>?@[\]^_`{|}~),
— La taille du mot de passe est de k caractères.
Aidez Joseph à savoir combien de chaines de k caractères pourraient être le mot de passe d’Alice.

4.2 Solution
Le but est de savoir combien de sous-chaines de taille k caractères répondent aux critères. Cet
exercice peut être résolu en utilisant une fenêtre coulissante contenant k éléments.
Il y a deux étapes à suivre :
1. Initialiser la fenêtre
2. Faire coulisser (mettre à jour) la fenêtre sur toute la chaîne.

4.2.1 Initialisation
La fenêtre doit prendre en compte 4 valeurs :
— Le compteur de lettres minuscules (’lower’)
— Le compteur de lettres majuscules (’upper’)
— Le compteur de nombres (’digits’)
— Le compteur des caractères spéciaux, ceux qui ne vont dans aucune autre catégorie (’special’)
Nous pouvons créer une fonction associant à un caractère sa catégorie (get_class dans l’implé-
mentation), puis une autre fonction pour déterminer si la fenêtre est valide, c’est à dire qu’elle contient
un mot de passe correct (is_valid dans l’implémentation).
Pour évaluer la première fenêtre, il faut incrémenter le compteur de chaque catégorie des k premiers
caractères.
Un autre compteur est créé contenant le nombre de mots de passe corrects (n_valid dans l’im-
plémentation). Ensuite, si la première fenêtre est valide, nous pouvons incrémenter ce compteur.

4.2.2 Mise à jour

Il ne reste plus qu’à faire coulisser la fenêtre sur les n − k prochains caractères. Pour cela, nous
allons itérer dans toutes les fenêtres existantes, de gauche à droite puis prendre en compte seulement
le caractère ne faisant plus partie de la dernière fenêtre (last) ainsi que le nouveau caractère, le plus
à droite de la fenêtre (new).
A présent, nous pouvons décrémenter le compteur de la classe de last et incrémenter celui de la
classe de new.

16
 La fenêtre est à jour, nous pouvons tester si elle est valide via is_valid pour incrémenter n_valid
si besoin.
Le résultat est n_valid.

4.2.3 Complexité
Les fonctions get_class et is_valid ont un temps et une mémoire constante.
Initialiser la fenêtre a une complexité de O(k) en temps ce qui est inclus dans O(n) puisque k ≤ n.
Mettre à jour la fenêtre a une complexité de O(n) en temps (la boucle ne contient que des opérations
de temps constant).
La complexité totale est alors de O(n) en temps et O(1) en mémoire si nous ne comptons pas les
entrées.

17
 4.3 Implémentation
1 import string
2

3 if n < k:
4 print(0)
5 return
6

7 chars = {
8 'lower': 0,
9 'upper': 0,
10 'digit': 0,
11 'special': 0,
12 }
13

14 def get_class(c):
15 if c in string.ascii_lowercase:
16 return 'lower'
17 elif c in string.ascii_uppercase:
18 return 'upper'
19 elif c in string.digits:
20 return 'digit'
21 else:
22 return 'special'
23

24 def is_valid(chars):
25 return (
26 chars['lower'] >= 1 and chars['upper'] >= 1 and
27 chars['digit'] >= 1 and chars['special'] >= 1
28 )
29

30 n_valid = 0
31

32 # Characters within chaine[0 : k]

33 for c in chaine[:k]:
34 chars[get_class(c)] += 1
35

36 # chaine[:k] is valid
37 if is_valid(chars):
38 n_valid += 1
39

40 # Test chaine[i : i + k]
41 for last, new in zip(chaine[:n - k], chaine[k : n]):
42 chars[get_class(last)] -= 1
43 chars[get_class(new)] += 1
44

45 # chaine[i : i + k] is valid (i is the loop index)

46 if is_valid(chars):
47 n_valid += 1

18
5 Coffre-fort
5.1 Énoncé
Joseph Marchand doit ouvrir un coffre électronique sécurisé.
Le coffre contient un circuit complexe, décrit sous la forme d’un ensemble de puces, reliées entre
elles par des fils. Il existe toujours exactement un chemin entre chaque paire de puces. Chaque puce
envoie un signal si au verrou lorsqu’elle est activée. Joseph Marchand tente de passer outre la sécurité
du coffre et a besoin de votre aide pour calculer rapidement les effets de ses manipulations.
Il veut régulièrement connecter les deux bornes d’un générateur électrique à deux puces a et b du
circuit, et se demande quel signal est envoyé au verrou du coffre suite à cette opération. Une puce c
est activée s’il existe un chemin de a vers b passant par c, qui ne repasse pas deux fois par le même
fil. Le signal reçu par le verrou est alors le produit du signal envoyé par chaque puce activée, modulo
1671404011 (car on ne peut pas représenter de trop grands nombres par un signal électrique).

5.1.1 Exemple

0
4 1
9
3
2
2
7

4 5
3 0

5.2 Solution
5.2.1 Stratégie
Pour pouvoir répondre aux requêtes, il est nécessaire d’avoir une manière de trouver et parcourir
l’unique chemin entre deux puces. Seulement, il n’est pas envisageable de les parcourir intégralement
à chaque requête. En effet, un chemin est constitué d’O(N ) puces, et parcourir chaque chemin pour
chaque requête résulterait en une complexité temporelle de O(R×N ), ce qui excéderait déjà les limites
de performance au vu des contraintes.
Une autre stratégie envisageable aurait été d’enraciner l’arbre depuis une puce arbitraire r, et de
pré-calculer pour chaque puce le produit des signaux du chemin le reliant à la racine à la manière
d’un tableau préfixe. Ensuite, un algorithme de plus petit ancêtre commun permettrait de diviser le
chemin entre deux puces en deux plus petits chemins, reliant les deux puces a et b à leur plus petit
ancêtre commun c. Enfin, il aurait pu être possible de calculer le produit des signaux entre a (ou b) et
c en divisant le produit des signaux entre a et r (précédemment calculé) avec le produit des signaux
entre c et r (également précédemment calculé). Ainsi, il aurait été possible de calculer le produit des
signaux entre a et c, ainsi qu’entre c et b, et le produit de ces deux valeurs aurait pu donner le résultat
attendu. Cependant, sous contrainte du modulo, il serait impossible d’effectuer la division entre deux
valeurs, car le modulo donné n’est pas premier et n’est donc pas inversible.
Nous sommes donc contraints de trouver la réponse sans tableau préfixe, car nous ne pouvons
pas effectuer de division. L’idée est alors de modifier l’algorithme du plus petit ancêtre commun afin
d’enregistrer en plus les produits des signaux entre chaque puce et son 2k -ème ancêtre (exclu). Ainsi,
le produit des signaux entre a et b peut se trouver en calculant, depuis les valeurs pré-calculées, les

19
produits des signaux entre a et c (exclu), ainsi qu’entre b et c, puis en multipliant le produit de ces
deux valeurs par le signal envoyé par c.

5.2.2 Plus petit ancêtre commun

L’algorithme du plus petit ancêtre commun est un algorithme permettant, après un pré-traitement
d’une complexité temporelle de O(N log N ), de trouver en une complexité de O(log N ) l’ancêtre com-
mun à deux puces a et b qui soit le plus éloigné de la racine d’un arbre.
Le principe est le suivant : pour chaque puce, on pré-calcule son 2k -ème ancêtre, pour tout k entre
0 et log2 (N ), ainsi que sa profondeur dans l’arbre. Dans notre cas, nous pré-calculerons également le
produit des signaux situés sur le chemin entre la puce et son 2k -ème ancêtre (exclu). On considère
l’ancêtre de la racine comme étant la racine elle-même. Depuis cette information, on peut calculer
en une complexité temporelle de O(log K) le K-ème ancêtre de toute puce. Pour ce faire, il suffit
de parcourir la décomposition sous forme de puissances de 2 de K (forme binaire), et pour chaque
puissance i se déplacer de la puce actuelle à son i-ème ancêtre.
La première étape du traitement d’une requête consiste à remonter de la puce la plus profonde
jusqu’à une puce située à la même profondeur. Supposons la puce a plus profonde que b sans perte de
généralité (il n’y a rien à faire si les deux puces sont déjà de la même profondeur). Appelons P (x) la
profondeur d’une puce x. Le plus petit ancêtre commun entre a et b est identique au plus petit ancêtre
commun entre le P (a) − P (b)-ème ancêtre de a et b. L’avantage de considérer le P (a) − P (b)-ème
ancêtre de a plutôt que a en elle-même est qu’ainsi, les deux puces auront la même profondeur, et
seront donc situées à la même distance de leur plus petit ancêtre commun. Nous enregistrons également
le produit des signaux entre a et son P (a) − P (b)-ème ancêtre (exclu), avec lequel nous multiplierons
notre résultat final.
Maintenant, il nous reste à trouver le plus petit ancêtre commun de deux puces situées sur la
même profondeur. Pour cela, pour chaque 2k à compter de k = log2 (N ), si le 2k -ème ancêtre de a est
différent de celui de b, cela signifie que leur ancêtre commun est situé plus loin d’eux. On déplace alors
nos deux puces de 2k puces en arrière, en enregistrant le produit des signaux croisés au passage. Faire
cela jusqu’à k = 0 nous assure d’avoir a et b qui sont, au pire, fils directs de c, la puce recherchée.
Depuis cette situation, la résolution est triviale.

20
 5.3 Implémentation
1 from sys import setrecursionlimit
2 setrecursionlimit(10**6)
3

4 MOD = 1671404011
5

6 def calculer_signaux(n, m, r, signaux, fils, questions):

7 """
8 :param n: nombre de puces
9 :type n: int
10 :param m: nombre de fils
11 :type m: int
12 :param r: nombre de questions
13 :type r: int
14 :param signaux: liste des signaux
15 :type signaux: list[int]
16 :param fils: liste des fils entre les puces
17 :type fils: list[dict["puce1": int, "puce2": int]]
18 :param questions: liste des questions
19 :type questions: list[dict["puce a": int, "puce b": int]]
20 """
21 adj = [[] for _ in range(n)] # Liste d'adjacence de l'arbre
22 for fil in fils:
23 a = fil['puce1']
24 b = fil['puce2']
25 adj[a].append(b)
26 adj[b].append(a)
27

28 # On considère la puce 0 comme racine

29

30 # ancetre[k][i] est un tuple contenant le 2^k-ieme ancetre de la puce k,

31 # ainsi que le produit des signaux entre la puce k et son 2^k-ieme ancetre
32 # exclu
33 ancetre = [[None] * n]
34

35 # profondeur[i] contient la profondeur du puce i

36 profondeur = [0] * n
37

38 def init_ancetre(racine, parent, profondeur_racine):

39 # Parcours en profondeur de l'arbre pour l'enraciner.
40 # Initialise le premier niveau du tableau ancetre ainsi que le tableau
41 # profondeur.
42 profondeur[racine] = profondeur_racine
43 for enfant in adj[racine]:
44 if enfant == parent:
45 continue
46 ancetre[0][enfant] = (racine, signaux[enfant])
47 init_ancetre(enfant, racine, profondeur_racine + 1)
48

49 init_ancetre(0, -1, 0)
50 ancetre[0][0] = (0, 1)
51

52 # Remplissage du tableau ancetre

21
53 for k in range(n.bit_length()): # ~log_2(n) niveaux sont suffisants
54 niveau = []
55 for i in range(n):
56 # Le 2^k-ieme ancetre de i est le 2^(k-1)e ancêtre
57 # de son 2^(k-1)e ancêtre
58 puceA, prodA = ancetre[-1][i]
59 puceB, prodB = ancetre[-1][puceA]
60 niveau.append((puceB, prodA * prodB % MOD))
61 ancetre.append(niveau)
62

63 def k_ancetre(i, k):

64 # Retourne le k-ième ancêtre de i ainsi que le produit des signaux entre
65 # i et son k-ième ancêtre
66 produit = 1
67 j = 0
68 while k > 0:
69 if k % 2 == 1:
70 i, prod = ancetre[j][i]
71 produit = produit * prod % MOD
72 k //= 2
73 j += 1
74 return i, produit
75

76 def lca(a, b):

77 # Retourne le plus petit ancêtre commun entre a et b, ainsi que le
78 # produit des signaux entre a et b (inclus)
79

80 produit = 1
81 # Premier saut pour mettre a et b à la même profondeur
82 if profondeur[a] > profondeur[b]:
83 a, produit = k_ancetre(a, profondeur[a] - profondeur[b])
84 if profondeur[b] > profondeur[a]:
85 b, produit = k_ancetre(b, profondeur[b] - profondeur[a])
86

87 # On fait tout les sauts de taille 2^k possibles (par taille

88 # décroissante) tant qu'on n'arrive pas sur la même puce
89 for j in range(n.bit_length(), -1, -1):
90 sautA, prodA = ancetre[j][a]
91 sautB, prodB = ancetre[j][b]
92 if sautA != sautB:
93 a = sautA
94 b = sautB
95 produit = produit * prodA * prodB % MOD
96

97 # On fait le dernier saut si a != b

98 if a != b:
99 produit = produit * signaux[a] * signaux[b] % MOD
100 a = b = ancetre[0][a][0]
101

102 # On comptabilise le signal racine

103 produit = produit * signaux[a] % MOD
104 return a, produit
105

22
106 for question in questions:
107 a = question['puce a']
108 b = question['puce b']
109 racine, produit = lca(a, b)
110 print(produit)
111

112 if __name__ == '__main__':

113 n = int(input())
114 m = int(input())
115 r = int(input())
116 signaux = list(map(int, input().split()))
117 fils = [
118 dict(zip(("puce1", "puce2"), map(int, input().split())))
119 for _ in range(m)
120 ]
121 questions = [
122 dict(zip(("puce a", "puce b"), map(int, input().split())))
123 for _ in range(r)
124 ]
125 calculer_signaux(n, m, r, signaux, fils, questions)

23
6 Coffre électronique
6.1 Énoncé
Joseph Marchand s’est rendu compte que le coffre qu’il cherche à ouvrir est bien trop sécurisé pour
qu’il puisse deviner la combinaison d’une façon aussi simple ! Cependant tout espoir n’est pas perdu,
car il a réussi à modifier le circuit. Il a rajouté un certain nombre de cables électriques, et est capable
de changer la valeur d’une puce à volonté.
Le coffre contient un circuit complexe, décrit sous la forme d’un ensemble de puces, reliées entre
elles par des fils. Il existe au moins un chemin entre chaque paire de puces (depuis que Joesph à rajouté
des fils, il peut y en avoir plusieurs). Chaque puce envoie un signal si au verrou lorsqu’elle est activée.
Joseph Marchand tente de passer outre la sécurité du coffre et a besoin de votre aide pour calculer
rapidement les effets de ses manipulations.
Il veut régulièrement modifier la valeur si contenue par une puce, puis mesurer l’effet que cela à
sur le circuit en connectant les deux bornes d’un générateur électrique à deux puces a et b du circuit.
Il se demande alors quel signal est envoyé au verrou du coffre suite à cette opération. Une puce c est
activée s’il existe un chemin de a vers b passant par c, qui ne repasse pas deux fois par le même fil
(mais peut passer deux fois par la même puce). Le signal reçu par le verrou est alors le produit du
signal envoyé par chaque puce activée, modulo 1671404011 (car on ne peut pas représenter de trop
grands nombres par un signal électrique).

6.1.1 Exemple

0
4 1
3
3
5

2 4 5
7 3 2

6 7
3 0

Ce circuit est l’état initial du circuit dans le premier exemple d’entrée. Les valeurs des puces 2, 3
et 5 vont cependant changer.

6.2 Solution
Cet exercice ressemble au précédent, qui est une introduction à celui-ci. Deux modifications
viennent compliquer le problème : ce n’est plus un arbre, mais un graphe quelconque, et il y a des
requêtes de modifications.

6.2.1 Transformer le graphe en arbre

La première difficulté n’en est pas une, mais illustre qu’il est parfois possible de se ramener à un
problème plus simple. En effet, un arbre est notamment caractérisé par l’absence de cycles. Prenons
un tel cycle de nœuds c1 , . . . , ck . On va montrer que pour tout couple (a, b) de puces activées, si une
puce du cycle est activée, elles le sont toutes.

24
 En effet, si on a un tel chemin entre a et b passant par c1 , on a un chemin a = x1 , . . . , xm =
c1 (éventuellement avec m = 1) de a vers c1 , qui ne passe par aucune arête du cycle, puis de c1
vers ci dont les arêtes peuvent appartenir au cycle ou non, et enfin de ci vers b que l’on note ci =
y1 , . . . , yl = b, et qui ne passe pas par le cycle. Alors on a les chemins x1 , . . . , xm , c2 , . . . , ci−1 , y1 , . . . , yl
et x1 , . . . , xm , ck , . . . , ci+1 , y1 , . . . , yl qui vont donc activer tous les nœuds du cycle.
Nous pouvons donc contracter tous les cycles du graphe en un seul ”gros” nœud, nous donnant un
arbre des cycles du graphe. Une manière simple de le faire est de parcourir le graphe avec un DFS et
d’utiliser un Union-Find pour fusionner les cycles : lorsque l’on arrive sur un nœud, on le marque ”en
cours”, et on retire cette marque une fois son exploration finie. Si un de ses voisins autre que son parent
est également en cours, c’est qu’on a trouvé un cycle : il se trouve parmi ses ancêtres dans l’arbre
d’exploration du DFS. On fusionne alors tous les nœuds entre le nœud actuel et le nœud ancêtre (les
deux extrémités incluses).
Dans la suite, on considérera cet arbre de nœuds fusionné. Mettre à jour la valeur d’un nœud de
l’arbre est très facile, compte donné une modification sur un nœud du graphe initial : on construit
pour chaque nœud i de l’arbre un arbre binaire Ti de produit, où les nœuds du graphe fusionnés
ensemble sont représentés par les feuilles. Ainsi si Ti correspond à une fusion de ni nœuds différents, il
est possible lors d’une modification d’obtenir la nouvelle valeur de i en O(log(ni )). Il suffit de mettre
à jour la feuille affectée, et de remonter Ti en recalculant le produit dans chaque nœud parent. On va
donc abstraire les requêtes comme des requêtes sur un arbre, et plus un graphe quelconque.

6.2.2 Chemins lourds

Nous avons donc un arbre et des requêtes de modification, et on veut calculer le produit entre deux
nœuds. En utilisant les idées de l’exercice précédent, on sait qu’il suffit de savoir calculer le produit
entre un nœud et l’un de ses ancêtres, ce qui à l’aide du plus petit ancêtre commun, nous permet
d’avoir la réponse. Reprenons l’algorithme bourrin : si on a une requête entre x et un ancêtre y, il
suffit de calculer le produit en remontant arc par arc de x vers y. Les requêtes de modifications sont
alors très simples : comme on recalcule à chaque fois, il suffit de modifier la valeur d’un nœud. Mais
chaque requête peut être lente : si l’arbre n’est qu’une longue chaîne a1 , . . . , aN , cela peut prendre
O(N ) pour chacune.
Le cas d’une longue chaîne semble plus simple que le problème avec un arbre complet, mais nous
pose problème : analysons-le. Cela revient à avoir un tableau de valeurs a1 , . . . , aN , et on veut pouvoir
modifier des valeurs n’importe où, mais aussi calculer le produit entre deux valeurs. Et nous avons
déjà la solution ! L’arbre binaire utilisé lors de la section précédente permet également de répondre
à ce problème en O(log(N )), en ajoutant une fonction récursive pour calculer le produit entre deux
cases arbitraires plutôt que tout le graphe.
Cela nous donne alors une idée : tenter de poser ces arbres binaires sur le graphe, ou du moins
sur les branches les plus longues. On va donc introduire le concept de décomposition en chemins
lourds. L’idée est d’avoir les chemins les plus longs (en réalité, ce ne sont pas toujours les plus longs,
mais ce sont les plus lourds tels qu’expliqué ensuite) qui seront des sortes d’”autoroutes”, où les
calculs seront réalisés par des arbres binaires. Pour construire le premier chemin lourd, on part du
nœud racine x1 et on sélectionne le nœud x2 ayant le plus grand sous-arbre (ou le plus profond, cela
fonctionne aussi). On continue ainsi à sélectionner le fils le plus lourd à chaque fois, jusqu’à obtenir
une branche x1 , . . . , xk avec xk une feuille. Pour chaque fils de x1 , . . . , xk−1 qui n’a pas été sélectionné,
on va construire un autre chemin lourd partant de ce nœud, et ainsi de suite jusqu’à ce que chaque
nœud fasse partie d’un chemin lourd.
La manière la plus simple d’implémenter l’idée ci-dessus est, pour chaque nœud, de sélectionner
le fils le plus lourd à l’avance, puis d’utiliser un simple DFS pour construire les chemins en un seul
parcours. On associe ensuite à chaque chemin lourd un arbre binaire, et à chaque nœud l’identifiant
de cet arbre, ainsi que sa position dans celui-ci, parmi les feuilles. Chaque arbre binaire calcule un
produit et effectuer une modification est alors trivial : on modifie la valeur dans l’arbre binaire du
chemin lourd du nœud, et on le met à jour en O(log(N )).
Il reste alors à utiliser cela pour calculer un produit de x vers y. On va reprendre notre algorithme
consistant à remonter l’arbre arête par arête, mais en utilisant les chemins lourds. Supposons que l’on

25
se trouve, en se déplaçant selon ce glouton, à un nœud ai , descendant de y. Il y a alors 3 cas pour
trouver le prochain nœud, ai+1 :
— Cas 1 : ai est le premier nœud de son chemin lourd. On remonte alors vers son parent en O(1),
et on utilise sa valeur pour le produit.
— Cas 2 : y et ai sont dans le même chemin lourd. On calcule alors le produit entre ai et y en
O(log(N )).
— Cas 3 : y n’est pas dans le chemin lourd de ai . On remonte au nœud le plus haut de ce chemin
(qui sera ai+1 ) et on calcule le produit entre ai et ai+1 en O(log(N )).

6.2.3 Complexité
Soit N le nombre de nœuds du graphe et R le nombre de requêtes. Pour calculer la complexité, il
faut savoir combien de fois chacun des cas 1, 2 et 3 peuvent arriver lors d’une requête.
Trivialement, le cas 2 n’arrive qu’une fois, car il mène directement à la réponse. Les cas 1 et 3
alternent et arrivent le même nombre de fois, à une constante près. On va alors montrer qu’avec
les chemins lourds, le cas 1 n’arrive qu’au plus log2 (N ) fois. Soit a1 , . . . , ak l’ensemble des nœuds
rencontrés dans le cas 1. ak n’est pas le fils lourd de son propre parent, donc le sous-arbre de ak est de
taille 6 N2 . Par le même raisonnement, le sous-arbre de ak−1 est de taille 6 N4 , et récursivement celui
de a1 est de taille 6 2Nk , mais de taille au moins 1. Ainsi, 1 6 2Nk donc k ≤ log2 (N ), d’où la conclusion.
La complexité de l’algorithme est donc de O(R log2 (N )).

26
 6.3 Implémentation
1 import sys
2 sys.setrecursionlimit(10**9)
3

4 lca_cur_pos = 0
5

6 def main():
7 MOD = 17 * 9697 * 10139
8 LCA_LOG = 18
9

10 nb_nodes = int(input())
11 nb_edges = int(input())
12 nb_queries = int(input())
13

14 node_signal = list(map(int, input().split()))

15 cycle_neighbors = [[] for _ in range(nb_nodes)]
16 neighbors = [[] for _ in range(nb_nodes)]
17 compo = [-1] * nb_nodes
18 compo_size = [1] * nb_nodes
19 state = [-1] * nb_nodes
20 heavy_child = [0] * nb_nodes
21 tree_depth = [0] * nb_nodes
22 tree_parent = [0] * nb_nodes
23 heavy_parent = [0] * nb_nodes
24

25 lca_min_left = [[0] * LCA_LOG for _ in range(nb_nodes*2)]

26 lca_min_right = [[0] * LCA_LOG for _ in range(nb_nodes*2)]
27 node_lca_pos = [0] * nb_nodes
28 root = None
29

30 i_leaf_of_node = [0] * nb_nodes

31 i_leaf_of_signal = [0] * nb_nodes
32

33 segtrees = [[0, []] for _ in range(nb_nodes)] # taille_reelle, noeuds_internes

34 compo_sig_tree = [[0, []] for _ in range(nb_nodes)]
35

36 for _ in range(nb_edges):
37 node_left, node_right = map(int, sys.stdin.readline().split())
38 cycle_neighbors[node_left].append(node_right)
39 cycle_neighbors[node_right].append(node_left)
40

41 # Arbres binaires
42

43 def heavy_segtree_build(tree, size, right_node):

44 # Initialistion d'un arbre binaire sur un chemin lourd avec au moins 'size'
45 # feuilles, le long d'une branche se terminant au noeud 'right_node'
46 leaves = []
47 while size:
48 leaves.append(right_node)
49 right_node = tree_parent[right_node]
50 size -= 1
51 leaves = leaves[::-1]
52 for i, i_node in enumerate(leaves):

27
53 i_leaf_of_node[i_node] = i
54

55 segtree_build(tree, [node_signal[l] for l in leaves])

56

57 def segtree_build(tree, leaves):

58 # Initilisation d'un arbre binaire, avec les valeurs de ses feuilles
59 real_size = 1
60 while real_size < len(leaves):
61 real_size *= 2
62 tree[:] = [1] * (real_size * 2)
63

64 for i, v in enumerate(leaves):
65 tree[real_size + i] = v
66

67 for i in range(real_size-1, 0, -1):

68 tree[i] = (tree[i*2] * tree[i*2+1]) % MOD
69

70 def segtree_query_prod(tree, deb, fin):

71 # Produit sur un intervalle dans l'arbre binaire
72 expl = [(1, 0, len(tree)//2)]
73 total = 1
74 while expl:
75 node, sub_deb, sub_fin = expl.pop()
76 if sub_fin <= deb or sub_deb >= fin:
77 continue
78 elif deb <= sub_deb and sub_fin <= fin:
79 total = (total * tree[node])%MOD
80 else:
81 expl.append((node*2, sub_deb, (sub_deb + sub_fin) // 2))
82 expl.append((node*2+1, (sub_deb + sub_fin) // 2, sub_fin))
83 return total
84

85 def segtree_set(tree, i_leaf, set_sig):

86 # Modification d'une valeur dans l'arbre binaire
87 node = len(tree)//2 + i_leaf
88 tree[node] = set_sig % MOD
89 while node > 1:
90 node //= 2
91 tree[node] = (tree[node*2] * tree[node*2+1])%MOD
92

93 # Union-find
94

95 def uf_find(x):
96 p = [x]
97 if compo[x] != -1:
98 while compo[p[-1]] != -1:
99 p.append(compo[p[-1]])
100 for y in p[:-1]:
101 compo[y] = p[-1]
102 return p[-1]
103

104 def uf_union(x, y):

105 x, y = uf_find(x), uf_find(y)

28
106 if x != y:
107 if compo_size[x] < compo_size[y]:
108 x, y = y, x
109 elif compo_size[x] == compo_size[y]:
110 compo_size[x] += 1
111 compo[y] = x
112

113 # Fusion de composantes cycliques

114

115 merge_compos_stack = [[0, -1, 0]]

116 compo_stack = []
117 def merge_compos(node, parent):
118 while merge_compos_stack:
119 node, parent, step = merge_compos_stack.pop()
120

121 if step == 0:
122 if state[node] == -1:
123 compo_stack.append(node)
124 state[node] = 0
125

126 merge_compos_stack.append([node, parent, 1])

127 for v in cycle_neighbors[node]:
128 if v != parent:
129 merge_compos_stack.append([v, node, 0])
130 elif state[node] == 0:
131 while uf_find(parent) != uf_find(node):
132 compo_stack.pop()
133 uf_union(parent, compo_stack[-1])
134

135 else:
136 state[node] = 1
137 if compo_stack[-1] == node:
138 compo_stack.pop()
139

140 def assign_signal_in_compos():

141 signals_in = [[] for _ in range(nb_nodes)]
142 for i_node in range(nb_nodes):
143 i_leaf_of_signal[i_node] = len(signals_in[uf_find(i_node)])
144 signals_in[uf_find(i_node)].append(node_signal[i_node])
145

146 for i_node in range(nb_nodes):

147 if signals_in[i_node]:
148 segtree_build(compo_sig_tree[i_node], signals_in[i_node])
149 node_signal[i_node] = compo_sig_tree[i_node][1]
150

151 # Construction des chemins lourds

152

153 def find_heavy_child(node, parent, node_depth):

154 state[node] = 0
155 tree_depth[node] = node_depth
156 tree_parent[node] = parent
157 node_children = []
158 max_child_depth = node_depth

29
159 heavy_child[node] = -1
160

161 for v in neighbors[node]:

162 if state[v] == -1:
163 depth = find_heavy_child(v, node, node_depth+1)
164 node_children.append(v)
165 if depth > max_child_depth:
166 max_child_depth = depth
167 heavy_child[node] = v
168 neighbors[node] = node_children
169 return max_child_depth
170

171 def build_heavy_paths(node):

172 if node == root or heavy_child[tree_parent[node]] != node:
173 # Dans le cas où on n'est pas un fils lourd, il faut construire son propre
174 # chemin lourd
175 heavy_parent[node] = node
176 right_node = node
177 while heavy_child[right_node] != -1: # Trouver tous les fils lourds
178 right_node = heavy_child[right_node]
179 heavy_parent[right_node] = node
180 # Construire l'arbre binaire sur le chemin lourds à partir du noeud
181 heavy_segtree_build(segtrees[node],
182 tree_depth[right_node] - tree_depth[node]+1, right_node)
183

184 for v in neighbors[node]:

185 build_heavy_paths(v)
186

187 # Remonter l'arbre via des arrêts et chemins de poid lourd jusqu'à une certaine
188 # profondeur
189

190 def get_lock_signal(node, top_depth):

191 lock_signal = 1
192 while node != -1 and tree_depth[node] >= top_depth:
193 h_parent = heavy_parent[node]
194 if top_depth <= tree_depth[h_parent]:
195 # Si on n'est pas sur le même chemin lourd que l'objectif, on le remonte
196 # complètement, et on remonte ensuite jusqu'au parent
197 # (cas 1 et 3 ensembles)
198 lock_signal = (lock_signal * segtree_query_prod(segtrees[h_parent], 0,
199 tree_depth[node] - tree_depth[h_parent] + 1)) % MOD
200 node = tree_parent[h_parent]
201 else:
202 # Cas 2 : on remonte jusqu'au noeud ancêtre objectif
203 lock_signal = (lock_signal * segtree_query_prod(segtrees[h_parent],
204 top_depth - tree_depth[h_parent],
205 tree_depth[node] - tree_depth[h_parent]+1)) % MOD
206 break
207 return lock_signal
208

209 # Plus petit ancêtre commun (construction de la structure)

210 def buildLcaTour(node):
211 global lca_cur_pos

30
212 lca_min_left[lca_cur_pos][0] = tree_depth[node]
213 lca_min_right[lca_cur_pos][0] = tree_depth[node]
214 node_lca_pos[node] = lca_cur_pos
215 lca_cur_pos += 1
216 for v in neighbors[node]:
217 buildLcaTour(v)
218 lca_min_left[lca_cur_pos][0] = tree_depth[node]
219 lca_min_right[lca_cur_pos][0] = tree_depth[node]
220 lca_cur_pos += 1
221

222

223 # ===== MAIN =====

224

225 # Transformer le graphe en arbre

226 merge_compos(0, -1) # On fusionne les composantes
227

228 # Puis on réassigne les arrêtes

229 for i_node in range(nb_nodes):
230 for v in cycle_neighbors[i_node]:
231 a, b = uf_find(i_node), uf_find(v)
232 if a != b:
233 neighbors[a].append(b)
234

235 assign_signal_in_compos() # Et on assigne chaque noeud du graphe à un noeud de l'arbre

236 root = uf_find(0) # On enracine l'arbre
237

238 # Chemins lourds

239 state[:] = [-1]*nb_nodes
240 find_heavy_child(root, -1, 0) # Trouver l'enfant le plus lourd pour chaque noeud
241 # Et construire les chemins lourds et les arbres binaires associés
242 build_heavy_paths(root)
243

244 # Construction de la structure pour le plus petit ancêtre commun

245 buildLcaTour(root)
246 for i in range(lca_cur_pos):
247 s = 1
248 while 1 << s <= i+1:
249 lca_min_left[i][s] = min(lca_min_left[i][s-1],
250 lca_min_left[i-(1 << (s-1))][s-1])
251 s += 1
252 for i in range(lca_cur_pos-1, -1, -1):
253 s = 1
254 while 1 << s <= lca_cur_pos - i:
255 lca_min_right[i][s] = min(lca_min_right[i][s-1],
256 lca_min_right[i + (1 << (s-1))][s-1])
257 s += 1
258

259

260 # Requêtes
261 for _ in range(nb_queries):
262 # Lecture de l'entrée et conversion des identifiants des noeuds du graphe
263 # vers ceux de l'arbre
264 set_at, set_signal, req_start, req_end = map(int, sys.stdin.readline().split())

31
265 change_compo = uf_find(set_at)
266 req_start, req_end = uf_find(req_start), uf_find(req_end)
267

268 # Modification de la valeur dans le sous-arbre binaire d'un noeud de l'arbre

269 # principal
270 segtree_set(compo_sig_tree[change_compo], i_leaf_of_signal[set_at], set_signal)
271 node_signal[change_compo] = compo_sig_tree[change_compo][1]
272 # Mise à jour de l'arbre binaire associé au chemin lourd du noeud modifié
273 segtree_set(segtrees[heavy_parent[change_compo]],
274 i_leaf_of_node[change_compo], node_signal[change_compo])
275

276 # Trouver la profondeur le plus petite ancêtre commun

277 if node_lca_pos[req_start] > node_lca_pos[req_end]:
278 req_start, req_end = req_end, req_start
279 s = 0
280 while 1 << (s+1) <= node_lca_pos[req_end] - node_lca_pos[req_start]+1:
281 s += 1
282 top_depth = min(lca_min_right[node_lca_pos[req_start]][s],
283 lca_min_left[node_lca_pos[req_end]][s])
284

285 # Effectuer les deux requêtes pour avoir le produit des valeurs sur un chemin
286 signal_left = get_lock_signal(req_start, top_depth)
287 signal_right = get_lock_signal(req_end, top_depth+1)
288 # Affichage
289 sys.stdout.write(f"{(signal_left * signal_right)%MOD}\n")
290

291 main()

***

Félicitations à tous les participantes et participants !

Nous avons tenté de rédiger une correction aussi claire que possible. Néanmoins, si vous avez des
questions, n’hésitez pas à nous contacter à l’adresse [email protected].

32