Meeting 12 Novembre 2016
Jussieu, room 26-25/105, from 9:00-12:00 only the ecole polytechnique teams, from 13:00-18:00 (+discussions) open to everyone.
Afternoon
Concours blanc. Bring one laptop per team. We will work on this contest.
[!] les notes ci-dessous sont en cours de rédaction.
P1 - Recurrences
Il s’agit d’un simple problème d’exponentiation rapide. On pose \(U(k) = [ [f(k)], [f(k+1)],\ldots , [f(k+d-1)] ]\), où \(U(k)\) est le vecteur colonne :
\[\left( \begin{array}{c} f(k)\\ f(k+1)\\ \vdots\\ f(k+d-1) \end{array} \right)\]Et on pose \(A\) la matrice de taille \(d\times d\)
\[\left( \begin{array}{cccccc} 0 &1 &0 &0 &\cdots &0\\ 0 &0 &1 &0 &\cdots &0\\ & & &\ddots & & \\ 0 &0 &0 &\cdots & 1 &0\\ 0 &0 &0 &\cdots & 0 &1\\ a_1& a_2 & a_3 &\cdots & a_{d-1} & a_d \end{array} \right)\]Du coup, on a \(U(k+1) = A \cdot U(k)\)
Ainsi, avec \(U(1)\) en entrée, il suffit de calculer \(A^{n-1} U(1) = U(n)\) et de prendre son premier coefficient (on pourrait l’obtenir avec \(U(n-d+1)\) mais on s’embrouille toujours dans les calculs de ce genre).
Attention, tous les calculs se font modulo m.
P2 - Leonardo’s Notebook
Il s’agit d’un problème de permutations. Toute une page de texte pour nous dire de décider si une permutation est un carré, pas très écologique tout ça. Pour cela, on considère la décomposition en cycles disjoints d’une permutation. On rappelle que la composition de deux cycles disjoints est commutative (ils agissent indépendamment).
On voit que si on met un cycle de longueur impaire au carré, on obtient un cycle de longueur impaire (car 2 est un générateur de \(\mathbb Z/n\mathbb Z\) avec \(n\) impair). Réciproquement, on peut facilement trouver la racine carrée d’un cycle impair car la multiplication par 2 est bijective dans \((\mathbb Z/n\mathbb Z)*\). Maintenant, si on met un cycle de longueur paire \(2n\) au carré, on obtient deux cycles de longueurs \(n\) (chacun correspond à l’orbite d’un élément).
Ainsi, dans la permutation d’arrivée, on peut déjà éliminer tous les cycles de longueur impaire, puisqu’on peut leur connaître une racine. Maintenant par analyse - synthèse, si la permutation est un carré, comme on a éliminé tous les cycles impairs, c’est qu’il n’y avait que des cycles pairs dans la racine. Ainsi, une CNS est qu’il y a un nombre pair de cycles de longueur \(2k\) pour tout \(k\).
Il suffit donc de partir de chaque élément et d’itérer la permutation en comptant le nombre d’itérations, et on incrémente le tableau compteur de nombres de cycles pour cette longueur. A la fin, on vérifie qu’il y a un nombre pair dans toutes les cases d’indice pair. On n’a même pas besoin d’optimiser la décomposition en cycles (avec un bool[] visited, le pire cas étant un seul cycle de longueur 26 et la complexité étant alors 26*26, et 26*26*500 = 338 000).
Notes
-
Une approche possible donc. Initialement C est une liste vide qui contiendra les longueurs de cycles pairs. Et
visitedun tableau boolean encore tout faux. Puis:-
Pour toute lettre pas encore visité. Marquer visite et passer à la lettre suivante comme spécifiée par la permutation. Jusqu’à ce qu’on rencontre un sommet déjà visité. Alors ajouter à C la longueur du cycle dans le cas où elle est paire.
-
Trier C, et vérifier que la longueur de C est pair et que
C[2*i]==C[2*i+1]pour tout i.
-
En interne travailler avec des entiers basés à 0 plutôt que des caractères. Utilisez l’arithmétique sur les caractères. Alors une partie du code pourrait avoir la forme suivante.
string perm;
cin >> perm;
// etc.
for (int i=0; i < 26; i++) {
if (!visited[i]) {
int longueur_cycle = 0;
for (longueur_cycle; !visited[i]; longueur_cycle++)
i = perm[i] - 'A';
}
// etc.
}P3 - Boxes of Chocolates Again
Il s’agit d’un problème de rendu de monnaie : combien de manières y a-t-il de décomposer N en plus petits nombres sans compter l’ordre ?
L’algorithme dynamique “naïf” tourne mais il faut faire un petit effort pour le voir : tab[i][j] contient le nombre de décompositions de j en nombres plus petits ou égaux à i (en fait on peut simplement avoir deux tableaux puisque tab[i] se calcule avec tab[i-1]) Pour chaque i et j, tab[i][j] = sum( tab[i-1][j - k] for k in range(0, j, i) ) (on partitionne selon le nombre de boîtes de taille i utilisées) On initialise avec tout à 0 sauf tab[0][0] = 1.
Cet algorithme est trivialement en \(O(n^3)\), ce qui ne passe pas. Cependant, quand on y regarde de plus près, tab[i][j] se calcule en \(O(j/i)\), donc en fait la complexité totale est (je sais, je somme les O, c’est pas légal mais les constantes sont les mêmes donc c’est bon, je les factorise aussi, mais ça marche, il faut savoir que l’égalité avec les O n’est pas commutative : si \(f = O(n), f = O(n^2)\) mais l’inverse est en général faux, fin de la remarque sur les O) :
\(O(\sum\sum j/i) = O(\sum j)O(\sum 1/i) = O(n^2)\cdot O(\log(n))\) car la série harmonique est équivalente à \(\log(n)\)
Ainsi, l’algo tourne en \(O(n^2\cdot\log(n))\), et pour \(n = 5000\), ça passe sûrement (on ne sait pas combien il y a de lignes).
Notes
- La difficulté principale est de faire de l’arithmétique sur des entiers à précision arbitraire. Les utilisateurs de Python et de Java sont avantagés. Mais depuis quelques années il n’y a plus de problème dans SWERC nécessitant ces BigIntegers. C’est officiel.
P4 - Chandelier
Cet exercice est plus difficile que les autres. On va modéliser les chandeliers avec des listes doublement chaînées (deque). C’est un problème récursif : pour construire \(\langle s_1, s_2, \ldots, s_k \rangle\) dans cet ordre, on doit construire chaque \(s_i\) à la suite des autres, donc si \(s_i\) est constructible avec une pile de taille \(n_i\), on utilisera une pile de taille \(i - 1 + n_i\), donc la construction de l’arbre total utilisera le maximum des \(i - 1 + n_i\).
Si on résout le problème pour \(s1,\ldots , s_k\), alors on obtient les \(n_i\). Il faut donc trouver la permutation circulaire qui minimise le maximum des \(i - 1 + n_i\). On a donc trouvé un sous-problème.
Maintenant, on considère donc juste une liste de nombres \(n_1, \ldots, n_k\) et on leur applique avec l’addition un “masque” \(0, 1, \ldots, k-1\) que l’on peut faire tourner de manière circulaire. Avec un autre masque cela demanderait \(O(k^2)\) opérations — peut-être \(O(n*log(n))\) — avec une transformée de Fourier magique mais je ne sais pas le faire), mais là on peut le faire de manière astucieuse. On commence par appliquer le masque non décalé. Maintenant, passer d’une position du masque à la suivante revient à enlever -1 à tous les nombres et à rajouter k au nombre qui avait 0 : élément par élément, \([0, 1, \ldots, k-1] - [1, 2, \ldots, k-1, 0] = [-1, -1, \ldots, -1, k-1]\). Tout ce qu’on veut faire, c’est maintenir le max de cette liste en passant d’une position à la suivante. Or lorsqu’on effectue cette opération, on diminue tous les indices sauf 1, et on connaît cet indice (il va de \(0\) à \(k-1\)). De plus, au moment où on l’augmente après \(i\) opérations, on l’augmente de \(k\) après l’avoir diminué de \(i\), donc on connaît sa valeur. Ainsi, pour mettre à jour le max à l’étape \(i\), il suffit de le comparer au nombre qu’on vient d’augmenter : en supposant que le max précédent était correct, s’il est situé à un autre indice que \(i-1\) (le nombre qu’on augmente à l’étape \(i\)), il a forcément diminué de 1.
On a donc résolu le sous-problème en temps linéaire. Ainsi, en notant \(T\) le temps d’exécution de l’algorithme, \(T(\langle s_1, s_2, \ldots, s_k \rangle) = O(k) + \sum T(s_i)\). Puisque le codage d’un arbre est linéaire en sa taille, i.e. \(\textrm{len}(\langle s_1, s_2, \ldots, s_k \rangle) = \sum \textrm{len}(s_i)\), on a un algorithme linéaire.
P5 - Ping pong
Le problème est difficile à lire, il faut comprendre que si \(i\) et \(j\) sont arbitrés par \(k\), alors on a à la fois (\(i < k < j\) ou \(j < k < i\)) et (\(\textrm{rank}[i] < \textrm{rank}[k] < \textrm{rank}[j]\) ou \(\textrm{rank}[j] < \textrm{rank}[k] < \textrm{rank}[i]\)) (les inégalités sont strictes car l’id est unique). C’est vraiment tordu de dire “The contestants have to walk to the referee’s house, and because they are lazy, they want to make their total walking distance no more than the distance between their houses.” pour (\(i < k < j\) ou \(j < k < i\)). Puisqu’une partie est symétrique, on peut supposer \(i < k < j\). On veut donc le nombre de tels triplets vérifiant \(\textrm{rank}[i] < \textrm{rank}[k] < \textrm{rank}[j]\) ou \(\textrm{rank}[j] < \textrm{rank}[k] < \textrm{rank}[i]\).
Cependant, si on cherche à résoudre le problème pour un arbitre k donné, il suffit de connaître le nombre de joueurs à gauche/droite ayant un rang plus petit/grand. Ensuite on fait une somme des produits croisés pour obtenir le nombre de matches arbitrés par \(k\).
On a de la chance, les rangs des joueurs sont compris entre 1 et 100000, on n’a même pas besoin de les “discrétiser”. On peut donc utiliser un arbre (tableau) de Fenwick (très pratique quand on peut, c’est simple à manipuler et court à programmer). A titre d’exemple, voici une implémentation en Python :
class Fenwick(list):
def __init__(self, n):
self.n = n
super().__init__([0] * n)
def add(self, i, val):
"""Ajoute val à l'indice i"""
i = i + 1
while i <= self.n:
self[i - 1] += val
i += i & -i
def sum(self, i):
"""Renvoie la somme des indices 0...i-1"""
val = 0
while i > 0:
val += self[i - 1]
i -= i & -i
return val
def get(self, i):
"""Renvoie l'élément d'indice i"""
return self.sum(i + 1) - self.sum(i)
def set(self, i, val):
"""Fixe l'élément d'indice i"""
self.add(i, val - self.get(i))
if __name__ == '__main__':
fen = Fenwick(5)
assert [fen.get(i) for i in range(5)] == [0, 0, 0, 0, 0]
fen.set(2, 3)
assert [fen.get(i) for i in range(5)] == [0, 0, 3, 0, 0]
fen.set(4, 2)
assert [fen.get(i) for i in range(5)] == [0, 0, 3, 0, 2]
fen.set(0, 1)
assert [fen.get(i) for i in range(5)] == [1, 0, 3, 0, 2]Pour résoudre le sous-problème, par exemple pour les joueurs situés à gauche, on a juste à parcourir la liste de gauche à droite en appelant à chaque fois fenwick.add(rank[k], 1). Pour connaître le nombre de joueurs de rang plus petits que \(k\) déjà lus (i.e. habitant à gauche), il suffit d’appeler fenwick.sum(rank[k]). Pour les plus grands, on peut simplement faire k - fenwick.sum(rank[k]) pour ne pas s’embêter avec des indices. On peut stocker ces deux listes de valeurs dans un tableau, puis faire la même chose de droite à gauche. Ensuite, un simple parcours permet d’obtenir le résultat en tant que somme des produits croisés.
Chaque parcours utilise un temps \(O(N \cdot \log( \textrm{max_rank} ))\) avec N ≤ 20 000 et max_rank ≤ 100 000. La lecture et la somme finale sont en \(O(N)\) donc le tout est en \(O(N \cdot \log( \textrm{max_rank} ))\).
Remarque : Même si max_rank n’était pas borné, on aurait quand même du \(O(N\cdot\log(N))\) car on peut utiliser un dictionnaire pour “discrétiser” le problème en remplaçant les indices par les nombres de 0 à \(N-1\).
Autre solution
- voir ici une approche basée sur le tri par fusion
P6 - Insurrection
Chercher du côté de Mininium cost flow
P7 - Ancient vending machine
Le problème le plus dégueulasse (comme dit JJ, “si M = N = 20, c’est forcément dégueulasse”). Il faut déterminer deux grandeurs puis les comparer : A et B
A. La “largeur” minimale de la pièce qu’on peut obtenir en la faisant tourner, i.e. la distance minimale d entre deux droites parallèles du plan telles que la pièce soit contenue dans la bande de largeur d. Cette partie est jolie (!).
En effet, si la pièce est contenue dans une bande de largeur d, l’enveloppe convexe de la pièce sera contenue dans l’enveloppe convexe de la bande (si U est inclus dans V, l’enveloppe convexe de U est incluse dans celle de V), et alors comme cette bande est convexe, l’enveloppe convexe de la pièce est contenue dans la bande. Or pour une pièce convexe, la largeur de la bande est égale à la plus petite distance entre un bord de la pièce et un sommet. Cela se voit géométriquement (si oui, on peut sauter le paragraphe suivant), sinon on suppose par l’absurde qu’aucun des bords ne touche une droite, on peut supposer que chaque droite touche un sommet. Alors une rotation infinitésimale du polygone en conservant un point d’attache sur une droite sera encore dans la bande puisqu’aucun bord ne touchait une droite, et si on choisit le sens tel que la distance entre le second point de contact et la droite d’attache diminue, on contredit la minimalité de la distance entre les deux droites.
Ainsi, il suffit de calculer l’enveloppe convexe puis de tester chaque couple (sommet, côté), il y en a \(n (n-1)\), complexité totale \(O( n \log(n) + n^2) = O(n^2) = O(N^2)\) avec n le nombre de points de l’enveloppe convexe.
B. La longueur du plus grand segment entièrement contenu dans le trou. Pour cela, on peut montrer que cet extremum est obtenu avec un segment touchant deux sommets du trou. En effet, sinon le segment est délimité par deux côtés. Alors dans une petite bande autour du segment il n’y aura aucun sommet, donc les seuls éléments de la frontière du trou seront les intersections des deux côtés avec la bande. Maintenant on peut même fixer une des extrémités du segment, la mobilité de l’autre sur un petit bout de segment suffit. Mathématiquement, on note a le point immobile, \(b + x t\) celui qui bouge où \(x\) est la direction et \(t\) un scalaire petit. On a alors
\[\begin{align*} d(a, b+xt)^2 &= \langle b+x t - a, b+xt - a\rangle \\&= d(a, b)^2 + 2 t \langle x, b - a\rangle + t^2 * d(0, x)^2 \\&= d(a, b)^2 + 2 t \langle x, b - a \rangle + o(t). \end{align*}\]Si le segment n’est pas perpendiculaire au bord, \(\langle x, b-a \rangle\) est non nul donc il suffit de prendre \(t\) de même signe. Sinon, le terme d’ordre 2 est strictement positif (c’est en fait le théorème de Pythagore, l’hypoténuse est bien le plus grand côté du triangle), et on augmente encore la distance.
Ainsi, il faut tester pour chaque couple de sommets la longueur du plus long segment inclus dans le trou passant par ces deux sommets. Cela se fait donc en O(nombre de couples de sommets * nombre de segments) = \(O(M^3)\). Je ne détaillerai pas les calculs géométriques horribles qu’il faut faire.
Enfin, il suffit de renvoyer ‘legal’ si A <= B et ‘illegal’ sinon.
P9 - Calculator Conundrum
On n’a vraiment aucun outil pour évaluer la complexité, il s’agit d’un brute force. Le piège est qu’on peut boucler sans repasser par le point de départ, il faut donc détecter les cycles. Pour cela le plus simple est la technique Baby step giant step. Attention, quand baby_step = giant_step, on n’a parcouru qu’un élément sur deux de la boucle avec giant_step. Le plus simple est de maintenir le max avec baby_step et de parcourir toute la boucle une fois qu’on l’a trouvée.
P10 - Animal Run
On pourrait résoudre ce problème avec un min-cut, mais il est beaucoup plus simple d’en faire un plus court chemin puisque le graphe est planaire. Une coupe est équivalente à relier les côtés NE aux côtés SW. On peut construire le graphe de la manière suivante : un noeud par zone de la grille, sauf l’extérieur où on a deux noeuds, NE et SW. On relie deux noeuds par une arête de même poids que la ligne qui les sépare sur le plan du zoo.
Et donc c’est un problème qui se résoud par l’algorithm des plus court chemins de Dijkstra.