Eléments de réponses pour des puzzles algorithmiques tirés de Google Code Jam et autres sites équivalents, nombres premiers, écoulement d'eau, séparation des bagarreurs, formation de binômes.
from jyquickhelper import add_notebook_menu
add_notebook_menu()
On propose la conjecture suivante :
Si $(a,b)$ sont premiers entre eux et si $(b,c)$ sont premiers entre eux alors $(a,c)$ sont premiers entre eux.
On veut montrer que cette conjecture est fausse. Pour cela, il faut trouver trois entiers $(a,b,c)$ pour lesquels l'énoncé est faux et on les cherche tels qu'il existe deux entiers $l<r$ :
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.
Geologists sometimes divide an area of land into different regions based on where rainfall flows down to. These regions are called drainage basins.
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.
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'.)
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.
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.
L'ordre dans lequel l'appariement sont envisagés n'a pas d'importance (contrairement à l'appariement de deux séquences d'ADN). Alors, une direction possible aurait été un algorithme du type distance de Levenstein.
Dans ce problème est un problème d'appariment ou de couplage dans un graphe bi-parti. Plusieurs algorithmes approchés existent pour résoudre ce problème :
L'algorithme optimal retourne la solution optimale en un temps polynômial : Blossom algorithm.