2A.algo - Puzzles algorithmiques (1)#

Links: notebook, html, python, slides, GitHub

Puzzles algorithmiques tirés de Google Code Jam et autres sites équivalents, produits scalaires, problèmes de recouvrements, soudoyer les prisonniers, découpage stratifié.

from jyquickhelper import add_notebook_menu
add_notebook_menu()

Produits scalaires#

Le problème est tiré de Google Jam 2008, round 1A.

On considère deux tableaux v=(v_1,..., v_n) et w=(w_1,...,w_n). On souhaite le minimum :

\min_{\sigma,\sigma'} \sum_{i=1}^{n} v_{\sigma(i)} w_{\sigma'(i)}

où \sigma,\sigma' sont deux permutations de l’ensemble [[1,...,n]].

Solution naïve#

Solution moins naïve#

Problème de recouvrement#

Google Jam 2008, round 1A

Couvrir le segment [0, M] avec le nombre minimum d’intervalles de la forme [a_i, b_i] ? Avec M, a_i b_i \in \mathbb{N}.

Exemple, couvrir [0, 1] avec les intervalles [-1, 0], [-5, -3], [2, 5].

Soudoyer les prisonniers#

Problem C. Bribe the Prisoners

Dans un royaume il y a des cellules de prison numérotées de 1 à P construites de telle sorte à former un segment de ligne droite. Les cellules i et i + 1 sont adjacentes et leur prisonniers sont appelés “voisins”. Un mur muni d’une fenêtre les sépare et ils peuvent communiquer via cette fenêtre. Tous les prisonniers vivent en paix jusqu’a ce qu’un prisonnier soit relâché. Quand cela se produit, le prisonnier libéré fait part de la nouvelle à ses voisins, qui en parlent à leurs voisins, etc., jusqu’à atteindre la cellule 1 ou P ou une cellule dont la cellule voisine est vide. Quand un prisonnier découvre qu’un autre prisonnier a été libéré, de colère, il casse tout dans sa cellule, sauf s’il a été préalablement soudoyé par une pièce d’or. Il faut donc veiller à soudoyer tous les prisonniers susceptibles de tout casser dans leur cellule avant de libérer un prisonnier. En supposant que toutes les cellules sont initialement occupées par un unique prisonnier et qu’un prisonnier par jour au plus puisse être relaché, et en connaissant la liste des Q prisonniers à relâcher, il faut trouver l’ordre de libération des prisonniers de cette liste qui soit le moins coûteux en pièce d’or. Ordres de grandeur : 1 \leqslant P \leqslant 104, 1 \leqslant Q \leqslant 102. A noter que le soudoiement n’est actif qu’un seul jour.

Exemple : 23 prisonniers, P=20, Q=3, les prisonniers à libérer sont les numéros 3, 6, 14.

Découpage intelligent d’une base de données#

On dispose d’une base de données à N observations et K variables (X^1,...,X^K). On calcule la moyenne de chaque variable \bar{X_k} =\frac{1}{N}\sum_{i=1}^N X^k_i sur l’ensemble de la base.

On souhaite maintenant diviser la base en deux bases apprentissage de taille égale, test sous intersection. On mesure également la moyenne de chaque variable sur chacun des deux bases : \bar{X^k}_a et \bar{X^k}_t. On souhaite effectuer un découpage de telle sorte que l’indicateur suivant soit minimum :

E = \sum_{k=1}^K \left( \bar{X^k_a} - \bar{X^k_t} \right)^2

Imaginer un algorithme qui effectue un tel découpage.