Kino

Pentru ca suma distanţelor între oricare două şiruri să fie maximă, trebuie să maximizăm distanţele poziţie cu poziţie, deoarece numerele care nu se află pe aceeaşi poziţie nu se afectează reciproc. Astfel, la fiecare pas numărăm câte poziţii libere sunt şi incercăm să le completăm cu numere cât mai puţin utilizate până atunci la poziţia respectivă. Observăm că este suficient să folosim maxim N numere distincte. O soluţie brute force de complexitate O(N²*L) care alege numărul cu frecvenţa minimă la fiecare pas ar fi obţinut 30 de puncte. Pentru a ajunge la soluţia optimă, sortăm şirul frecvenţelor şi obţinem astfel o "scară". Scara se completează treptat pe nivele, la fiecare pas existând două alternative: continuăm să alegem elementul următor de pe nivel sau alegem primul element, pe cel frecvenţa minimă. Complexitatea acestui pas este O(N) şi, deci, complexitatea totală este O(NlogN*L) (din cauza sortării).