Solutii Algoritmiada 2018, Runda PreOJI

Zoro

Solutia acestei probleme se bazeaza pe construirea unei matrice D unde D[i][j] reprezinta care este cel mai lung drum care porneste din celula (1,1) si ajunge in celulal (i,j).

Initial, D[ 1 ][ 1 ] = 1. Distanta pana la celula (1,1) este 1, ca urmare putem initializa la inceput aceasta valoare.
Dupa ce terminam de calculat intreaga matrice, raspunsul se va afla in D[N][M].

Pentru a putea construi aceasta matrice, este nevoie sa avem in vedere urmatoarele 2 lucruri:

1) In ce ordine calculam elementele matricei?
2) Cum le calculam? (care este relatia de recurenta)

In cazul acestei probleme, se observa faptul ca elementele matricei trebuie parcurse in ordinea valorii lor de la mare la mic. Mai exact, calculam raspunsul pentru o celula (x, y) abia dupa ce am calculat raspunsul pentru toate celulele cu valori mai mari (deoarece (x, y) poate sa vina din oricare celula mai mare de pe aceeasi linie sau coloana).

Ramane sa aflam relatia de recurenta. O solutie cu o recurenta de complexitate O(N) este ca pentru celula (x, y) sa parcurgem toate elementele de pe aceeasi linie sau coloana. Daca aceste elemente au fost deja calculate (valoarea lor este mai mare), selectam maximul dintre ele (cel mai lung drum). Cel mai lung drum care se termina in (x, y) va fi desigur cel mai lung drum care se termina intr-un vecin (de pe aceeasi linie sau coloana) + 1. Daca elementele nu au fost calculate (valoarea este mai mica), le ignoram. Aceasta solutie are complexitate O(N3) si obtine 50 de puncte.

Observatia pentru 100 de puncte se bazeaza pe faptul ca nu este nevoie sa parcurgem toate elementele de pe o linie sau coloana. Din moment ce ne dorim sa aflam care este maximul pe toate elementele, putem folosi o structura de tipul: line[x] = care este cel mai bun raspuns pentru toate elementele de pe linia x (analog colum[y]), strucura care poate fi folosita si actualizata in O(1). Astfel, raspunsul pentru D[x][y] va fi max(line[x], colum[y]) + 1. Desigur, in paralel vom actualiza cele 2 structuri: line[x] = max(line[x], D[x][y]), respectiv colum[y] = max(colum[y], D[x][y]). Aceasta solutie are complexitate O(N2).

Smooth2

Rezumat:

  • Un şir de litere este smooth dacă şi numai dacă exista un numar K pentru care sirul este o concatenare de grupuri de litere distincte de mărime K (cu excepţia ultimului grup care poate fi mai mic).
  • Cunoscând mulţimea de litere care se află la final în răspunsul optim, trebuie doar să ne asigurăm că niciun grup nu conţine duplicate, numărul de modificări fiind dat de numărul de litere duplicat din fiecare grup.
  • Pentru a afla mulţimea optimă de litere vom itera peste mărimea ei (sunt 26 de mărimi posibile). Având mărimea fixată, putem calcula pentru fiecare literă câte modificări ne-ar impune dacă am păstra-o în şir. Aceste valori sunt independente, deci putem selecta acele litere care impun cele mai puţine modificări.
  • În mod posibil contra-intuitiv, există teste pentru care soluţia optimă are mai multe litere distincte decât şirul iniţial.

Explicaţie:

Il vom fixa pe K, dandu-i valori intre 1 si 26. Vrem sa alegem cele K litere din care sa fie format sirul de caractere. Stim ca secevnta de la 1 la K va fi formata din caractere distincte, secventa de la K + 1 la 2K e formata tot din caractere distincte, si tot asa. Plecam de la ideea ca vom rescrie toate caracterele sirului si calculam Help[ch] = ajutorul pe care l-as primi daca printre cele K litere alese se afla si caracterul ch. Ajutorul se exprima in numarul de pozitii la care nu mai e nevoie sa schimb caracterul. In mod natural, Help[ch] proneste de la valoarea 0 si creste cu 1 pentru fiecare secventa din cele mentionate (inclusiv ultima, desi poate incompleta) in care caracterul ch apare macar la o pozitie (daca apare de 2 ori nu ne avantajeaza cu mai mult decat daca aparea o singura data). Acum alegerea celor K litere se va face la fel de natural, sortandu-le in ordine descrescatoare dupa Help[ch] si luandu-le pe primele K.

Calcularea lui Help se poate realiza in O(N), pentru fiecare valoare a lui K, prin urmare solutia are complexitatea O(N * Sigma) (unde Sigma inseamna marimea alfabetului si este egal cu 26)

Delfin

Observatia cea mai relevanta este ca nu nu avem de ce sa ne urcam de 2 ori pe testoasa. Fiind o singura testoasa, daca vrem sa coboram pe pamant si sa ne intoarcem, mai tarziu, inapoi pe testoasa, oricum ar trebui sa o asteptam sa ajunga la pozitia noii intalniri, deci nu ne ajuta cu nimic.

O utilizare directa a observatiei ne conduce la urmatoarea abordare: Sa fixam pozitia in care ne urcam pe testoasa! Ce ne trebuie pentru a calcula timpul de a ajunge la comoara, stiind celula in care ma urc pe testoasa? Trebuie sa stim: timpul in care ajung eu la celula respectiva (aceasta fiind pe apa, ne intereseaza de fapt timpii in care ajung pe pozitiile de uscat din jurul ei, accesibile fara utilizarea testoasei), timpul in care ajunge testoasa la celula respectiva, si timpul pe care l-as petrece pana sa ajung la comoara daca plec de la celula data. Daca cele 3 valori exista, vom lua maximul primelor doua valori si adaugand-o pe a treia, vom afla costul celulei. Luand minimul tututor costurilor si considerand si cazul in care nu ma intalnesc deloc cu testoasa, vom gasi solutia optima.

Cele 3 valori pe care trebuie sa le aflu pentru fiecare celula pot fi calculate astfel:

  • timpul in care ajung eu la o celula - BFS (Algoritmul lui Lee / parcurgerea cu coada a matricei) din S mergand doar pe uscat
  • timpul in care ajunge delfinul la o celula - BFS din D mergand doar pe apa
  • timpul in care ajung de la o celula la comoara stiind ca initial sunt pe testoasa = timpul in care ajung de la comoara la celula stiind ca, odata ce ajung pe apa, merg doar pe apa - BFS din F mergand de pe uscat pe orice iar de pe apa doar pe apa.

Complexitatea algoritmului este O(N2)

O alta abordare

O alta rezolvare ar fi folosing varianta algoritmului Disktra pe costuri mici, in aceeasi complexitate timp de O(n2).
Acesta consta in pastrarea a n2 liste inlantuite, in lista cu indicele i aflandu-se toate celulele de matrice accesibile in exact i momente de timp.

Tinand cont de observatia "cea mare" avem de numarat fiecare celula de matrice de 2 ori, in cazul in care am ajuns pe acea celula si pana acum am mers doar pe uscat si cazul in care am ajuns pe acea celula si pe drum am trecut si prin celule de apa folosind testoasa.

O sa marcam o celula ca un triplet (X, Y, a) unde X ia valori intre 1 si n; Y intre 1 si m si a este un bool 0/1 care semnifica daca pana acum am mers doar pe pamant (a = 0) sau daca am mers si pe apa (a = 1).

Initial, punem doar celula de start (Sx, Sy, 0) in lista corespondenta costului 0;

Listele inlantuite se vor parcurge crescator, de la 0 la 2n2.
Cand vom procesa un element dintr-o lista cu indicele L (cea care contine celulele la distanta L) : (X, Y, a) , vom verifica initial ca celula respectiva (X, Y, a) sa nu mai fi fost vizitata anterior
(deci sa aiba costul minim de a ajunge la ea). Luam, pe rand cei 4 vecini ai celulei noastre. Fie unul dintre ei (Vx, Vy).
a) Daca (Vx, Vy) si (X, Y) sunt de acelasi tip (pamant sau apa) inseamna ca putem adauga (Vx,Vy,a) in lista L + 1
b) Daca (X, Y) este apa si (Vx, Vy) este pamant, putem adauga (Vx, Vy, a) in lista L + 1. Pe acest caz sigur a va fi egal cu 1
c) Daca (X, Y) este pamant si (Vx, Vy) este apa,

  • pt a = 1 nu facem nimic, deoarece aplicam observatia
  • pt a = 0 vom adauga (Vx, Vy, 1) in lista max(L+1,timpul_minin_in_care_ajuge_delfinul[Vx][Vy]);

Indicele primei liste in care gasim celula in care se afla destinatia (indiferent de a) ne da rezultatul la cerinta.