Solutii Algoritmiada 2010, Runda 4

Binar

Algoritmii obişnuiţi de sortare au complexitatea O(N log N), iar pentru a compara două şiruri vom facem O(N) comparaţii. Astfel, putem obţine algoritmi de complexitate O(N ^ 2 log N), însă aceştia nu vor obţine 100 de puncte. Pentru punctaj maxim, trebuie să adaptăm algoritmul Radix sort. Iniţial ne vom uita la valorile de pe prima linie a matricei şi vom împărţi coloanele în două mulţimi - cele care au pe prima linie 0 şi cele care au pe prima linie 1. Apoi, coloanele din fiecare mulţime le vom împărţi din nou în alte două mulţimi, în funcţie de valorile de pe a doua linie. Un algoritm recursiv pe această idee - care la fiecare pas împarte coloanele dintr-o mulţime în două submulţimi în funcţie de valorile de pe o anumită linie - are complexitatea O(N * M) şi obţine 100 de puncte.

Copii

Problema este o aplicaţie oarecum clasică a algoritmului de generare a tuturor partiţionărilor unei mulţimi. Algoritmul este de tip backtracking şi este bazat pe următoarea idee: la un pas k (1 ≤ k ≤ N), putem adăuga cea de a k-a persoană la oricare din grupurile existente sau putem crea un grup nou format doar din persoana k. Cum grupurile vor conţine persoanele în ordine crescătoare a indicilor, avem siguranţa că nu vom genera o partiţionare de mai multe ori. Pentru a vă clarifica algoritmul puteţi consulta o implementare aici. Având o astfel de partiţionare generată, verificările necesare se pot face în mod direct în complexitate O(N2). Menţionăm că verificarea se poate face şi în complexitate O(N) dacă pe parcurs se construiesc nişte informaţii suplimentare pe biţi, dar acest lucru nu este necesar pentru a obţine 100 de puncte.

Cuburi5

O soluţie evidentă în O(N2 * K) (sau O(N2 * K2)) este asemănătoare găsirii subşirului crescător maximal. Putem îmbunătăţi această soluţie folosindu-ne de faptul că numerele înscrise pe cuburi sunt din intervalul [1..105]. Vom parcurge cuburile începând cu ultimul (pentru a putea găsi prima soluţie lexicografică uşor) şi ne vom menţine un vector best de mărime 105 având semnificaţia: best[i] = lungimea maximă a unui subşir care începe cu un cub pe care este înscris numărul i. Pentru a găsi lungimea maximă a unui subşir care începe cu un cub dat, ne vom uita la toate valorile best[i] pentru care valoarea i este înscrisă pe cub. După ce calculăm această valoare pentru un cub, va trebui sa reactualizăm vectorul best. Aceasă soluţie are complexitatea O(N * K) şi obţine 100 de puncte.

Retea

Vom construi solutia cu programare dinamica astfel: Fie C[i][j] costul minim pentru a ajunge in nodul i cu j acceleratoare folosite. Astfel recurenta va fi urmatoarea C[i][j] = min( C[k][j - q] + Cm[i][k] / 2q ) unde k este un vecin al lui i (bineinteles luam toti vecinii posibili), q reprezinta cate acceleratoare folosim pe muchia dintre i si k iar Cm[i][k] reprezinta costul muchiei dintre i si k. Putem observa usor ca aceasta problema este o problema de drum minim intr-un graf in care un nod este reprezentat de perechea (i, j) reprezentand nodul si respectiv numarul de acceleratoare folosite in drumul de la 1 pana la i, iar muchiile grafului intial se transforma in muchii in graful nou luand in calcul "noua dimensiune" data de j, numarul de acceleratoare. Graful nou format nu trebuie retinut propriu zis in memorie, pentru ca muchiile lui sunt usor determinate la fiecare pas din muchiile grafului intial. Pentru a gasi drumul minim intre nodul initial si cel final folosim Dijkstra cu heapuri pentru complexitatea optima. Bellman-Ford nu intra in timp.

Solutia aceasta are complexitate O(M * K * K * log(N * K)). Chiar daca pare mare complexitatea, aceasta este supraestimata.

Matrice 3

Pentru a putea rezolva problema, trebuie să ştim întâi rezolva problema determinării laturii maxime a unui pătrat plin cu 0 dintr-o matrice binară. Problema este foarte cunoscută şi se rezolvă cu ajutorul programării dinamice. Vom nota C[i][j] = latura maximă a unui pătrat plin cu 0 cu colţul dreapta jos în (i, j). Pentru a calcula C[i][j], avem nevoie de două informaţii precalculate: A[i][j] = numărul de 0 consecutivi aflaţi pe linia i exact în stânga poziţiei (i, j) şi B[i][j] = numărul de 0 consecutivi aflaţi pe coloana j exact înaintea poziţiei (i, j). Recurenţa devine C[i][j] = min(C[i-1][j-1]+1, A[i][j], B[i][j]). Dacă pentru fiecare din cele Q întrebări, ar fi fost aplicată rezolvarea descrisă mai sus strict pe zona din matrice descrisă de întrebare, s-ar fi obţinut 30 de puncte.
Pentru a rafina ideea descrisă anterior, trebuie sa ne găsim un mod eficient de tratare a unui query. Se observă că este semnificativ mai uşor să răspundem la următoarea întrebare: În dreptunghiul determinat de celulele (x1, y1) (x2, y2), există un pătrat plin cu 0 de latură L? Răspunsul la această intrebare este echivalent cu un query de maxim în matricea C calculată anterior, în dreptunghiul (x1+L, y1+L) (x2, y2). Un astfel de pătrat există dacă şi numai dacă maximul respectiv este ≥ L. Această observaţie ne duce la ideea de a căuta binar rezultatul pentru fiecare dintre cele Q întrebări. Pentru a putea găsi maximul într-un dreptunghi în mod eficient (complexitate O(1)), putem folosi un RMQ 2D a cărui construcţie prealabilă necesită complexitate timp şi spaţiu O(N2log2N). Aşadar soluţia oficială are complexitate timp O(N2log2N + QlogN).
Menţionăm că folosirea unui RMQ 1D şi rezolvarea query-ului de maxim în complexitate O(N), ar fi adus 60 de puncte.

Pirati

Vom construi un graf în care fiecare nod va fi asociat unei zone conexe de elemente din matrice având aceeaşi valoare. O observaţie mai puţin evidentă este ca graful rezultat va fi întotdeauna un arbore. Lăsăm pe seama cititorilor demonstraţia acestei afirmaţii :P. Problema se reduce astfel la aflarea lungimii drumului între două noduri dintr-un graf. Acest lucru se poate face cu LCA în O(log N), însă pentru 100 de puncte nu era necesară implementarea optimă. Deşi arborele poate avea O(N ^ 2) noduri, adâncimea sa este de ordinul O(N). Astfel, putem găsi LCA-ul pentru două noduri cu o abordare brute force. Soluţia oficială are complexitatea O(N * M + Q * N).

Compact

Algoritmul optim de rezolvare are complexitate O(N). Pe baza vectorului citit, construim alti doi vectori leftMin si leftMax care au urmatoarea semnificatie:

  • leftMini = maxim(j < i | permj < permi), adica leftMini va retine cel mai mare indice din stanga lui i pentru care permj < permi
  • leftMaxi = maxim(j < i | permj > permi), adica leftMaxi va retine cel mai mare indice din stanga lui i pentru care permj > permi

Cei doi vectori pot fi calculati in timp liniar folosind o stiva. De exemplu, pentru calcularea primului vector, la fiecare pas stiva va avea elemente sortate crescator. Atunci cand inseram un nou element in stiva, vom elimina varful stivei cat timp acest varf este mai mare decat elementul curent, permi, pe care dorim sa il inseram. Astfel, leftMini va fi chiar varful stivei dupa ce am facut toate eliminarile. Cum fiecare element este scos din stiva maxim o data, operatia are complexitate amortizata O(1). Similar se calculeaza si leftMaxi.

Secventele compacte care se termina pe pozitia i incep pe pozitii de forma leftMini, leftMin[leftMin[i]], etc., unde numarul de compuneri se realizeaza pana cand ajungem pe o pozitie x < leftMaxi. Pentru fiecare i trebuie sa determinam eficient numarul de intoarceri. Putem crea un arbore unde nodul i are ca parinte nodul leftMin[i]. La fiecare pas cautam binar pe stiva DF (care este evident sortata crescator, deoarece leftMini < i) care este ultima pozitie pana la care ne putem intoarce. Diferenta de nivel dintre cele doua noduri va da numarul de secvente compacte care se termina pe pasul curent. Complexitatea acestei abordari este totusi O(N log N).

Pentru a obtine complexitate liniara, trebuie sa observam ca ultima valoare din sirul leftMin[i], leftMin[leftMin[i]]... pe care ne vom opri este chiar minimul pe secventa dintre pozitiile leftMaxi+1 si i. Pozitia acestui minim poate fi calculata in timp O(1) amortizat chiar atunci cand construim vectorul leftMax, retinand valoarea minima dintre toate valorile minime ale intervalelor pe care le scoatem din stiva.

Mentionam ca sunt multe solutii de complexitate O(NlogN), unele dintre ele obtinand 100 de puncte in concurs. Din pacate nu s-a putut face o diferentiere clara intre acesti algoritmi si cel de complexitate liniara, fara a creste semnificativ marimea datelor de intrare.

Tree

Problema cere de fapt o acoperire a arborelui dat cu numar minim de drumuri. O acoperire inseamna ca fiecare nod al arborelui apartine exact unui drum. Daca numarul de drumuri din acoperirea optima este X, atunci raspunsul va fi 2*X-1 deoarece sunt necesare X-1 operatii de stergere pentru a separa drumurile in arbore si inca X operatii de adaugare pentru a conecta drumurile astfel incat sa se formeze un ciclu (primul drum va fi conectat cu al doilea printr-o muchie, al doilea cu al treilea, etc.).

Problema acoperirii cu drumuri pentru un arbore se poate rezolva fie prin metoda greedy, fie prin metoda programarii dinamice, ambele abordari avand complexitate liniara in numarul de noduri. Vom descrie abordarea de tip greedy.

Facem o parcurgere DF din nodul radacina. La fiecare pas din DF avem urmatoarele cazuri:

  • in nodul curent i se unesc mai multe fire (drumuri simple). Daca numarul de fire va fi P, vom adauga la solutie P-1 drumuri si vom elimina subarborele cu radacina in i. Primul drum va fi de la capatul primului fir la capatul celui de-al doilea, iar celelalte drumuri vor fi formate din nodurile dintre capatul unui fir si un fiu al lui i.
  • nodul i este continuarea unui fir (are un singur fiu neeliminat). In acest caz nu adaugam nimic la numarul total de drumuri pentru ca s-ar putea sa unim acest fir mai sus in arbore.

Daca in final ajungem in radacina cu un singur fir, adaugam 1 la raspuns.

Aceasta abordare este foarte simplu de implementat si obtine punctajul maxim.