{"cells": [{"cell_type": "markdown", "metadata": {}, "source": ["# 2A.algo - Puzzles algorithmiques (1)\n", "\n", "Puzzles algorithmiques tir\u00e9s de [Google Code Jam](https://code.google.com/codejam/) et autres sites \u00e9quivalents, produits scalaires, probl\u00e8mes de recouvrements, soudoyer les prisonniers, d\u00e9coupage stratifi\u00e9."]}, {"cell_type": "code", "execution_count": 1, "metadata": {"ExecuteTime": {"end_time": "2016-11-06T22:17:04.866129", "start_time": "2016-11-06T22:17:04.763507"}}, "outputs": [{"data": {"text/html": ["
run previous cell, wait for 2 seconds
\n", ""], "text/plain": [""]}, "execution_count": 2, "metadata": {}, "output_type": "execute_result"}], "source": ["from jyquickhelper import add_notebook_menu\n", "add_notebook_menu()"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Produits scalaires\n", "\n", "Le probl\u00e8me est tir\u00e9 de [Google Jam 2008, round 1A](https://code.google.com/codejam/contest/32016/dashboard#s=p0).\n", "\n", "On consid\u00e8re 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\u00f9 $\\sigma,\\sigma'$ sont deux permutations de l'ensemble $[[1,...,n]]$."]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Solution na\u00efve"]}, {"cell_type": "code", "execution_count": 2, "metadata": {"collapsed": true}, "outputs": [], "source": []}, {"cell_type": "markdown", "metadata": {}, "source": ["### Solution moins na\u00efve"]}, {"cell_type": "code", "execution_count": 3, "metadata": {"collapsed": true}, "outputs": [], "source": [" "]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Probl\u00e8me de recouvrement\n", "\n", "[Google Jam 2008, round 1A](https://code.google.com/codejam/contest/32016/dashboard#s=p0)\n", "\n", "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}$.\n", "\n", "Exemple, couvrir $[0, 1]$ avec les intervalles $[-1, 0]$, $[-5, -3]$, $[2, 5]$."]}, {"cell_type": "code", "execution_count": 4, "metadata": {"collapsed": true}, "outputs": [], "source": []}, {"cell_type": "markdown", "metadata": {}, "source": ["## Soudoyer les prisonniers\n", "\n", "[Problem C. Bribe the Prisoners](https://code.google.com/codejam/contest/189252/dashboard#s=p2)\n", "\n", "Dans un royaume il y a des cellules de prison num\u00e9rot\u00e9es de 1 \u00e0 $P$ construites de telle sorte \u00e0 former un segment de ligne droite. Les cellules $i$ et $i + 1$ sont adjacentes et leur prisonniers sont appel\u00e9s \"voisins\". Un mur muni d'une fen\u00eatre les s\u00e9pare et ils peuvent communiquer via cette fen\u00eatre. Tous les prisonniers vivent en paix jusqu'a ce qu'un prisonnier soit rel\u00e2ch\u00e9. Quand cela se produit, le prisonnier lib\u00e9r\u00e9 fait part de la nouvelle \u00e0 ses voisins, qui en parlent \u00e0 leurs voisins, etc., jusqu'\u00e0 atteindre la cellule 1 ou $P$ ou une cellule dont la cellule voisine est vide. Quand un prisonnier d\u00e9couvre qu'un autre prisonnier a \u00e9t\u00e9 lib\u00e9r\u00e9, de col\u00e8re, il casse tout dans sa cellule, sauf s'il a \u00e9t\u00e9 pr\u00e9alablement soudoy\u00e9 par une pi\u00e8ce\n", "d'or. Il faut donc veiller \u00e0 soudoyer tous les prisonniers susceptibles de tout casser dans leur cellule avant de lib\u00e9rer un prisonnier. En supposant que toutes les cellules sont initialement occup\u00e9es par un unique prisonnier et qu'un prisonnier par jour au plus puisse \u00eatre relach\u00e9, et en connaissant la liste des $Q$ prisonniers \u00e0 rel\u00e2cher, il faut trouver l'ordre de lib\u00e9ration des prisonniers de cette liste qui soit le moins co\u00fbteux en pi\u00e8ce 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.\n", "\n", "Exemple : 23 prisonniers, $P=20$, $Q=3$, les prisonniers \u00e0 lib\u00e9rer sont les num\u00e9ros $3, 6, 14$."]}, {"cell_type": "code", "execution_count": 5, "metadata": {"collapsed": true}, "outputs": [], "source": []}, {"cell_type": "markdown", "metadata": {}, "source": ["## D\u00e9coupage intelligent d'une base de donn\u00e9es\n", "\n", "On dispose d'une base de donn\u00e9es \u00e0 $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.\n", "\n", "On souhaite maintenant diviser la base en deux bases apprentissage de taille \u00e9gale, test sous intersection. On mesure \u00e9galement la moyenne de chaque variable sur chacun des deux bases : $\\bar{X^k}_a$ et $\\bar{X^k}_t$. On souhaite effectuer un d\u00e9coupage de telle sorte que l'indicateur suivant soit minimum : \n", "\n", "$E = \\sum_{k=1}^K \\left( \\bar{X^k_a} - \\bar{X^k_t} \\right)^2$\n", "\n", "Imaginer un algorithme qui effectue un tel d\u00e9coupage."]}, {"cell_type": "code", "execution_count": 6, "metadata": {"collapsed": true}, "outputs": [], "source": []}], "metadata": {"kernelspec": {"display_name": "Python 3", "language": "python", "name": "python3"}, "language_info": {"codemirror_mode": {"name": "ipython", "version": 3}, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.2"}}, "nbformat": 4, "nbformat_minor": 2}