Solutii Algoritmiada 2010, Runda 3

• Lista de probleme
• Joben
• Semafoare
• Drum3
• Intersect
• Karb
• Cabine
• Piramid
• Arbore3

Joben

O primă observaţie necesară pentru a rezolva această problemă este că niciodată nu este nevoie să facem mai mult de o permutare şi o transformare pentru a obţine şirul dorit, în cazul în care există soluţie. De asemenea, ordinea în care aplicăm operaţiile nu are nicio relevanţă. Dacă am aplica doar o operaţie de permutare, condiţia necesară şi suficientă pentru existenţa unei soluţii este ca frecvenţa fiecărei litere din primul şir să coincidă cu frecvenţa ei din al doilea şir. Aplicând şi o operaţie de transformare, pentru fiecare frecvenţă de literă din primul şir trebuie indentificată o frecvenţă de literă din al doilea şir egală cu ea astfel încât oricare două litere din primul şir să aibă corespondenţi diferiţi. Cea mai simplă metodă de a face această verificare este să sortăm cei doi vectori de frecvenţă şi apoi să-i comparăm element cu element.

Semafoare

Pentru a rezolva problema, ne vom propune să calculăm D[i][j][k] = timpul minim necesar pentru a ajunge la semaforul din intersecţia (i, j) venind din direcţia k, unde k ia valori în mulţimea {0, 1, 2, 3} ce reprezintă codificări pentru cele 4 direcţii posibile: nord, est, sud si vest. Dacă în problemă nu ar interveni semafoarele, matricea D ar putea fi calculată cu uşurinţă folosind o parcurgere in lăţime sau, mai popular, un Lee. Totuşi, se observă că o maşină nu poate aştepta mai mult de 3 minute la un semafor, deci costul pentru a ajunge în oricare din celulele adiacente poate fi cel mult 4. De aceea, vom folosi 5 cozi în parcurgerea noastră: una pentru costul curent, una pentru costul curent + 1, ... şi una pentru costul curent + 4. Observaţia făcută mai devreme ne asigură că la pasul curent vom avea triplete (i, j, k) al căror cost să depăşească costul curent+4, în afară de cele al căror cost este infinit (nu ştim nimc de distanţa minimă până la ele). Vom parcurge coada corespunzătoare costului curent şi vom proceda exact ca în cazul unei parcurgeri în lăţime. Când terminăm de parcurs coada curentă, vom muta coada de cost curent + 1 în locul celei curente, cea de cost curent + 2 în locul celei de cost curent + 1, ..., iar ultima coadă va fi vidă. Este necesar ca pentru a calcula costurile de deplasare în celulele adiacente să ştim să determinăm timpul minim în care putem intra într-o intersecţie oarecare dacă ştim că am ajuns la semaforul respectiv la momentul de timp t, venind din direcţia d1, iar pentru în această intersecţie în minutul 0 intră maşinile din direcţia d2. Timpul minim căutat se poate obţine în complexitate O(1) cu ajutorul următoarei formule: (d1 - d2 - (t%4) + 8) % 4 sau în varianta optimizată folosind operaţii pe biţi: (d1 - d2 - (t&3) + 8) & 3. Algoritmul prezentat procesează fiecare triplet (i, j, k) de un număr constant de ori, ceea ce conduce la o complexitate totală O(N*M). Acest algoritm mai poate fi aplicat în mai multe probleme precum Pădure şi Car.

Drum3

O prima solutie pentru aceasta problema ar fi o dinamica in N³, din[i][j][k] = numarul total de drumuri pentru a ajunge in pozitia i, j din matrice cu k schimbari de directie. Aceasta solutie este totusi ineficienta. Pentru a gasi o solutie in N², vom face cateva observatii:

• Numarul total de posibilitati este egal cu dublul numarului de posibilitati daca am face prima mutare la dreapta (drumurile sunt simetrice fata de prima diagonala). Asadar de acum inainte vom considera ca prima mutare va fi mereu la dreapta, iar la sfarsit inmultim cu doi rezultatul.
• Orice drum de la 1, 1 la N, N in matrice este compus dintr-o serie de segmente verticale (ce unesc doua casute adiacente) ce au suma lungimilor egala cu N-1 si o serie de segmente orizontale cu aceeasi proprietate.
• Numarul acestor segmente verticale si orizontale este unic determinat de K. Fie No si Nv numarul de segmente orizontale si respectiv verticale, atunci No = (K + 2) / 2 si Nv = (K + 1) / 2.
• Numarul posibilitatilor de a parcurge matricea cu exact K schimbari de directie este egal cu numarul de partitionari a numarului N-1 in No numere inmultit cu numarul de partitionari a numarului N-1 in Nv numere, unde definim numarul de partitionari al numarul N in K sume ca fiind numarul total de moduri in care putem obtine suma N cu K numere naturale unde ordinea conteaza (exemplu: partitionarile lui 4 in 3 numere sunt: 1 + 1 + 2, 1 + 2 + 1 si 2 + 1 + 1).

Tot ce ramane de facut este sa vedem cum aflam numarul de partitionari al unui numar N in K numere. Daca ne gandim la numarul N ca la un segment de lungime N observam ca o partitionare a lui, in K numere poate fi reprezentata prin taierea segmentului in exact K segmente mai mici. Acest lucru se obtine prin K-1 taieturi in N-1 locuri posibile (exemplu: 2 + 3 + 1 poate fi reprezentat ca --|---|-). Asadar numarul de partitionari al unui numar N in K numere este egal cu combinari de N-1 luate cate K-1. De aici se deduce usor ca rezultatul final al problemei este C[N-2][No-1] * C[N-2][Nv-1] * 2 (unde C[x][y] este egal cu combinari de x luate cate y).

Intersect

Cea mai importanta observatie ce ajuta la rezolvarea acestei probleme este ca avand i drepte deja desenate si adaugand o dreapta noua neparalela cu nici una din cele i dinainte se vor forma i intersectii noi si i + 1 zone noi in care este impartita foaia. In continuare daca avem i drepte deja desenate si adaugam k drepte noi paralele intre ele dar neparalele cu nici una din cele i drepte deja desenate se vor forma i * k intersectii noi, si (i + 1) * k zone noi in care este impartita foaia. Asadar problema se poate rezolva prin progamare dinamica. Fie din [ i ] [ j ] numarul maxim de zone in care poate fi impartita foaia astfel incat sa fi desenat i drepte ce se intersecteaza in j puncte, sau 0 in caz ca i drepte nu pot forma j intersectii. Valoarea initiala a aceste dinamici va fi din [ 0 ][ 0 ] = 1 . Vom porni de la dimensiunile mai mici ale dinamicii ( adica vom parcurge starile dinamicii in ordine crescatoare dupa i si apoi j ) . Daca suntem in starea din [ i ] [ j ] < > 0 , vom incerca sa desenam k noi drepte paralele intre ele dar neparalele cu nici una din cele i deja desenate si vom actualiza din [ i + k ] [ j + ( i * k ) ] = maxim ( din[ i + k ][ j + ( i * k ) ], din[ i ] [ j ] + (i + 1) * k ) .
O alta observatie utila ar fi ca numarul maxim de zone in care poate fi impartit planul de i drepte ce formeaza j intersectii este unic determinat de i si j si este egal cu i + j + 1 . Ajutandu-ne de aceasta observatie trebuie doar sa stim daca i drepte pot forma j intersectii si putem schimba dinamica in din[i][j] este 1 sau 0 daca i drepte se pot intersecta in j puncte, si astfel putem reduce memoria folosind stari pe biti. Acest lucru nu era necesar pentru a obtine punctaj maxim.
Solutia aceasta are complexitatea N^3 .

Soluţie alternativă
Având în vedere că numărul maxim de zone în care poate fi împărţit planul de i drepte ce formează j intersecţii este unic determinat, pentru a afla o anumită configuraţie (i, j) este necesar să calculăm maxim i configuraţii. Astfel, vom calcula doar configuraţiile necesare, folosind memoizarea. Această soluţie are complexitatea O(T*N)

Karb

Această problemă admite o mulţime de soluţii cu diferite complexităţi. Noi vom enumera doar trei.

O soluţie în complexitate O(M² log*(N)) ar obţine în jur de 40 de puncte. Considerăm mulţimea tuturor arborilor de acoperire. Între arborele de acoperire de cost minim şi arborele de acoperire de cost maxim există o serie de arbori de acoperire intermediari, cu proprietatea că există o ordine astfel încât oricare doi arbori consecutivi diferă doar prin două muchii iar costul lor prin exact 1. Astfel, dacă vom elimina o muchie şi vom adăuga o alta costul arborelui de acoperire minim / maxim va creşte / scădea cu 0 sau 1. Algoritmul constă în considerarea succesivă a fiecărei muchii; dacă elimininând-o vom obţine că avem K cuprins între costul arborelui de acoperire minim, respectiv maxim, atunci o vom păstra, altfel, o vom elimina. Soluţia va fi formată din muchiile care au rămas, în număr de N - 1.

O soluţie alternativă în complexitate O(M*N), ce obţine în jur de 60 de puncte, dar care foloseşte aceeaşi idee ca soluţia anterioară, porneşte de la un arbore de acoperire minim căruia i se adaugă muchii de cost 1 astfel încât pe ciclul ce îl formează să existe o muchie de cost 0. Muchia din urmă va fi eliminată şi se va rămâne cu un arbore de acoperire cu un cost mai mare cu 1. Acest pas se repetă până costul arborelui de acoperire devine K.

Soluţia optimă, în complexitate O(M log*(N)), urmează paşii de mai jos:

1. cu muchiile de cost 0 descompune graful în componente conexe;
2. caută muchiile de cost 1 care unesc aceste componente, astfel încât să nu se formeze un ciclu între acestea;
3. consideră doar muchiile de cost 1 de la pasul anterior la care adaugă altele de acelaşi cost până ce vor fi în număr de K;
4. adaugă muchii de cost 0 până ce se formează un arbore de acoperire;

Ultimul pas are sens datorită pasului al doilea.

Cabine

Vom incerca sa gasim ordinea in care vor fi ocupate cabinele. Ne vom folosi de urmatoarea strategie greedy:

• Prima si ultima cabina vor fi intotdeauna alese la inceput, deoarece ele nu se vor afla niciodata intre alte doua cabine ocupate.
• In cazul in care nu exista doua cabine libere adiacente, fiecare persoana care soseste va alege cabina cu indicele cel mai mic.
• Daca exista cel putin doua cabine adiacente, prima persoana care soseste va alege cabina cu indicele cel mai mare pentru care cabina vecina din dreapta este la randul ei libera. Demonstratie: In continuare vom considera ca aceasta cabina are indicele P. Fie X numarul de cabine libere din stanga lui P. Cabina P+1 va fi ocupata dupa cele X aflate la stanga, deci cabina P va avea cel putin un vecin liber timp de X+1 secunde. Acelasi timp se obtine si pentru cabina P+1, dar aceasta are indicele mai mare. Daca ar fi fost aleasa o cabina cu indice mai mic decat P, s-ar fi obtinut un timp mai mic decat X+1.

Cunoscand aceasta strategie, putem sa simulam modul in care sunt alese cabinele folosind doua parcurgeri ale sirului de intrare.

Piramid

Vom considera doar cazurile in care varful piramidei este in sus. Celelalte cazuri se pot numara identic rotind matricea initiala cu 90 de grade de 3 ori. Inainte de a incerca sa rezolvam problema o sa trebuiasca sa definim si sa precalculam cateva lucruri:

1. Fie V[i][j] lungimea celui mai mare /\ cu varful in i, j. (vezi Fig. 1: V = 2)
2. Fie L[i][j] lungimea celui mai mare interval de 1-uri consecutive de pe linia i, ce are pozitia i, j ca mijloc (vezi Fig.2: pentru 1-ul inclinat segmentul ingrosat este cel mai mare interval de 1-uri consecutive de pe linia lui, al carui centru este, si L = 2)
3. Definim centrul unei piramide ca fiind punctul din mijlocul bazei acelei piramide (vezi Fig. 3)
4. Definim inaltimea unei piramide ca fiind distanta intre centrul piramidei si varful acesteia (vezi Fig. 4: inaltimea este egala cu 3 si este marcata de literele H).

Fig. 1	Fig. 2	Fig. 3	Fig. 4	Fig. 5
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0	0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0	0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 1 1 1 C 1 1 1 0 0 0 0 0 0 0	0 0 0 0 0 0 0 0 0 0 H 0 0 0 0 0 1 H 1 0 0 0 1 0 H 0 1 0 1 1 1 C 1 1 1 0 0 0 0 0 0 0	0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 1 0 1 1 1 1 C 1 1 1 1 0 0 0 0 0 0 0 0 0

Vom parcurge fiecare coloana din matrice in parte. Pentru o anumita coloana j vom parcurge liniile in ordine crescatoare si pentru fiecare linie i vom incerca sa numaram cate piramide cu centrul in pozitia i, j exista (vezi Fig. 5). Folosindu-ne de informatia din L[i][j] putem sti inaltimea maxima pe care o poate avea o piramida cu centrul in i, j. Asadar observam ca de fapt ne intereseaza sa numaram cate pozitii k, j respecta conditiile j - L[i][j] <= k < j si k + V[i][k] >= j (adica, pentru cate pozitii k, j, /\-ul lor intersecteaza segmentul bazei piramidei determinat de centrul acesteia). Astfel, putem transforma problema intr-una de sume pe un anumit interval. Daca consideram ca un anume "varf" k, j ( /\ ) "este valabil" intre pozitiile k si k + V[k][j], atunci pentru un centru i, j ne intereseaza cate "varfuri valabile" avem intre pozitiile j - L[i][j] si j - 1. Deci se creeaza o serie de evenimente de genul: marcheaza pozitia i, j ca fiind valabila, marcheaza pozitia i, j ca fiind nevalabila si afla numarul pozitiilor valabile intre pozitiile j - L[i][j] si j - 1 ceea ce este echivalent cu urmatorul set de evenimente: aduna 1 in pozitia j, scade 1 din pozitia j si afla suma intre pozitiile k si j care poate fi rezolvat foarte simplu cu un arbore indexat binar sau cu un arbore de intervale. Asadar daca pentru o anumita coloana construim toate aceste evenimente, le sortam, si apoi le parcurgem in ordinea sortarii, putem rezolva problema in N log N cu o complexitate totala (pentru toate cele N coloane) de N² log N.

Arbore3

Vom calcula pentru nodurile arborelui un vector Sum, unde Sum[nod] va fi egal cu valoarea sumei tuturor nodurilor de pe drumul de la nod la radacina. Suma pentru un drum in arbore de la un nod A la un stramos de-al sau B va fi egala cu Sum[A] - Sum[Tata[B]]. Efectuand o parcurgere in adancime a arborelui, ne intereseaza pentru fiecare nod cati stramosi are atfel incat Sum[Tata[stramos]] = Sum[nod] - S. Pentru a raspunde eficient la aceaste interogari, vom mentine o tabela hash pentru elemente ale vectorului Sum, in care vom insera valori cand vom inainta in parcuregerea subarborelui si vom scoate valori cand ne intoarcem din subarbore. Interogarile se reduc la a determina cate elemente cu o anumita valoare exista in tabela hash.