Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2011-03-29 07:15:10.
Revizia anterioară   Revizia următoare  

Solutii Algoritmiada 2011, Runda 3

Proc2

Solutia 1 :
Pentru un task avem dat timpul de inceput, durata acestuia si trebuie sa aflam procesorul pe care sa ruleze. Pentru un task i dat ne intereseaza indicele minim al unui procesor pe care ruleaza un task j<i si pentru care timpul de terminare ( s + d - 1 ) al lui j este mai mic decat timpul de start s al lui i. Pentru ca sa aflam in mod eficient acest indice minim pastram o coada de prioritati, care va pastra in varf taskul care a fost atribuit unui procesor si care are timpul de terminare cel mai mic. Daca avem doua task-uri cu acelasi timp de terminare, va avea prioritate mai mare cel cu indicele de procesor mai mic.
La pasul i, extragem din coada de prioritati toate task-urile cu timp de terminare mai mic decat si si de la acestea obtinem indicele minim al procesorului caruia ii vom asigna taskul i. Daca nu exista niciun astfel de task, adaugam un procesor nou la lista noastra de procesoare si ii atribuim acestui procesor taskul i. In final inseram in coada de prioritati taskul i cu timpul de terminare si si toate celelalte taskuri extrase din coada de prioritati care nu ruleaza pe procesorul asignat task-ului i cu timp de terminare 0.
Complexitate finala: Aproximativ O(N * M * log M), unde N este numarul de task-uri si M este numarul de procesoare.

Tema: Incercati sa imbunatatiti aceasta aproximare de O(N * M * log M) a algoritmului.

Solutia 2:
Problema poate fi rezolvata utilizand 2 heapuri (sau 2 cozi cu prioritate) astfel : primul (T) pentru a afla ce procesor termina de executat o sarcina cat mai curand si al doilea (P) pentru a afla care este procesorul cu numarul de ordine cel mai mic disponibil la un anumit moment. Pentru fiecare task adaugam in P toate procesoarele care isi termina sarcina intr-un timp <= decat timpul la care trebuie sa inceapa taskul respectiv. Actualizam timpul la care isi termina sarcina procesorul cu numarul de ordine cel mai mic din P si il adaugam in T.

Complexitate : O(M*logM) (deoarece vor fi necesare maxim M procesoare)

Solutia 3:

Problema se poate rezolva si cu ajutorul unui arbore de intervale in complexitatea O(N*log N). Pentru o sarcina care trebuie executata trebuia sa gasim cel mai la stanga procesor liber. Pentru asta facem o interogare in arborele de intervale, care va retine timpul minim de terminare al unei sarcine din intervalul asociat nodului. Dupa ce am determinat acest procesor liber, ii actualizam timpul nou de terminare al procesului in arbore.

Egal

Solutie:

Vom face o notatie pentru simplificarea explicatiei. Daca consideram cheia pentru un seif ca fiind o culoare atunci raspunsul pentru un subarbore o reprezinta culoarea care apare de cele mai multe ori in subarbore.
Vom numi map o structura care poate face rapid ( O(log N) ) urmatoarele operatii:
Adaugarea unei perechi (cheie, valoare), daca cheia respectiva exista deja ca (cheie, valoare_existenta) atunci valoare se adauga la valoarea_existenta
Interogarea pentru o cheie x, mai exact sa se returneze o daca nu exista nicio pereche de forma (x, valoare) sau daca exista (ea fiind unica) sa se returneze aceea valoare
O astfel de structura este clasa map din STL.

Mentinem pentru fiecare nod x un map M pentru care M[i] = j are semnificatia urmatoarea "in subarborele lui x culoarea i apare de fix j ori".

Solutie O(N2 * log N) Worst-case

Facem o parcurgere in adancime. Avand calculat map-urile pentru fiecare fiu putem calcula map-ul nodului curent astfel. Parcurgem map-urile fiecarui fiu si adaugam acea culoare cu numarul de aparitii din map-ul fiuliu in map-ul nodului curent. Cum sunt maxim N culori la un pas(unde N e numarul de noduri) si sunt maxim N pasi, iar o inserare intr-un map are maxim log N operatii obtinem o solutie O(N2 * log N) ca timp si O(N2) ca spatiu.

Solutie O(N * log2 N) Worst-case

Vom tine map-uri doar pentru frunze. Atunci cand incercam sa calculam map-ul unui nod vom fuziona map-urile fiilor intr-unul singur si vom adauga culoarea nodului la acesta(verificand dupa printr-o interogare daca solutia se modifica).
Le vom fuziona astfel: alegem fiul cu cele mai multe noduri in subarbore, luam toti ceilalti fii si adaugam culorile cu numarul de aparitii din map-urile lor in map-ul fiului ales verificand la fiecare pas daca solutia se modifica.
Map-ul nou va deveni map-ul nodului curent.
Vom demonstra ca numarul maxim de pasi este N * log N si operatiile fiind executate in log N pasi obtinem o complexitate de O(N * log2 N) ca timp si O(N * log N) ca memorie

Fie un nod oarecare x. Fie a1, a2, ..., ak - 1 toti stramosii lui astfel incat a1 e parintele lui a2 si a2 e parintele lui a3 s.a.m.d si ak - 1 e parintele lui x si ak = x. Notam cu nr_fii[v] numarul de noduri din subarborele lui v. Atunci culoarea lui x va fi prezenta in fiecare din stramosii lui.
Presupunem ca la fuzionarea intr-un nod ap culoarea lui x e mutata din ap + 1 intr-un alt fiu. Inseamna ca nr_fii[ap + 1] <= nr_fii[ap] / 2 (demonstratie triviala prin metoda reducerii la absurd).
Folosim metoda reducerii la absurd acum: Presupunem ca o culoare dintr-un nod va fi mutata astfel de mai mult de log N ori. Fie ap1, ap2, ..., apm nodurile pentru care se intampla asta( p1 < p2 < ... < pm ) si m > log N. De aici deducem nr_fii[ap1] >= 2 * nr_fii[ap2] >= ... >= 2m * nr_fii[x]. Dar m > log N => 2m * nr_fii[x] > N, fals intrucat numarul de noduri dintr-un subarbore nu poate fi mai mare decat numarul total de noduri.

Se poate scapa de log N la fiecare din solutii utilizand un hash in loc astfel obtinandu-se 100 de puncte cu a doua solutie rafinata la O(N * log N).
Pentru o implementare usoara se poate folosi structura unordered_map din libraria #include <unordered_map> din namespace-ul tr1 (Technical Report 1).

NumereX

Sa notam sirul initial cu A. Ne cream un nou sir, B, B[i] = A[i] - A[i + 1]. Astfel o operatie de tipul UPDATE x, y, k se reduce la a adauga valoarea -k la pozitiile B[i], ∀ i in [x - 1, y - 1] si valoarea k * (y - x + 1) la pozitia B[y]. Aceste operatii se pot efectua eficient cu ajutorul unui arbore de intervale in complexitate O(logN) pe operatie. Se observa ca B[x] + 2 * B[x + 1] + ... + (N - x + 1) * B[N] este de fapt egal cu A[x] + A[x + 1] + ... + A[N]. Astfel, cand dorim sa aflam suma pe un interval [x, y] din A, calculam diferenta dintre suma pe [x, N] si suma pe [y + 1, N] din B.
Astfel, fiecare nod din arborele de intervale va trebui sa retina 3 lucruri:

  • suma pe un interval din B
  • suma de forma B[x] + 2 * B[x + 1] + ... pe un interval din B
  • suma valorilor cu care s-a facut update-uri pe un interval din B

La fiecare update toate acestea trebuie actualizate, atat la update, cat si la query necesitand niste mici observatii matematice.

O solutie alternativa cu aceeasi complexitate ce foloseste arbori indexati binari urmeaza. Sa notam cu s[i] suma primelor i elemente din sirul initial, adica s[i] = a[1] + ... + a[i]. Convenim ca s[0] = 0. Pentru a calcula a[i] + ... + a[j], este suficient sa cunoastem s[j] si s[i-1], caci a[i] + ... + a[j] = a[1] + ... + a[i-1] + a[i] + ... + a[j] - (a[1] + ... + a[i-1]) = s[j] - s[i-1] (Obervati ca, din cauza ca s[0] = 0, formula functioneaza si cand i = 1). Ne intrebam, deci, cum afecteaza un update de forma "0 x l k" sirul s. Fie y = x+l-1, adica pozitia finala a progresiei adaugate. Atunci, pe pozitia i in intervalul [x, y], la a[i] se adauga k * (i-x+1), deci, la s[i] se adauga k + 2*k + 3*k + ... + k * (i-x+1). Rescriind aceasta suma, pentru i in [x, y], la s[i] se adauga k * (i-x+1) * (i-x+2) /2, adica la s[i] se adauga (k * i2 + (3-2x) * k * i + k * (x-1) * (x-2)) / 2. Pentru i > y, la s[i] se aduaga k + 2*k + 3*k + ... + l*k, o constanta ce se poate calcula in timp constant. Ne vine, deci, urmatoarea idee: vom mentine trei siruri p, q, r, cu proprietatea ca 2 * s[i] = p[i] * i2 + q[i] * i + r[i]. Cand vine un query "0 x l k", pentru i in [x, y] la s[i] se adauga (k * i^2 + (3-2x) * k * i + k * (x-1) * (x-2)) / 2, deci la p[i] se adauga k, la q[i] se adauga (3-2x) * k, iar la r[i] se adauga k * (x-1) * (x-2). Pentru i > y, la s[i] se adauga constanta k + ... + l * k, deci adaugam aceasta valoare la r[i] pentru i > y. Astfel, pentru un update trebuie sa adaugam niste valori la a, b, c pe intervalul [i, j], la c pe intervalul [i+1, n], si pentru a afla s[j] sau s[i-1] in query-uri, trebuie doar sa aflam p[j], q[j], r[j], respectiv p[i-1], q[i-1], r[i-1]. Putem face aceste operatii cu trei arbori indexati binar. Astfel, avem complexitatea de O(qlogn).

Elemente

Observam ca ordinea elementelor in sir nu influenteaza numarul de subsiruri cautat asa ca sortam sirul. Astfel vom cauta pentru sirul sortat A numarul de subsiruri distincte care respecta proprietatea ca diferenta dintre oricare doua numere ale subsirului este cel mult egala cu K. Calculam best[i] ca fiind numarul de subsiruri distincte ale sirului format din numerele A[1], ..., A[i] care respecta proprietatea ca diferenta dintre oricare doua numere ale subsirului este cel mult egala cu K.
Avem evident best[1] = 1. Vom pastra de asemenea un indice j, cu proprietatea ca diferenta intre oricare doua numere din M = { A[j], ..., A[i] } este cel mult K si j este minim. Astfel oricare subset al lui M reprezinta un subsir cautat. Cand calculam best[i], ne intereseaza numarul subsirurilor cautate din sirul A[1], ..., A[i] care il contin pe A[i] si cele care nu il contin pe A[i].
Primul numar este best[i - 1], iar cel de-al doilea este numarul de subseturi ale lui M care il contin pe A[i]. Astfel relatia de recurenta este:
* best[i] = best[i - 1] + 2( ( i - 1 ) - ( j - 1 ) ) = best[i - 1] + 2 i - j.
Observatii: M este de fapt un multiset, si nu o simpla multime pentru ca admite duplicate, la fel si subseturile lui, iar j si 2i - j pot fi calculate "din mers".
Complexitate finala O(N log N).

Subsir1000

Problema se rezolva folosind programarea dinamica. Calculam best[i] ca fiind dimensiunea celui mai lung subsir cu ultimul termen divizibil cu i. Evident, vom calcula aceasta dinamica doar pentru numerele i prime.
Pentru fiecare A[i] actualizam vectorul best. Fie x = max {best[p] | p divide A[i], p prim}. Cautand doar printre sirurile care au ultimul termen divizibil cu p se garanteaza ca A[i] si ultimul termen al sirului ales nu vor fi prime intre ele. Pentru fiecare p divizor prim al lui A[i] actualizam vectorul best[p] = x + 1.