{"cells": [{"cell_type": "markdown", "metadata": {}, "source": ["# 2A.algo - Puzzles algorithmes (2) - correction\n", "\n", "El\u00e9ments de r\u00e9ponses pour des puzzles algorithmiques tir\u00e9s de [Google Code Jam](https://code.google.com/codejam/) et autres sites \u00e9quivalents, nombres premiers, \u00e9coulement d'eau, s\u00e9paration des bagarreurs, formation de bin\u00f4mes."]}, {"cell_type": "code", "execution_count": 1, "metadata": {"ExecuteTime": {"end_time": "2016-11-06T22:48:08.653795", "start_time": "2016-11-06T22:48:08.645777"}}, "outputs": [{"data": {"text/html": ["<div id=\"my_id_menu_nb\">run previous cell, wait for 2 seconds</div>\n", "<script>\n", "function repeat_indent_string(n){\n", "    var a = \"\" ;\n", "    for ( ; n > 0 ; --n) {\n", "        a += \"    \";\n", "    }\n", "    return a;\n", "}\n", "var update_menu_string = function(begin, lfirst, llast, sformat, send, keep_item) {\n", "    var anchors = document.getElementsByClassName(\"section\");\n", "    if (anchors.length == 0) {\n", "        anchors = document.getElementsByClassName(\"text_cell_render rendered_html\");\n", "    }\n", "    var i,t;\n", "    var text_menu = begin;\n", "    var text_memo = \"<pre>\\nlength:\" + anchors.length + \"\\n\";\n", "    var ind = \"\";\n", "    var memo_level = 1;\n", "    var href;\n", "    var tags = [];\n", "    var main_item = 0;\n", "    for (i = 0; i <= llast; i++) {\n", "        tags.push(\"h\" + i);\n", "    }\n", "\n", "    for (i = 0; i < anchors.length; i++) {\n", "        text_memo += \"**\" + anchors[i].id + \"--\\n\";\n", "\n", "        var child = null;\n", "        for(t = 0; t < tags.length; t++) {\n", "            var r = anchors[i].getElementsByTagName(tags[t]);\n", "            if (r.length > 0) {\n", "child = r[0];\n", "break;\n", "            }\n", "        }\n", "        if (child == null){\n", "            text_memo += \"null\\n\";\n", "            continue;\n", "        }\n", "        if (anchors[i].hasAttribute(\"id\")) {\n", "            // when converted in RST\n", "            href = anchors[i].id;\n", "            text_memo += \"#1-\" + href;\n", "            // passer \u00e0 child suivant (le chercher)\n", "        }\n", "        else if (child.hasAttribute(\"id\")) {\n", "            // in a notebook\n", "            href = child.id;\n", "            text_memo += \"#2-\" + href;\n", "        }\n", "        else {\n", "            text_memo += \"#3-\" + \"*\" + \"\\n\";\n", "            continue;\n", "        }\n", "        var title = child.textContent;\n", "        var level = parseInt(child.tagName.substring(1,2));\n", "\n", "        text_memo += \"--\" + level + \"?\" + lfirst + \"--\" + title + \"\\n\";\n", "\n", "        if ((level < lfirst) || (level > llast)) {\n", "            continue ;\n", "        }\n", "        if (title.endsWith('\u00b6')) {\n", "            title = title.substring(0,title.length-1).replace(\"<\", \"&lt;\").replace(\">\", \"&gt;\").replace(\"&\", \"&amp;\")\n", "        }\n", "\n", "        if (title.length == 0) {\n", "            continue;\n", "        }\n", "\n", "        while (level < memo_level) {\n", "            text_menu += \"</ul>\\n\";\n", "            memo_level -= 1;\n", "        }\n", "        if (level == lfirst) {\n", "            main_item += 1;\n", "        }\n", "        if (keep_item != -1 && main_item != keep_item + 1) {\n", "            // alert(main_item + \" - \" + level + \" - \" + keep_item);\n", "            continue;\n", "        }\n", "        while (level > memo_level) {\n", "            text_menu += \"<ul>\\n\";\n", "            memo_level += 1;\n", "        }\n", "        text_menu += repeat_indent_string(level-2) + sformat.replace(\"__HREF__\", href).replace(\"__TITLE__\", title);\n", "    }\n", "    while (1 < memo_level) {\n", "        text_menu += \"</ul>\\n\";\n", "        memo_level -= 1;\n", "    }\n", "    text_menu += send;\n", "    //text_menu += \"\\n\" + text_memo;\n", "    return text_menu;\n", "};\n", "var update_menu = function() {\n", "    var sbegin = \"\";\n", "    var sformat = '<li><a href=\"#__HREF__\">__TITLE__</a></li>';\n", "    var send = \"\";\n", "    var keep_item = -1;\n", "    var text_menu = update_menu_string(sbegin, 2, 4, sformat, send, keep_item);\n", "    var menu = document.getElementById(\"my_id_menu_nb\");\n", "    menu.innerHTML=text_menu;\n", "};\n", "window.setTimeout(update_menu,2000);\n", "            </script>"], "text/plain": ["<IPython.core.display.HTML object>"]}, "execution_count": 2, "metadata": {}, "output_type": "execute_result"}], "source": ["from jyquickhelper import add_notebook_menu\n", "add_notebook_menu()"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Exercice 1 : nombres premiers\n", "\n", "[CodeForces 483A](http://codeforces.com/problemset/problem/483/A)\n", "\n", "On propose la conjecture suivante :\n", "    \n", "Si $(a,b)$ sont premiers entre eux et si $(b,c)$ sont premiers entre eux alors $(a,c)$ sont premiers entre eux.\n", "\n", "On veut montrer que cette conjecture est **fausse**. Pour cela, il faut trouver trois entiers $(a,b,c)$ pour lesquels l'\u00e9nonc\u00e9 est faux et on les cherche tels qu'il existe deux entiers $l<r$ :\n", "\n", "* $l \\leqslant a < b < c \\leqslant r$\n", "* $1 \\leqslant l \\leqslant r  \\leqslant  10^{18}$\n", "* $r - l \\leqslant 50$"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Premi\u00e8re id\u00e9e\n", "\n", "On peut chercher $(a,b,c)$ de la forme $2n, 2n+1, 2n+2$. On peut trouver $n$ tel que $(2n,2n+1)$, $(2n+1,2n+2)$ soient premiers eux. $(2n, 2n+2)$ ne le seront pas. Exemple : 4,5,6."]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Seconde id\u00e9e : les trouver tous ?\n", "    \n", "   "]}, {"cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": []}, {"cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": []}, {"cell_type": "markdown", "metadata": {}, "source": ["## Exercice 2 : watersheds\n", "\n", "[Google Code Jam 2009](https://code.google.com/codejam/contest/90101/dashboard#s=p1)\n", "                       \n", "Geologists sometimes divide an area of land into different regions based on where rainfall flows down to. These regions are called drainage basins.\n", "\n", "Given an elevation map (a 2-dimensional array of altitudes), label the map such that locations in the same drainage basin have the same label, subject to the following rules.\n", "\n", "* From each cell, water flows down to at most one of its 4 neighboring cells.\n", "* For each cell, if none of its 4 neighboring cells has a lower altitude than the current cell's, then the water does not flow, and the current cell is called a sink.\n", "* Otherwise, water flows from the current cell to the neighbor with the lowest altitude.\n", "*  In case of a tie, water will choose the first direction with the lowest altitude from this list: North, West, East, South.\n", "\n", "Every cell that drains directly or indirectly to the same sink is part of the same drainage basin. Each basin is labeled by a unique lower-case letter, in such a way that, when the rows of the map are concatenated from top to bottom, the resulting string is lexicographically smallest. (In particular, the basin of the most North-Western cell is always labeled 'a'.)"]}, {"cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": []}, {"cell_type": "markdown", "metadata": {}, "source": ["## Exercice 3 : s\u00e9paration des bagarreurs\n", "\n", "[Google Code Jam 2014](https://code.google.com/codejam/contest/2933486/dashboard#s=p0)\n", "\n", "As the leader of the Evil League of Evil, Bad Horse has a lot of problems to deal with. Most recently, there have been far too many arguments and far too much backstabbing in the League, so much so that Bad Horse has decided to split the league into two departments in order to separate troublesome members. Being the Thoroughbred of Sin, Bad Horse isn't about to spend his valuable time figuring out how to split the League members by himself. That what he's got you -- his loyal henchman -- for."]}, {"cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [], "source": []}, {"cell_type": "markdown", "metadata": {}, "source": ["## Exercice 4 : formation de bin\u00f4mes\n", "\n", "[UVa 10911](http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1852)\n", "\n", "You have been given the job of forming the quiz teams for the next 'MCA CPCI Quiz Championship'. There are $2N$ students interested to participate and you have to form $N$ teams, each team consisting of two members. Since the members have to practice together, all the students want their member's house as near as possible. Let $x_1$ be the distance between the houses of group 1, $x_2$ be the distance between the houses of group 2 and so on. You have to make sure the summation ($x_1 + x_2 + x_3 + ... + x_n$) is minimized."]}, {"cell_type": "markdown", "metadata": {}, "source": ["### solution"]}, {"cell_type": "markdown", "metadata": {}, "source": ["L'ordre dans lequel l'appariement sont envisag\u00e9s n'a pas d'importance (contrairement \u00e0 l'appariement de deux s\u00e9quences d'ADN). Alors, une direction possible aurait \u00e9t\u00e9 un algorithme du type [distance de Levenstein](http://en.wikipedia.org/wiki/Levenshtein_distance).\n", "\n", "Dans ce probl\u00e8me est un probl\u00e8me d'[appariment](http://fr.wikipedia.org/wiki/Couplage_%28th%C3%A9orie_des_graphes%29) ou de couplage dans un [graphe bi-parti](http://fr.wikipedia.org/wiki/Graphe_biparti). Plusieurs algorithmes approch\u00e9s existent pour r\u00e9soudre ce probl\u00e8me :\n", "\n", "* [la m\u00e9thode hongroise](http://fr.wikipedia.org/wiki/Algorithme_hongrois)\n", "* [algorithme de Floyd Fulkerson](http://fr.wikipedia.org/wiki/Algorithme_de_Ford-Fulkerson) (algorithme exact mais qui r\u00e9pond au probl\u00e8me de flot maximal)\n", "* [l'algorithme de Hopcroft\u2013Karp](https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm)\n", "\n", "L'algorithme optimal retourne la solution optimale en un temps polyn\u00f4mial : [Blossom algorithm](http://en.wikipedia.org/wiki/Blossom_algorithm)."]}, {"cell_type": "code", "execution_count": 6, "metadata": {}, "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.6.1"}}, "nbformat": 4, "nbformat_minor": 2}