Solutii Algoritmiada 2009, Runda 3

Fetite

Vom rezolva problema recursiv. Fie f(N) numarul de ordine al ultimei petale ramase in cazul in care avem la inceput o floare cu N petale. Se disting 2 cazuri:

N este un numar par. Vor fi eliminate toate petalele pare si ne vom intoarce la petala 1. Putem considera ca am redus jocul la N/2 petale, singurul lucru de care trebuie sa avem grija este renumerotarea petalelor. Deducem ca f(N) = 2 * f(N/2) - 1.
N este un numar impar. Vor fi eliminate toate petalele pare si apoi vom elimina petala numarul 1. Vom ajunge la petala 3, si observam ca am redus din nou jocul la N/2 petale. Din renumerotare rezulta f(N) = 2 * f(N/2) + 1.

Complexitatea acestui algoritm este O(log N).

O alta metoda de rezolvare a acestei probleme se bazeaza pe urmatoarea observatie: Oricare ar fi N ( putere a lui 2 ), ultima petala ce va ramane va fi 1.
Daca se iau mai multe cazuri, se observa faptul ca din momentul acela pentru: f(N+1) = f(N) + 2, pana la urmatoarea putere a lui 2.

Exemplu: f(8) = 1 , f(8) = 3 ... f(14) = 13, f(15) = 15, f(16) = 1 ... iar algoritmul se reia.

Se determina P: cea mai mare putere a lui 2, mai mica sau egala decat N. Rezultatul se gaseste in: (N - P) * 2 + 1. Complexitatea este aceeasi.

Recurenta

Pentru a afla termenul de indice n al sirului D vom calcula pe rand toate valorile lui D_i pentru k ≤ i ≤ n. O prima solutie tine un vector de intregi pe 64 de biti si pentru a calcula valoarea lui D_i itereaza pe rand peste toate valorile D_j, i - k ≤ j ≤ i-1, adunandu-le.
Aceasta solutie are complexitate O(n*k) si functioneaza pentru n foarte mic, solutia ia 30 de puncte. O solutie asemanatoare dar care foloseste adunarea pe numere mari va lua 60 de puncte. Se observa ca nu avem nevoie decat de ultimii k termeni ai sirului D pentru a determina valoarea unui termen, astfel putem optimiza memoria folosita de la O(N * nr_mari) la O(K * nr_mari). De asemeni nu este nevoie sa calculam suma ultimilor k termeni la fiecare pas, pentru ca D_i+1 = 2 * D_i - D_i-k. Folosind aceasta relatie de recurenta complexitatea algoritmului este de O(N * nr_mari) si obtine 100 de puncte. Pentru ca solutia sa intre in memorie se va utiliza optimizarea prezentata mai sus sau numerele mari vor fi implementate folosind o baza mare (10⁹)

Par

Exista mai multe solutii la aceasta problema. Folosind programare dinamica putem calcula A[i][j], numarul minim de inversari care trebuie facut pentru a obtine o secventa corect parantezata. A[i][j] se poate obtine din A[i+1][j-1] (avem o secventa corect parantezata in interior) sau din A[i][k]+A[k+1][j] (concatenam doua secvente corect parantezate) pentru k intre i+1 si j-1. Complexitatea va fi O(N³). O idee mai buna ar fi sa calculam C[i][j] numarul minim de inversari astfel incat daca am luat in calcul doar primele i caractere vor ramane j paranteze deschise care trebuie inchise in continuare. C[i][j] poate proveni doar din C[i-1][j-1] sau C[i-1][j-1], deci complexitatea va fi O(N²), suficienta pentru a obtine 100 puncte. Aceasta nu este insa cea mai buna solutie, exista si o solutie greedy care ruleaza in timp liniar. Ne imaginam ca avem o stiva in care tinem parantezele deschise care le avem la un moment dat. Procesam apoi sirul initial de paranteze. Daca paranteza curenta este inchisa si in stiva se afla macar o paranteza deschisa, eliminam din stiva o paranteza deschisa si trecem mai departe. Daca paranteza curenta este inchisa si in stiva nu se afla nicio paranteza deschisa atunci inversam paranteza curenta si o introducem in stiva. Daca paranteza curenta este deschisa o introducem in stiva. Dupa ce am parcurs tot sirul initial trebuie ca in stiva sa existe un numar par de paranteze deschise. Pentru a obtine un numar minim de inversari trebuie inversate exact jumatate din ele.

Kino

Pentru ca suma distanţelor între oricare două şiruri să fie maximă, trebuie să maximizăm distanţele poziţie cu poziţie, deoarece numerele care nu se află pe aceeaşi poziţie nu se afectează reciproc. Astfel, la fiecare pas numărăm câte poziţii libere sunt şi incercăm să le completăm cu numere cât mai puţin utilizate până atunci la poziţia respectivă. Observăm că este suficient să folosim maxim N numere distincte. O soluţie brute force de complexitate O(N²*L) care alege numărul cu frecvenţa minimă la fiecare pas ar fi obţinut 30 de puncte. Pentru a ajunge la soluţia optimă, sortăm şirul frecvenţelor şi obţinem astfel o "scară". Scara se completează treptat pe nivele, la fiecare pas existând două alternative: continuăm să alegem elementul următor de pe nivel sau alegem primul element, pe cel frecvenţa minimă. Complexitatea acestui pas este O(N) şi, deci, complexitatea totală este O(NlogN*L) (din cauza sortării).

Secvmax

Solutie 1

O sa sortam query-urile crescator. Cand parcurgem query-urile in ordinea sortarii unele pozitii din vectorul initial vor putea fi folosite (apar pe parcurs). Acum ne intereseaza sa tinem o structura care sa sa suporte adaugarea unei pozitii intr-un vector si sa ne zica cea mai lunga subsecventa "lipita". Pentru aceasta ori putem sa folosim o structura de date gen "paduri de multimi disjuncte" ori pentru fiecare capat al unei bucati "lipite" tinem celalat capat si de fiecare daca cand introducem o pozitie noua actualizam aceste informatii uitandu-ne la pozitia din stanga si cea din dreapta. Sa luam un exemplu:
Fie sirul initial 1, 2, 4, 2, 3 si query-urile 3, 1, 2, 4 care dupa sortare vor fi 1, 2, 3, 4. O sa parcurgem query-urile in ordinea sortarii. Se poate observa ca atunci cand ajungem la valoarea x a unui query toate valorile mai mici sau egale cu x din vectorul initial pot fi folosite. Trebuie sa gasim cea mai lunga bucata continua (lipita) de elemente mai mici sau egale cu x. Pe exemplu sirul va evolua asa (elementele cu valoarea 1 reprezinta numerele ce pot fi folosite):
----- 1, 2, 4, 2, 3
1 -> 1, 0, 0, 0, 0
2 -> 1, 1, 0, 1, 0
3 -> 1, 1, 0, 1, 1
4 -> 1, 1, 1, 1, 1.
Ca sa gasim cea mai lunga bucata de 1-uri lipite putem proceda in felul urmator: pentru fiecare bucata lipita deja aparuta de la pozitia x la pozitia y tinem doua valori: D[x] = y si L[y] = x (reprezentand capatul opus al bucatii). Lungimea unei astfel de bucati este y - x + 1. Trebuie sa mentinem aceste informatii in timp ce unele noi pozitii apar. Cand o noua pozitie x apare trebuie sa intializam informatia pentru segmentul x - x ( D[x] = x si L[x] = x ). Dupa aceea trebuie sa ne uitam la pozitiile x - 1 si x + 1. Avem doua bucati posibile care trebuiesc lipite cu noua pozitie (daca ambele exista o sa le lipim intre ele) : bucata L[x-1]...x-1 si x+1...D[x+1] ce pot fi unite cu x...x (stim ca aceste bucati exista daca avem o informatie in L[x-1] sau in D[x+1] ). Acum trebuie doar sa actualizam unele L-uri si unele D-uri. Ca sa mentinem cea mai lunga bucata lipita in primul rand trebuie sa observam ca aceasta poate doar sa creasca (doar lipim bucati). Asadar putem sa tinem o valoare lmax care sa o actualizam de fiecare data cand lipim niste bucati noi. Trebuie sa mai avem grija ca nu raspundem la intrebari in ordinea lor initiala ci in ordinea sortarii, de aceea trebuie sa tinem pentru fiecare intrebare pozitia initala pe care apare si sa raspundem la pozitia respectiva (putem tine raspunsurile intr-un vector si sa afisam abia la sfarsit).
Complexitatea acestor solutii (cea prezentata si cea care se foloseste de multimi disjuncte) este O(N log N + M log M) ambele luand punctajul maxim.

Solutie 2

Pentru fiecare element din sir vom calcula st[i] si dr[i] , adica lungimea maxima a unei secvente care se termina cu a[i] si contine doar elemente mai mici sau egale cu a[i], respectiv lungimea maxima a unei secvente care incepe cu a[i] si contine doar elemente mai mici sau egale cu a[i]. Aceste informatii le obtinem cu ajutorul unei stive a carei elemente se vor mentine sortate.
combinand st[i] si dr[i] obtine lungimea maxima a unei secvente care contine doar elemente mai mici sau egale cu a[i], vom nota aceasta valoare best[i]. Vom construi sirul sol[i] = max(best[j]), unde a[j] <= a[i]. Pentru fiecare intrebare vom cauta binar X cel mai mare numar mai mic sau egal cu Q, rapsunsul va fi sol[X]. Complexitatea acestei solutii este O(N log N + M log N).

Solutie oferita de Puni Andrei Paul •crawler

Marmelada

Folosind o parcurgere in latime vom calcula drumul minim de la S la D. Fie K lungimea acestui drum minim. Apoi sortam sirul initial de costuri si realizam o bijectie intre muchiile din drumul minim si primele K costuri din sirul sortat. Restul muchiilor le putem atribui orice cost din cele ramase disponibile. Este clar ca in acest fel obtinem cel mai scurt drum posibil intre S si D, deoarece nu exista un drum mai scurt de K muchii intre S si D si pentru acest drum de lungime K orice atribuire de costuri muchiilor poate genera doar un drum cel mult egal cu cel calculat. Complexitatea va fi deci O(M*logM+N).

Gminmax

Se observa ca daca vrem ca un subgraf sa aibe gradul minim al unui nod X trebuie ca toate nodurile cu grad mai mic ca X sa fie scoase inainte. De aici ne vine ideea sa scoatem nodurile cu grad minim pe rand. La fiecare nod scos avem grija sa actualizam gradele nodurilor vecine nodului scos. La fiecare pas verificam daca gradul minim al unui nod ramas e mai mare ca rezultatul si actualizam. Este destul de evident ca asa descoperim si cel mai mare subgraf optim.

O solutie ar fi sa folosim un arbore de intervale care sa suporte operatiile necesare. Aceasta abordare duce la o complexitate O(M log N).

O alta solutie este un algoritm in complexitate O(N + M) unde ne folosim de N liste in care tinem nodurile. In a i-a lista tinem nodurile cu gradul i. Parcurgem listele in ordine. Pentru lista curenta parcurgem toate nodurile nescoase inca si scadem gradul nodurilor vecine acestuia, inca nescoase. Cand scadem gradul unui nod, copiem acel nod din lista in care se afla in lista cu un grad mai mic la sfarsitul acesteia (mai tarziu cand vizitam acelasi nod in lista lui superioara nu il consideram pentru el a fost scos inainte intr-o lista inferioara). Putem sa folosim o functie recursiva care sa rezolve toate nodurile nevizitate dintr-o lista. Astfel cand inseram un nod intr-o lista inferioara celeia in care ne aflam apelam aceasta functie pentru lista inferioara. Cand terminam cu lista inferioara revenim la lista curenta si asa mai departe. Fiecare nod x va aparea in grad[x] liste.

Din pacate nu se poate face o diferenta clara intre cele doua solutii (la timp), astfel incat ambele iau punctajul maxim (de asemenea ambele ocupa memorie O(N + M)).

Patrulatere

Cea mai simpla solutie la aceasta problema este sa numaram numarul de patrulatere concave cu varfuri in punctele date si sa le scadem din numarul total de patrulatere (combinari de N luate cate 4). Singura modalitate in care se poate forma un patrulater concav este ca unul din cele 4 puncte sa se afle in triunghiul determinat de celelate 3. Astfel deducem ca trebuie sa numaram pentru fiecare triunghi cate puncte contine in interior. Cunoscatorii probabil ca stiu deja cum se rezolva aceasta problema (ea a fost data in mai multe randuri pe infoarena si alte site-uri; de exemplu Tri2).
O sa explic pe scurt cum putem rezolva: pentru fiecare segment determinat de doua puncte i - j calculam cate puncte se afla in trapezul ce se formeaza sub acel segment (trapezul determinat de segment si de o dreapta paralela cu Ox ce trece prin ordonata -INF cu celelalte doua drepte paralele cu Oy ce trec prin capetele segmentului). Acestea putem sa le calculam in O(N³). Avand aceste informatii putem sa calculam cate puncte sunt intr-un triunghi in O(1) adunand sau scazand (in functie de triunghi) cate puncte sunt sub fiecare segment ce determina un triunghi (un fel de includere si excludere). Aceasta abordare duce la o complexitate toatala O(N³) care obtine punctajul maxim.