bingo

Algoritmul, pas cu pas

O interschimbare vecină mută un caracter cu o poziție. Vrem să apară bingo consecutiv plătind cât mai puțin. Două litere identice cu „bingo" sunt complet egale pentru noi, deci în fond avem o singură decizie: pe care ocurență a lui $b$, a lui $i$, a lui $n$, a lui $g$ și a lui $o$ o folosim. Restul caracterelor nu ne interesează — îi „trecem prin" ele cât adunăm cele cinci litere.

Odată fixate cele cinci litere, costul de a le lipi în cuvântul bingo se desparte în două lucruri independente, fiecare numărat în interschimbări vecine:

• Reordonarea lor în ordinea corectă $b, i, n, g, o$ — exact câte inversiuni au (perechi de litere alese aflate în ordine greșită una față de alta).
• Strângerea lor ca să devină consecutive — pentru elemente pe poziții sortate $p_1 < p_2 < \dots < p_5$, numărul minim de pași e dat de „trucul medianei": le aducem toate lângă cel din mijloc, iar costul se reduce la $p_4 + p_5 - p_1 - p_2 - 6$.