Revizia anterioară Revizia următoare
Soluţii Urmasii lui Moisil 2015
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)
Rox
Autor: stud. Liana Ştefania Ţucăr
Descrierea soluţiei (stud. Marta Diana Filimon)
Solutie – 100 p
Pentru a reţine tipul florilor care sunt plantate în celula de pe linia L şi coloana C vom utiliza un tip de date care este reprezentat pe 32 de biţi şi vom utiliza cei mai nesemnificativi (aceştia fiind ultimii) 26 de biţi, astfel: cel de al k-lea bit este 1 dacă floarea care are numele celei de a (k+1)-a literă a alfabetului englez apare pe linia L şi coloana C, unde 0 <= k <= 25.
Pentru o parcelă de coordonate L1, C1, L2, C2 pe care se plantează o floare de tipul T se procedează astfel: vom aplica operaţia xor cu valoarea 1 deplasată la stânga cu k biţi, unde k reprezintă numărul de ordine al literei în alfabet mărit cu 1, în celulele de coordonate (L1, C1), (L2, C2+1), (L2+1, C1), (L2+1, C2+1).
Vom face suma xor pentru elementele aflate în submatricea care are colţurile în celulele (1, 1) şi (L, C) oricare ar fi L şi C cu 1 <= L <= N; 1 <= C <= M. Apoi, pentru a răspunde unei întrebări din cele Q întrebări date, vom determina numărul de biţi de 1 al reprezentării binare a valorii de pe linia şi coloana specificată.
Observăm că nu poate fi reţinută matricea sumelor xor, însă acest lucru nu este necesar deoarece pentru a determina valoarea oricărei celule de pe linia i avem nevoie cel mult de linia i-1. Într-o astfel de abordare, soluţia problemei se modifică asftel:
- Se reţin de la început atât plantările cât şi întrebările.
- Pentru fiecare plantare vom reţine separat prima linie şi ultima linie pe care apare, deoarece în rest aceasta nu modifică suma xor a valorilor din celule; se observă că astfel se dublează numărul de plantări.
- Se sortează crescător dupa linie plantările, iar întrebările se sortează crescător după linie şi, în caz de egalitate, după coloană.
- Pe măsură ce determinăm răspunsurile întrebărilor, le reţinem; la final le sortăm după ordinea apariţiei în fişierul de intrare.
Observăm că pentru a calcula sumele xor de pe o linie nu este necesar să reţinem sumele xor de pe linia precedentă, noile plantări aplicându-se peste cele anterioare. Pentru a răspunde la întrebările de pe o linie i, facem suma xor a valorilor de pe linia respectivă doar în cazul în care avem o întrebare.
