h2(#marbles). 'Marbles':problema/marbles

 
Datorita modului in care sunt mutate bilele, ordinea relativa a acestora nu se va schimba pe parcursul efectuarii operatiilor, deci ordinea culorilor va ramane neschimbata. Initial sortam bilele din fisierul de intrare dupa coordonata lor, si calculam un tablou de sume partiale {$S$}, unde {$S{~c,i~}$} va reprezenta numarul de aparitii ale culorii $c$ in primele $i$ bile din lista sortata. La fiecare pas vom avea un vector de coordonate $x$ = ({$x{~1~}$}, {$x{~2~}$},... , {$x{~N~}$}), care, conform observatiei de mai sus, va ramane intotdeauna sortat crescator. Astfel, putem realiza operatia de mutare a unei bile in complexitatea {$O(log{~2~}N)$}, cautand binar pozitia in vectorul $x$ pe care apare bila care trebuie mutata, si modificand aceasta valoare. Daca dorim sa aflam care este numarul maxim de bile de aceeasi culoare din intervalul [{$i, j$}] este suficient sa cautam binar valorile {$a$} si {$b$}, unde $a$ este cel mai mic numar natural astfel incat {$i ≤ x{~a~}$}, iar $b$ este cel mai mare numar natural astfel incat {$x{~b~} ≤ j$}. Astfel, toate bilele intre pozitiile $a$ si $b$ inclusiv vor avea coordonata in intervalul [{$i, j$}]. Iteram fiecare culoare $C$ de la $1$ la $64$ si afisam maximul valorilor de forma {$S{~C,b~}-S{~C,a-1~}$}, care reprezinta chiar numarul de aparitii ale culorii $C$ intre pozitiile $a$ si {$b$}.
Complexitatea algoritmului de mai sus va fi {$O(Nlog{~2~}N + N*C + Mlog{~2~}N + M*C)$}. Aceasta solutie obtine punctajul maxim.