Bignumber
Autor: stud. Cosmin Tututnaru, Universitatea „Babeş-Bolyai”, Cluj-Napoca
Descrierea soluţiei (Cosmin Tutunaru)
Soluţie – 50 p
Încercăm să aducem pe prima poziţie cea mai mare cifră care nu se află la o distanţă mai mare decât X (număul de mutări permise). Evident că, dacă cifra apare pe mai multe poziţii, o vom alege pe cea mai din stânga. Aducem această cifră pas cu pas pe prima pozitie si actualizăm X-ul. Eliminăm prima poziţie din şir şi repetăm procesul.
Complexitate: O(X)
Soluţie – 100 pct
Fie getCost(pos) o funcţie care returnează costul minim de a duce cele mai mari pos cifre pe primele pos poziţii. Aceasta funcţie poate fi implementată în O(N) cu constanta 10, deoarece la primul pas aducem toate cifrele de 9 pe prima poziţie, la pas-ul următor toate cifrele de 8, … şi tot aşa, până când sunt aduse cele mai mari pos cifre.
Fie v şirul maxim care se poate obţine (şirul iniţial sortat descrescător).
Având funcţia de mai sus implementată, putem căuta binar primele elemente din v care se vor afla şi in rezultat (fără a fi necesare mai mult de X swap-uri). După ce se află numărul de elemente care coincid, numărul de mutari care ne mai pot rămâne este cel mult N şi putem aplica în continuare algoritmul de la soluţia de 50 de puncte pentru restul cifrelor rămase.
Complexitate: O(N*LogN)
