Puzzles algorithmes (1) - correction#
Eléments de réponses pour des puzzles algorithmiques tirés de Google Code Jam et autres sites équivalents, produits scalaires, problèmes de recouvrements, soudoyer les prisonniers, découpage stratifié.
Produits scalaires#
Google Jam 2008, round 1A
On considère deux tableaux et . On souhaite le minimum : où sont deux permutations de l’ensemble .
Problème de recouvrement#
Première solution#
Elle est inspiré de la distance d’édition. Si on doit recouvrir l’ensemble des entiers , on passe en revue tous les intervalles qui inclut 0. On construit deux tableaux :
: conserve le nombre minimum d’intervalles pour couvrir tous les entiers de à
: conserver le dernier intervalle utilisé pour recouvrir
On commence par initialiser en passant en revue tous les intervalles qui inclut 0. Pour trouver , on passe en revue tous les intervalles , et on affirme que:
Le tableau conserve l’intervalle qui minimise le problème de minimisation précédent.
Une fois les tableaux et renseigné, on utilise le tableaux pour retrouver la solution.
[1]:
def recouvrement(B, intervalles):
# initialisation
entier = {}
pred = {}
for a, b in intervalles:
if 0 <= a <= B:
for k in range(0, b + 1):
entier[k] = 1
pred[k] = (a, b)
# programmation dynamique
i = 0
while i <= B:
mini = None
best = None
for a, b in intervalles:
if a <= i <= b:
a = max(0, a)
for l in range(a, b + 1):
if l in entier:
d = entier[l] + 1
if mini is None or d < mini:
mini = d
best = (a, b)
entier[i] = d
pred[i] = best
i += 1
# on retourne la solution
if B in entier:
sol = []
while B > 0:
p = pred[B]
m = max(0, p[0])
sol.append(p)
B = p[0]
sol.reverse()
return sol
else:
# la solution n'existe pas
return None
b = 1
intervalles = [(-1, 0), (0, 1), (0, 0)]
print("sol=", recouvrement(b, intervalles))
sol= [(0, 1)]
Seconde solution#
Ce programme améliore la solution précédente.
[2]:
from IPython.core.display import Image
Image("inter.png", width=500)
[2]:
[3]:
# solution par Benjamin DONNOT
def solve(B, intervalles):
res = []
upper = 0
while True:
aux = []
for x in intervalles:
if x[0] <= upper:
aux.append(x)
new_intervalles = []
for x in intervalles:
new_intervalles.append(x)
intervalles = new_intervalles
if aux == []:
return "0\n"
mymax = max(aux, key=lambda x: x[1])
res.append(mymax)
upper = mymax[1]
if upper >= B:
break
return res
b = 1
intervalles = [(-1, 0), (0, 1), (0, 0)]
print("sol=", solve(b, intervalles))
sol= [(0, 1)]
Soudoyer les prisonniers#
Problem C. Bribe the Prisoners
Approche par programmation dynamique#
Une observation fondamentale à faire pour ce problème est la suivante. Imaginons qu’un oracle nous donne le nombre de pièces d’or minimum à dépenser pour toutes les prisons contenant strictement moins de cellules et strictement moins de prisonniers. On peut alors r´esoudre notre problème par :
On va donc utiliser cette observation pour calculer la quantité cherchée récursivement. D’autre part, afin d’éviter de refaire les calculs plusieurs fois, on va mémoriser les réponses.
[4]:
from IPython.core.display import Image
Image("priso.png", width=450)
[4]:
Découpage intelligent d’une base de données#
Voir GroupKFold, découpage stratifié d’une base de données ou stratified sampling.
[ ]: