15 concurenti au reusit sa rezolve problema in timpul rundei. Totusi, doar 3 dintre ei au reusit s-o rezolve cu un punctaj mai mare de 50 (punctajul minim acordat pe o solutie care trece toate testele). Problema era una de idee, care necesita cunostinte elementare de combinatorica. In general, scorurile sunt asa mici din cauza trimiterii mai multor submisii. Unii concurenti au implementat solutii gresite, care mergeau numai pe cazuri particulare, fara a demonstra ca functioneaza pe caz general. Testele feedback au aratat ca submisia nu e buna si concurentul a trebuit s-o ia de la capat. Alta cauza a resubmisiilor a fost testul 7, fiind un caz particular. De exemplu, acest test l-a facut pe ==user(user="darren" type="tiny")== sa-si retrimita 'sursa':job_detail/802521 de-abia la putin timp inainte de finalul concursului. Cu toata astea, ==user(user="Magnvs" type="tiny")== a reusit sa rezolve problema in 32 de minute de la inceperea concursului.

Pentru a rezolva problema initiala, propun sa rezolvam o versiune simplificata a ei. Sa presupunem ca orice interschimbare are costul 1. Care este costul minim ca sa sortam permutarea?

Pentru a rezolva problema initiala, propun sa rezolvam o versiune simplificata a ei. Sa presupunem ca orice interschimbare are costul 1. Care este costul minim ca sa sortam permutarea? Vom descompune permutarea in cicli. Oricare 2 cicli sunt disjuncti (un element apartine unui singur ciclu), deci costul sortarii permutarii este egal cu suma costurilor sortarii fiecarui ciclu.
 
Fie x1, x2, ..., xn elementele ciclului curent (adica perm(x1) = x2, perm(x2) = x3, ..., perm(xn - 1) = xn, perm(xn) = x1). Costul sortarii acestui ciclu este n - 1. De ce? Mai departe voi spune ca perm(x) = elementul care se afla pe pozitia x. Stiu ca pe pozitia x1 ar trebui sa fie elementul x1. Dar x1 se afla pe pozitia xn, deci schimb elementul de pe pozitia x1 cu elementul de pe pozitia xn (voi nota asta swap(x1, xn)). Pe pozitia xn se afla acum ce se afla inainte pe pozitia x1, adica x2. Pe pozitia x2 trebuie sa se afle elementul x2, deci fac swap(x2, xn). Acum pe pozitia xn se va afla elementul x3. Dupa ce fac operatiile swap(x1, xn), swap(x2, xn), swap(x3, xn), ..., swap(xn - 2, xn), swap(xn - 1, xn) permutarea va fi complet sortata. Practic, dupa i swap-uri, primele i elemente ale permutarii vor fi sortate. Dupa n - 1 swapuri, primele n - 1 elemente ale permutarii vor fi sortate, iar pe pozitia xn se va afla exact elementul xn, deci toata permutarea va fi sortata. In concluzie, pentru a sorta un ciclu de lungime n am nevoie de n - 1 operatii, iar pentru a sorta o permutare, costul va fi lungimea totala a ciclurilor - numarul de cicluri.
 
 

h2. 'Petrecere2':problema/petrecere2