Solutii Happy Coding 2007 

• Lista de probleme:
• Abc2
• Tritzi
• Regine 2
• Rfinv
• Pali
• Furnica
• Flori 2
• Bitmap
• Cascaval
• Cercuri 3
• Antitero
• Sistem 2
• Optic
• Zvon
• Cerc 2
• Puteri 2
• Aimin
• Multimi
• Nrbanda
• Tramvai
• Biti 3
• Clear
• H
• Permavg
• Kboard

Abc2

O prima abordare care ar parea sa aiba sanse de a obtine punctaj maxim este de a construi un trie al cuvintelor. Cu ajutorul acestui trie putem verifica in complexitate O(L) daca exista vreun cuvant care sa se termine la fiecare pozitie i din sir. Totusi, aceasta solutie are complexitate O(L*lungime text mare) si nu se incadreaza in timp.

Optimizarea consta in construirea automatului finit determinist asociat celor N cuvinte. Acest automat poate fi construit in complexitate O(N*L), conform algoritmului Aho-Corasick. Modul de constructie este asemanator calculului functiei prefix din algoritmul KMP. Construim trie-ul cuvintelor, apoi, pentru un nod X al trie-ului, determinam nodul din trie care corespunde celui mai lung sir de caractere care este sufix al sirului asociat nodului X. Putem calcula aceste valori pe nivele, intrucat un nod Y de tipul celui mentionat mai sus se va afla intotdeauna pe un nivel superior nodului X (dar nu neaparat pe calea de la radacina trie-ului pana la nodul X). Acest automat se poate folosi apoi in cadrul parcurgerii textului dat. Incepem din starea corespunzatoare sirului vid (radacina trie-ului). De fiecare data cand trecem la urmatorul caracter, incercam sa trecem in nodul din trie ce corespunde caracterului respectiv si este fiu al starii curente. Daca acest nod nu exista, la fel ca la KMP, trecem in starea corespunzatoare "prefixului-sufix" al starii curente si repetam acest lucru pana cand ajungem in radacina trie-ului sau intr-un nod care are un fiu ce corespunde caracterului urmator din sir. Daca ajungem intr-un nod ce corespunde unei stari finale, atunci am gasit o aparitie a unui cuvant.

Solutia oficiala foloseste un algoritm de constructie a unui automat finit determinist avand complexitate O(N*L²). Se va construi trie-ul cuvintelor, apoi, pe baza acestui trie, se va calcula un automat care are un numar de stari egal cu numarul de noduri ale trie-ului. Pentru fiecare stare X si fiecare caracter c, se va calcula functia nextState[X,c], reprezentand starea ce corespunde celui mai lung sir care este un subsir al sirului corespunzator starii X concatenat cu caracterul c. Pentru starile X ce au fiu in trie corespunzator unui caracter c, nextState[X,c] va fi egal cu acest fiu. Pentru celelalte caractere si o stare X, vom avea O(L) stari candidate. Mai exact, sa consideram ca TX este tatal nodului X in trie (presupunand ca X nu este radacina trie-ului) si ca avem starile Q₀, Q₁, .., Q_P stari ce corespund sufixelor de lungime 0, 1, .., P ale sirului corespunzator nodului TX (acest sir are P+1 caractere). Atunci multimea de stari R₁, .., R_P+1 avand aceeasi semnificatie pentru nodul X se calculeaza ca fiind R₁=fiu[Q₀,u], R₂=fiu[Q₁,u], .., R_P+1=fiu[Q_P,u], unde X=fiu[TX,u], adica fiul nodului TX, ce corespunde caracterului u. La aceasta multime vom adauga pe R₀=radacina trie-ului (ce corespunde sirului vid). nextState[X,c] va fi egal cu sirul de lungime maxima dintre sirurile corespunzatoare nodurilor fiu[R_i,c], cu 0 ≤ i ≤ P+1. Se observa usor ca pentru orice nod X pot exista cel mult O(L) stari candidate, deoarece sirul corespunzator unui nod X are O(L) caractere.

O solutie mai simpla si care ar obtine punctajul maxim consta in folosirea unor functii de hash, ca in algoritmului Rabin-Karp. Aceste functii trebuie sa fie calculabile usor (in O(1)) atunci cand avem valoarea hash-ului pentru un sir S si dorim sa calculam valoarea pentru sirul S' obtinut prin adaugarea unui caracter la dreapta lui S si inlaturarea unui caracter din stanga lui S. Cateva variante de functii de hash ar putea fi urmatoarele:

• functii polinomiale, cu puteri de numere prime: (c_N*P^N + c_N-1*P^N-1 + c₁*P + c₀) mod Q (P si Q numere prime)
• scrierea sirurilor ca numere in baza 3 (intrucat alfabetul consta doar din 3 litere) => este ideea de mai sus, dar cu P=3.

Probleme asemanatoare

• Dangerous Pattern / ZJU

Tritzi

Algoritm de complexitate O(N)

Vom calcula valorile T[i,j], reprezentand numarul de siruri de i tritzi, pentru care ultimul trit are valoarea j. T[1,j] = (1 mod P). Pentru i > 1, avem:

• T[i, 0] = (T[i-1, 0] + T[i-1, 2]) mod P
• T[i, 1] = (T[i-1, 1] + T[i-1, 2]) mod P
• T[i, 2] = (T[i-1, 0] + T[i-1, 1] + T[i-1, 2]) mod P

Aplicarea directa a acestor relatii de recurenta conduce la un algoritm liniar, care, insa, nu se incadreaza in limita de timp.

Algoritm de complexitate O(log N) - varianta 1

Folosind relatiile de recurenta de mai sus, putem construi o matrice A de iteratie si vom privi T[i] ca pe un vector coloana. Avem relatia: T[i] = A * T[i-1]. T[N] = A^N-1 * T[ 1 ]. T[ 1 ] este cunoscut direct, iar A^N-1 se poate calcula in complexitate O(log N), folosind exponentiere logaritmica.

Algoritm de complexitate O(log N) - varianta 2

Vom calcula o matrice T[x][i][y] = numarul de siruri de tritzi (mod P), de lungime 2ⁱ si pentru care primul trit are valoarea x, iar ultimul trit are valoarea y. T[x][ 0 ][y] se determina direct, iar pentru i > 0, T[x][i][y] va fi egal cu o suma din T[x][i-1][a] * T[b][i-1][y], unde a si b sunt doua valori (0, 1 sau 2) care pot fi plasate una dupa alta.

Apoi vom scrie numarul N ca o suma de puteri ale lui 2: N = 2^p1 + 2^p2 + .. 2^pK. Vom calcula o matrice U[x][i][y] = numarul de siruri de tritzi (mod P) de lungime 2^p1 + 2^p2 + .. + 2^pi, pentru care primul trit are valoarea x si ultimul trit are valoarea y. Avem U[x][ 0 ][y] = T[x][p0][y]. Pentru i > 0, U[x][i][y] este egal cu o suma din U[x][i-1][a] * T[b][pi][y], unde a si b sunt doua valori de tritzi care pot fi plasate una dupa alta. Rezultatul final il vom obtine adunand toate valorile U[x][K][y], unde K este numarul de biti de 1 din reprezentarea binara a lui N.

Probleme asemanatoare

• Iepuri / preONI 2005
• Nice Patterns Strike Back / SGU
• Fibo / .campion 2003

Regine2

Problema se rezolva prin backtracking. Pentru fiecare pozitie (in ordinea liniilor si, pentru fiecare linie, in ordinea coloanelor), se incearca amplasarea sau neamplasarea unei regine in pozitia respectiva, iar apoi se marcheaza toate pozitiile atacate de regina respectiva, pentru a nu se mai incerca amplasarea unei regine viitoare pe o pozitie deja atacata. La intoarcerea din backtracking, pozitiile marcate se demarcheaza (vom folosi, de fapt, un contor pentru fiecare pozitie, in care vom retine de cate regine deja amplasate este atacata pozitia respectiva). Singura optimizare necesara este ca, atunci cand marcam pozitiile atacate de o regina nou-amplasata, vom marca doar pozitiile pe care vom incerca sa amplasam o regina in viitor (adica doar inspre directiile: est, sud-est, sud, sud-vest, si nu in toate cele 8 directii).

Probleme asemanatoare

• Problema celor N regine [ clasica ] & co.
• Dame2 / Summer Challenge 2007

Rfinv

Solutie de complexitate O(N⁴)

Vom sorta toate cele O(N²) distante din matrice in ordine crescatoare si vom initializa o matrice D[i][j]=infinit, pentru i <> j, respectiv 0, pentru i=j. Pe masura ce parcurgem sirul sortat al distantelor, vom actualiza valorile din matricea D. Sa presupunem ca am ajuns la o distanta avand valoarea x, ce reprezinta distanta minima dintre 2 noduri i si j. Daca D[i][j] < x sau D[i][j] > x si nu exista muchie in graf intre i si j, atunci nu avem solutie si ne oprim. Daca D[i][j] > x si exista muchie intre i si j, atunci vom pune pe aceasta muchie costul x. In continuare, va trebui sa actualizam valorile D[a][b] afectate de setarea valorii x pe muchia (i,j). Mai exact, pentru fiecare pereche de noduri (a,b), D[a][b] va fi egal cu minimul dintre valoarea actuala D[a][b] si min { D[a][i] + x + D[j][b], D[a][j] + x + D[i][b] }.

Daca nu am intalnit nici o contradictie pe masura ce am parcurs muchiile, atunci raspunsul este "DA" ; in caz contrar, raspunsul este "NU".

Solutie de complexitate O(N³)

Pe fiecare muchie a grafului (i,j) se pune o distanta egala cu valoarea A[i][j] (A fiind matricea data). Se aplica apoi algoritmul Roy-Floyd pe acest graf, iar matricea distantelor obtinuta trebuie sa fie identica cu matricea distantelor data (in caz contrar neexistand solutie).

Probleme asemanatoare

• Rf / Happy Coding 2006

Pali

Se va calcula pmin[i] = numarul minim de palindroame in care poate fi impartit sirul format din primele i caractere ale sirului dat.

Solutia 1

Vom avea pmin[ 0 ] = 0 si pmin[i] = 1 + min { pmin[j] | subsirul j+1,..,i este un palindrom }, cu 0 ≤ j ≤ i-1. Pentru a determina rapid daca subsirul dintre 2 pozitii k si l este un palindrom, vom calcula o matrice Pali[k][l], avand valorile 1 si 0, daca subsirul dintre pozitiile k si l este palindrom sau nu. Vom avea Pali[k][l] = 1, daca sir[k] = sir[l] si Pali[k+1][l-1]=1 (pentru cazul in care l-k ≥ 2). Pentru ca aceasta solutie sa se incadreze in timp, va trebui ca matricea sa o calculam coloana cu coloana, pe masura ce avem nevoie de valorile din ea.

Solutia 2

Vom incerca sa calculam valorile pmin[i] treptat. Vom parcurge pozitiile de la 1 la N si vom incerca sa incepem un palindrom avand centrul in pozitia i (pentru cazul unui palindrom de lungime impara), respectiv avand centrul la pozitiile i si i+1 (pentru cazul unui palindrom de lungime para). Ideea importanta este ca, atunci cand ajungem la pozitia i, toate valorile pmin[j], cu j < i au fost calculate, iar valorile pmin[k], k > i, au niste valori partiale (adica valorile calculate nu sunt inca finale, ele mai putand sa scada ulterior). Vom extinde treptat cat putem de mult un palindrom in jurul pozitiei i (respectiv pozitiilor i si i+1); la fiecare pas de extindere, vom incerca sa incrementam palindromul de la lungimea curenta L, la lungimea L+2 (pentru aceasta verificam caracterele din capatele palindromului); inainte de a realiza extinderea, vom incerca sa folosim palindromul curent in cadrul unei solutii - mai exact, vom avea posibilitatea ca valoarea pmin[i-(L+1)/2]+1 sa fie folosita pentru a micsora valoarea lui pmin[i+(L+1)/2-1] (pentru cazul lungimii impare), respectiv valoarea pmin[i-L/2]+1 poate fi folosita pentru a micsora valoarea lui pmin[i+L/2] (pentru cazul lungimii pare).

Complexitatea ambelor solutii este O(N²), insa a doua solutie merge mai repede, in practica, deoarece ia in considerare numai palindroamele valide (care pot fi cel mult O(N²)).

Furnica

• daca pozitia de start este 'C', atunci raspunsul este (t+1)²
• daca pozitia de start este 'S', atunci:
  • daca t este par, atunci raspunsul este ((t/2)+1)²
  • daca t este impar, atunci raspunsul este ((t+1)*(t+2)/2)-((t+1)/2)²

Aceste formule (sau altele echivalente) pot fi obtinute folosind urmatorul rationament: furnica se poate afla in orice pozitie aflata la o distanta care are aceeasi paritate ca si t, fata de pozitia initiala. Pentru pozitia de start 'C', aceste pozitii formeaza niste "romburi", iar pentru pozitia de start 'S', aceste pozitii formeaza niste diagonale "secundare".

Flori2

Pentru fiecare punct i, se sorteaza toate celelalte N-1 puncte in jurul punctului i (in functie de unghi). Parcurgand apoi punctele in ordinea sortata, vom determina numarul maxim de puncte avand acelasi unghi fata de i (folosind o precizie corespunzatoare, de 10^-8, de exemplu). Fie acest numar MAX_i. Raspunsul cautat este maxim{MAX_i + 1} si se obtine in complexitate O(N²*logN).

Cosmin: problema s-a dat si la algoritmus. Acolo limita de timp era foarte stransa si solutiile ce au luat punctaj maxim aveau complexitate O(N²). Ajungem la complexitatea aceasta, folosind un hash table pentru a determina numarul maxim de puncte cu acelasi unghi fata de i in loc sa sortam punctele.

Solutia de complexitate O(N³), in care se fixeaza 2 puncte si se determina in O(N) numarul de puncte ce se afla pe dreapta determinata de cele 2 puncte, nu se incadreaza in timp.

Probleme asemanatoare

• Rabbit Hunt / TIMUS
• Maximum Number of Colinear Points / KATTIS

Bitmap

O prima solutie ar consta in a incerca toate cele 4 posibilitati de a codifica un bitmap care nu are toate celulele de aceeasi culoare. Aceasta abordare de tip backtracking nu s-ar incadra in timp. Optimizarea necesara consta in memoizarea starilor prin care trecem in cadrul backtracking-ului (algoritmul nu se mai numeste backtracking acum, ci devine un fel de programare dinamica). O stare este data de 2 numere pe cel mult 11 biti, S₁ si S₂. Bitii de 1 din S₁ definesc liniile selectate din cadrul bitmap-ului initial, iar bitii de 1 din S₂ definesc coloanele selectate din cadrul bitmap-ului initial. Bitmap-ul definit de starea (S₁,S₂) este reprezentat de celulele aflate la intersectia dintre liniile selectate de S₁ si coloanele selectate de S₂. Prin urmare, vom calcula lmin[S₁,S₂] = lungimea minima a bitmap-ului ce corespunde starilor S₁ si S₂. lmin[2^M 1,2^N-1] va contine rezultatul cautat. Pentru ca solutia sa se incadreze in timp, matricea cu valorile asociate fiecarei stari nu trebuie reinitializata la fiecare test. Se va folosi o matrice suplimentara last_test, in care vom memora numarul ultimului test in care am ajuns sa calculam valoarea pentru starea (S₁,S₂). Daca ajungem la starea (S₁,S₂) in testul curent, vom verifica valoarea lui last_test[S₁,S₂]. Daca aceasta este egala cu numarul testului curent, inseamna ca am calculat deja valoarea respectiva; in caz contrar, o vom calcula acum si vom seta last_test[S₁,S₂] la numarul testului curent.

Cascaval

Rezolvarea problemei incepe cu o observatie ne neaparat evidenta. Sa presupunem ca in luna j, compania are X kilograme de cascaval (produse in luna respectiva sau in lunile anterioare si stocate pana in luna j). Sa presupunem, de asemenea, ca aceste X kilograme provin din productia de cascaval din 2 luni diferite, i1 si i2. Vom calcula costurile obtinerii celor X1 si celor X2 kilograme de cascaval:

• C1 = F_i1 + C_i1 * X1 + (S_i1 + S_i1+1 + .. + S_j-1) * X1 = A1 + B1 * X1
• C2 = F_i2 + C_i2 * X2 + (S_i2 + S_i2+1 + .. + S_j-1) * X2 = A2 + B2 * X2

Costul total pentru a avea X kilograme in luna j este C1+C2. Voi arata ca s-ar obtine un cost mai bun daca toate cele X kilograme de cascaval ar fi produse in luna i1 sau in luna i2. Daca am produce toate cele X kilograme in luna i1 si costul obtinut ar fi mai mic sau egal cu C1+C2, am avea urmatoarea relatie:

A1+B1*(X1+X2) ≤ A1+B1*X1+A2+B2*X2, care devine B1*X2 ≤ A2+B2*X2 si apoi *X2 ≤ A2 (1)

In mod similar, daca toate cele X kilograme ar fi produse in luna i2 si costul obtinut ar fi mai mic sau egal cu C1+C2, s-ar obtine relatia: *X1 ≤ A1 (2)

Pentru a demonstra afirmatia, ar trebui ca cel putin una dintre relatiile (1) si (2) sa fie adevarata. Acest lucru este evident. Sa presupunem ca B1 ≥ B2. In acest caz, in relatia (1), am avea in partea stanga o valoarea mai mica sau egala cu 0, iar in partea dreapta o valoarea mai mare sau egala cu 0. Deci relatia (1) este adevarata. Daca B1 ≤ B2, atunci se observa in mod similar ca relatia (2) este adevarata.

Concluzia la care ajungem este ca daca intr-o luna j compania are X kilograme de cascaval, acestea au fost produse toate in aceeasi luna i ≤ j. Aceasta concluzie ne permite sa gandim problema in urmatorul mod: In luna 1 sunt produse un numar suficient de kilograme de cascaval pentru a satisface cererile din lunile 1, 2, .., a. In luna a+1 se produc atatea kilograme de cascaval cate sunt necesare pentru a satisface cererile din lunile a+1, a+2, .., b s.a.m.d. Acest mod de a privi problema ne duce usor cu gandul la o solutie folosind programare dinamica.

Programare dinamica cu complexitatea O(N³)

Vom calcula costurile cmin[i], reprezentand costul total minim pentru a satisface cererile din lunile 1, 2, .., i. Algoritmul este descris in continuare in pseudocod:

cmin[ 0 ] = 0
pentru i de la 1 la N
cmin[i]=infinit
pentru j de la 1 la i
  cost_total = cmin[j-1] + F[j] + C[j] * D[j]
  cost_stocare=S[j]
  pentru k de la j+1 la i
    cost_total = cost_total + (C[j]+cost_stocare) * D[k]
    cost_stocare = cost_stocare + S[k]
  daca cost_total < cmin[i] atunci
    cmin[i]=cost_total

Se variaza valoarea lui i de la 1 la N si pentru fiecare valoare incercam sa calculam cmin[i]. Pentru aceasta, incercam toate valorile j ≤ i care pot reprezenta luna in care sunt produse kilogramele de cascaval necesare in luna i. Apoi calculam costul total pentru cazul in care luna j produce cantitatea de cascaval necesara pentru a satisface cererile din lunile j, j+1, .., i. In cele din urma vom avea in cmin[i] minimul dintre costurile corespunzatoare fiecarei variante de alegere a lunii j. Costul total minim pentru toate cele N luni il avem in cmin[N]. Bineinteles, aceasta solutie nu se incadreaza in limita de timp.

Programare dinamica cu complexitatea O(N²)

Algoritmul descris anterior are complexitatea O(N³). El se poate optimiza, insa, usor la complexitatea $O(N²).

cmin[ 0 ] = 0
pentru i de la 1 la N
  cmin[i] = infinit
  dtotal = 0
  cost_stocare = 0
  pentru j de la i la 1
    cost_stocare = cost_stocare + S[j] * dtotal
    dtotal = dtotal + D[j]
    cost_productie = F[j] + C[j]    dtotal
    cost_total = cmin[j-1] + cost_productie + cost_stocare
    daca cost_total < cmin[i] atunci
      cmin[i]=cost_total

Optimizarea adusa este minora, dar importanta. In algoritmul anterior, cel de-al treilea ciclu era folosit pentru a aduna la costul total costul stocarii cantitatilor de cascaval. In varianta optimizata, am schimbat sensul de parcurgere al variabilei j si, in felul acesta, putem calcula pe parcurs o parte din costul de stocare. Practic, la inceputul fiecarei iteratii din cel de-al doilea ciclu, cost_stocare retine costul stocarii cantitatiior de cascaval din lunile j+1, .., i, el trebuind actualizat doar cu costul de stocare din luna j.

Programare dinamica cu complexitatea O(N*log²N)

Aceasta solutie este semnificativ diferita fata de primele doua si presupune cunoasterea structurii de date numita arbore de intervale. De data aceasta vom privi problema usor diferit. In principiu, vom dori sa calculam acelasi lucru ca si in solutiile anterioare, si anume cmin[i], reprezentand costul total minim pentru a satisface cererile din primele i luni. Cand calculam cmin[i] putem alege luna j in care se produce cantitatea de cascaval necesara in luna i dintre i valori (1,2,..,i). Vom privi aceste i optiuni ca pe niste functii f1, f2, .., fi. Valoarea unei functii fj in punctul x, fj(x), reprezinta costul total minim pentru satisfacerea cererilor din primele x luni, in cazul in care luna j a fost aleasa pentru productia cantitatii de cascaval necesara in luna x.

Solutia va contine ciclul principal existent si in solutiile anterioare, in care este variata valoarea lui i. Pentru fiecare valoare a lui i apare o functie noua (fi), iar noi trebuie sa evaluam valoarea minima fj(i) dintre toate functiile existente (f1, f2, .., fi).

Inainte de trece mai departe vom introduce doi noi vectori SP si DP, reprezentand sume partiale ale costurilor de stocare si ale cantitatilor de cascaval cerute:

• SPi = S1 + S2 + .. + Si
• DPi = D1 + D2 + .. + Di

In continuare vom defini mai detaliat functiile fj care ne intereseaza. O functie fj apare la momentul j si este definita doar pentru valori x de la j la N. Valoarea initiala a functiei este: fj(j) este: fj(j) = cmin[j-1] + Fj + Cj * Dj.

Diferenta dintre doua valori consecutive ale functiei este: Delta fj(i) = fj(i) - fj(i-1) = Cj * Di + (Sj + Sj+1 + .. + Si-1) * Di

Aceasta diferenta reprezinta cu cat creste functia fata de momentul anterior. Diferenta contine costul necesar productiei a Di kilograme in luna j si costul necesar stocarii acestei cantitati din luna j (inclusiv) pana in luna i (exclusiv). Diferenta poate fi scrisa folosind vectorul SP introdus anterior, astfel: Delta fj(i) = Cj * Di + (SPi-1 - SPj-1) * Di.

Putem rescrie aceasta diferenta intr-un mod si mai convenabil, in felul urmator: Delta fj(i) = SPi-1 * Di + (Cj - SPj-1) * Di. Observam ca diferenta consta dintr-un termen ce depinde doar de punctul in care se evalueaza functia (i) si un termen ce reprezinta un produs dintre un factor ce depinde doar de definitia functiei (constant pentru functia fj) si un factor ce depinde doar de punctul in care este calculata functia. Vom nota valoarea Cj - SPj-1 cu Pj.

Sa ne gandim ce efect are acest mod de scriere al diferentei dinte doua valori consecutive ale unei functii fi. In momentul in care trecem de la valoarea i-1 la valoarea i, toate functiile fj anterioare cresc cu aceeasi valoare SPi-1 * Di, precum si cu produsul Pj * Di. Singurul inconvenient in tratarea unitara a tuturor functiilor existente la momentul i este reprezentat de aparitia unei functii noi, fi. Pentru aceasta, vom schimba putin definitia functiilor. Vom considera ca fiecare functie fi are o valoare initiala in punctul i-1, chiar daca ea nu exista, practic, la momentul i-1: fi(i-1) = cmin[i-1] + Fi

In felul acesta, avem Delta fi(i) = fi(i) - fi(i-1) = Ci * Di = (Ci + SPi-1 - SPi-1) * Di = SPi-1 * Di + (Ci - SPi-1) * Di = SPi-1 * Di + Pi * Di.

Folosind aceasta scriere, putem considera ca toate functiile fj (j=1,..,i) au crescut de la pasul i-1 la pasul i cu o valoare Delta fj(i) definita in mod unitar.

Revenind la solutie, la fiecare pas i va trebui sa determinam minimul dintre valorile fj(i), cu j de la 1 la i si sa atribuim acest minim lui cmin[i]. O solutie care ar calcula valoarea fiecarei functii ar fi prea lenta, avand complexitatea O(N²). Chiar si excluzand functiile care nu mai au sanse sa fie minime in viitor, solutia tot nu ar obtine punctaj maxim, din cauza depasirii limitei de timp (totusi, solutia nu trebuie exclusa de la bun inceput, deoarece, cu niste optimizari minore, ea va avea complexitatea O(N * numarul de functii candidate "active"), iar numarul de functii candidate "active" este, in cele mai multe cazuri, semnificativ mai mic decat N). In continuare va fi prezentata o modalitate eficienta de determinare a acestei valori minime.

Intai sa observam ca orice valoare cmin[i] contine o suma de valori constante, pe care le putem calcula de la inceput. cmin[i] va contine suma valorilor (SPj-1 * Dj) (cu j de la 1 la i). Aceasta este suma termenilor comuni fiecarei Delta fj. Prin urmare, vom modifica definitiile functiilor noastre pentru a exclude aceasta suma de valori constante si vom adauga suma respectiva la sfarsit, cand vom afisa rezultatul.

Asadar, vom considera ca Delta fj(i) = (Cj - SPj-1) * Di = Pj * Di. Conform acestei noi definitii, valorile calculate cmin[i] nu mai au semnificatia initiala. Totusi, adaugand la valoarea cmin[N] pe care o vom obtine folosind noile definitii ale functiilor, suma precizata, vom obtine costul total minim dorit. Avantajul excluderii acestei sume din calculul valorilor cmin[i] va fi vizibil in continuare.

Sa consideram o reprezentare in plan a functiilor fj, in care abscisele x iau valori de la 0 la N, iar ordonatele corespund valorilor functiilor fj. Aceste valori pot fi acum si negative, doarece Pj poate fi o valoare negativa. Aceasta reprezentare ne este folositoare doar daca o modificam in felul urmator: abscisa corespunzatoare lunii i este DP[i]. Folosind reprezentarea in plan modificata, se observa ca functiile fj sunt niste semidrepte. Acest lucru este evident si din definitia lor. Ele pornesc de la o valoare initiala si apoi cresc pentru fiecare unitate a coordonatei x cu o valoare egala cu Pj, corespunzand pantei semidreptei.

In acest caz, fiecare functie fj are valoarea minima dintre toate functiile pe un interval de abscise [lj, rj] sau nu are niciodata valoarea minima dintre toate functiile. Acest lucru se poate demonstra usor. Sa presupunem ca functia fj este minima pe doua intervale disjuncte [lj1, rj1] si [lj2, rj2], cu lj2 > rj1. Sa presupunem ca la abscisa rj1, o alta functie fk a depasit functia fj. Mai exact, functia fk avea valori mai mari decat functia fj, iar dupa momentul rj1 a atins valori mai mici. Pentru ca o functie sa o depaseasca pe alta, este necesar ca panta functiei respective sa aiba o valoare mai mica decat a functiei depasite. Prin urmare, Pk < Pj. Dar in aceste conditii, de la abscisa rj1 incolo, functia fk va avea mereu valori mai mici decat functia fj, astfel ca functia fj nu va mai fi niciodata minima. O alta situatie in care functia fj ar putea sa nu mai fie minima dupa abscisa rj1 este pentru ca a aparut o functie fk cu o valoare initiala mai mica decat fj, dar o panta mai mare, astfel ca, in cele din urma, functia fj o va depasi pe functia fk si va redeveni minima. Aceasta situatie este si ea imposibila, din modul de calcul al valorii initiale al unei functii fk. Aceasta valoare initiala este valoarea minima a unei functii existente la momentul k-1, plus valoarea Fk (Fk ≥ 0), iar valoarea minima la momentul aparitiei functiei fk este chiar valoarea functiei fj.

Folosind observatia ca fiecare functie este minima pe cel mult un interval, putem folosi un arbore de intervale pentru a stoca in el semidrepte. Aceasta este o utilizare oarecum neobisnuita a unui arbore de intervale, dar vom vedea ca este foarte utila in cazul acestei probleme. Pseudocodul solutiei este urmatorul:

// calculeaza vectorii SP si DP  
SP[ 0 ] = 0  
DP[ 0 ] = 0  
pentru i de la 1 la N  
  SP[i] = SP[i-1] + S[i]  
  DP[i] = DP[i-1] + D[i]  
// calculeaza vectorul cmin  
cmin[ 0 ] = 0  
pentru i de la 1 la N  
  finit[i] = cmin[i-1] + F[i]  
  P[i] = C[i] - SP[i-1]  
  [li,ri] = find_interval(i) // gaseste intervalul [li,ri] pe care functia fi este minima  
  daca intervalul [li, ri] nu este vid  
    update(li, ri, i, radacina_arborelui_de_intervale)  
  cmin[i] = get_min(i) // determina valoarea minima in punctul i dintre toate functiile existente  
suma = 0  
pentru i de la 1 la N  
  suma = suma + SP[i-1] * D[i]  
afisaza cmin[N] + suma

Cele 3 functii a caror implementare mai trebuie descrisa in detaliu sunt: find_interval, update si get_min.

Functia find_interval

Aceasta functie cauta binar, intre i si N, prima luna li in care functia fi are o valoare mai mica decat toate celelalte functii. In mod similar se cauta binar si ultima luna ri in care functia fi are o valoare mai mica decat celelalte functii. Pentru a gasi capatul stanga al intervalului pe care o functie este minima, va trebui sa observam cum variaza functia in raport cu valoarea minima de la fiecare moment. O descriere generala a acestui comportament (care exclude cazurile particulare) este urmatoarea: la momentul aparitiei, functia va avea o valoarea mai mare decat valoarea minima din acel moment, apoi diferenta va scadea treptat, pana cand functia devine minima ; functia ramane minima pana la un anumit moment, dupa care diferenta dintre valorile functiei si valoarea minima creste. Acest comportament sugereaza ca trebuie folosita o cautare binara pe "derivata" functiei (adica pe diferentele dintre 2 valori consecutive ale functiei si valoarea minima a unei functii in punctele respective).

Pseudocodul pentru calculul capatului stanga al intervalului in care functia fi este minima este urmatorul:

find_interval(i)  
  left=i
  right=N
  li=N+1
  cat timp left <= right
    mid = (left+right)/2
    fi_mid_1 = finit[i]+(DP[mid]-DP[i-1]) * P[i] // valoarea in punctul DP[mid+1]
    fi_mid_2 = finit[i]+(DP[mid + 1]-DP[i-1]) * P[i] // valoarea in punctul DP[mid]
    fmin1=get_min(mid+1) // valoarea minima in punctul DP[mid+1]
    fmin2=get_min(mid) // valoarea minima in punctul DP[mid]
    df1 = fi_mid_1 - fmin1
    df2 = fi_mid_2 - fmin2
    daca (df1 < 0)
      li = mid
      right = mid - 1
    altfel
    daca (df1 - df2 > 0)
      left = mid + 1
    altfel
      right = mid - 1
// la sfarsit, in li se afla capatul stanga al intervalului in care fi este minima (sau N+1 daca nu exista un astfel de interval)

Functiile update si get_min se aplica arborelui de intervale si au complexitate O(logN). Complexitatea functiei find_interval este O(log²N).

Fiecare nod al arborelui de intervale memoreaza indicele i al unei semidrepte al carei interval [li,ri], in momentul determinarii acestuia, continea complet intervalul corespunzator nodului din arborele de intervale. De asemenea, fiecarui nod al arborelui de intervale ii corespunde un interval [ l[nod], r[nod] ].

Functia update

Pseudocodul functiei update este prezentat in continuare:

update(li,ri,i,nod) 
  daca intervalul corespunzator nodului nod este chiar [li,ri], atunci
    index[nod]=i
  altfel
    fs = fiul stanga al nodului nod
    fd = fiul dreapta al nodului nod
    daca l[fd] > ri atunci
     update(li,ri,i,fs)
   altfel
   daca r[fs] < li atunci
     update(li,ri,i,fd)
   altfel
     update(li,r[fs],i,fs)
     update(l[fd],ri,i,fd)

Functia get_min

Fiecare nod din arbore are o referinta catre tatal sau (tata[nod]). Radacina arborelui are o referinta catre o valoare nedefinita (NEDEFINIT). Pseudocodul functiei get_min este urmatorul:

get_min(i)   
  nod = nodul din arbore corespunzator intervalului [i,i] 
  val_min=infinit 
  cat timp nod != NEDEFINIT 
    k=index[nod] 
    daca k este definit atunci 
      fki = finit[k] + (DP[i] - DP[k-1]) * P[k] 
      daca fki < val_min atunci 
        val_min=fki 
    nod=tata[nod] 
  intoarce val_min

Link-uri utile

• Sensitivity Analysis of the Economic Lot-Sizing Problem / MIT -> articolul prezinta o solutie a acestei probleme avand complexitatea optima O(N*logN)

Probleme asemanatoare

• Euro / BOI 2003
• Yogurt Factory / USACO 2005
• Branza / preONI 2007
• Rompetrol / Autumn Warmup 2007

Cercuri3

O metoda simpla este sa translatam primul cerc in originea sistemului de axe de coordonate si sa il rotim pe cel de-al doilea pana cand centrul acestuia se afla pe axa OX (la coordonata X egala cu distanta dintre cele 2 centre). Trebuie analizate cateva cazuri, pe baza valorilor razelor celor 2 cercuri si a distantei dintre centrele lor (cazurile simple sunt cand unul din cercuri se afla complet in interiorul, respectiv complet in exteriorul celuilalt cerc). In cazul in care se decide ca cele 2 cercuri se intersecteaza in 2 puncte, vom observa ca, in urma translatiei si rotatiei efectuate, cele 2 puncte de intersectie se vor afla la aceeasi coordonata x, dar la coordonate y opuse (egale in modul, dar opuse ca semn). Vom determina cele 2 coordonate folosind Teorema lui Pitagora generalizata in triunghiul format din centrele celor 2 cercuri si fiecare din cele 2 puncte de intersectie (deoarece cunoastem lungimile tuturor laturilor). Aria comuna a celor 2 cercuri este acum formata din 2 bucati de cerc, de o parte si de alta a segmentului ce uneste cele 2 puncte de intersectie. Aria fiecareia din cele 2 bucati de cerc se poate scrie ca diferenta dintre aria unui sector de cerc (corespunzator segmentului ce uneste punctele de intersectie) si aria unui triunghi (format din centrul unui cerc si cele 2 puncte de intersectie). O formulare suficient de generala a expresiilor ce calculeaza aria comuna permite tratarea unitara a cazurilor in care cel de-al doilea cerc are centrul in exteriorul, respectiv in interiorul primului cerc.

Link-uri utile

• Circle-Circle Intersection / Mathworld

Probleme asemanatoare

• Cercuri / Happy Coding 2005 [2]
• Cerc2 / Happy Coding 2007

Antitero

cat timp (exista un soldat care se poate deplasa in siguranta intr-o pozitie de unde poate omori un terorist)
  deplaseaza soldatul in pozitia respectiva si elimina teroristul
daca toti soldatii pot ajunge in siguranta la destinatie, atunci deplaseaza-i acolo si incheie misiunea cu succes
altfel: "Mission aborted!"

Aceasta este schita unui algoritm usor de implementat care rezolva problema. Practic, se incearca eliminarea repetata a cat mai multor teroristi, dupa care se incearca deplasarea la destinatie. Rezolvarea problemei implica, asadar, doar parcurgeri repetate ale grafului (de exemplu, DF sau BF), in care unele noduri sunt "blocate" (cele in care se afla teroristi in viata si cele amenintate de teroristi in viata).

Sistem2

Problema se rezolva generand permutari ale celor N variabile si verificand daca ele verifica constrangerile. Ideea importanta este ca verificarea satisfacerii constrangerilor sa nu se realizeze abia dupa ce s-a generat cate o permutarea intreaga, deoarece o astfel de abordare nu s-ar incadra in limita de timp. Pe masura ce selectam o valoare pentru un element i al permutarii, vom verifica toate constrangerile care contin acel element si elemente dinaintea lui i (ale caror valori au fost, de asemenea, deja selectate). Daca cel putin o constrangere nu este satisfacuta, nu vom mai continua generarea permutarii in continuare, ci vom trece la valoarea urmatoare a elementului i (scapand, astfel, de un numar posibil foarte mare de permutari pe care le-am fi generat degeaba). Aceasta optimizarea nu ne-ar fi prea folositoare daca, de exemplu, toate constrangerile contin ultimul element (si verificarea lor se poate face abia la sfarsit), insa, putem schimba ordinea in care selectam valorile elementelor. De exemplu, daca luam elementele in ordinea in care apar acestea in constrangeri (intai cele din prima constrangere, apoi cele din a doua care nu apar si in prima, apoi cele din a treia care nu apar in primele doua s.a.m.d.), putem garanta ca dupa selectarea valorilor a cel mult 4 elemente vom putea verifica prima constrangere si ca dupa cel mult 8 elemente putem verifica a doua constrangere. Daca schimbam si ordinea constrangerilor, in asa fel incat constrangerile cu numar mai mic de variabile sa fie primele, obtinem niste optimizari si mai bune. Alta optimizare utila ar fi aceea ca, daca o constrangere contine P variabile, dupa setarea valorilor a P-1 dintre ele se poate calcula valoarea celeialalte variabile. De asemenea, pentru fiecare element a carui valoare nu a fost setata inca s-ar putea memora multimea valorilor posibile pe care le mai poate lua in continuare (pe baza variabilelor avand valori setate si a multimilor de valori posibile ale variabilelor cu valori nesetate inca, dar impreuna cu care se afla in cel putin o constrangere),

In concluzie, problema nu se rezolva in timp polinomial (lucru care se putea ghici dupa numarul mic de variabile), fiind necesare unele optimizari. Ea poate fi privita ca un caz particular al problemei satisfacerii constrangerilor, care este o problema generala, pentru care au fost studiati multi algoritmi si au fost gasite multe optimizari.

Optic

Sa consideram, pe rand, fiecare nod i al arborelui dat (in ordine, de la frunze spre radacina) si subarborele acestuia. Vom rezolva problema considerand ca arborele consta numai din subarborele cu radacina in nodul i. In felul acesta, cand vom considera nodul i=1, vom avea solutia pentru intreg arborele.

Pentru fiecare nod i al arborelui, strategia optima de distribuire a mesajelor la toate nodurile din subarborele sau consta dintr-un numar X de pasi (momente de timp). In primii Y ≤ X dintre acesti pasi, nodul i va trimite mesaje unor noduri din subarborele sau (nu are sens sa existe momente in care nodul i sa nu trimita mesaj, intercalate intre momente in care nodul i trimite mesaj).

La fiecare din cei Y pasi, un nod j din subarborele lui i va primi mesajul de la nodul i. In continuare, nodul i nu va mai trimite niciodata vreun mesaj unui alt nod din subarborele lui j (daca i ar trimite un mesaj unui nod j' din subarborele lui j, j nu ar putea trimite mesaje in acel pas ; de aceea, am putea decide ca nodul j sa fie cel care trimite mesajul nodului j', in timp ce nodul i ar putea trimite mesajul unui alt nod). Dupa ce un nod j a primit mesajul de la nodul i, vom considera in continuare ca subarborele lui i a ramas fara subarborele lui j (e ca si cum intreg subarborele lui j ar fi fost taiat din subarborele lui i).

Vom calcula valorile Tmin[i][j], reprezentand numarul minim de pasi necesari pentru a distribui mesajul tuturor nodurilor din subarborele nodului i, considerand ca au fost efectuati primii j pasi din cadrul strategiei optime a nodului i si ca au fost taiate din subarborele lui i toti subarborii primelor j noduri care au primit mesajul direct de la nodul i. Evident, cand i=1, in Tmin[ 1 ][ 0 ] vom avea numarul minim de pasi necesari pentru distributia mesajului la toate nodurile din arbore.

Vom calcula, in ordine (de la j=0), toate valorile Tmin[i][j]. Sa observam intai (pentru cazul j=0), ca Tmin[i]⁰ trebuie sa fie mai mare sau cel putin egal cu Tmin[f][ 0 ], unde f este fiu al lui i. Vom cauta binar aceasta valoare, intre maximul dintre valorile Tmin[f]⁰ si N-1. Sa presupunem ca am fixat, in cadrul cautarii binare, T unitati de timp. Vom initializa fiecare fiu f al lui i ca aflandu-se in starea s(f)=0 (adica nu s-a efectuat nici o mutare din cadrul strategiei sale optime). Vom considera fiul f al lui i care are valoarea Tmin[f][s(f)] maxima. Daca T > Tmin[f][s(f)], atunci trimitem mesajul nodului f, scadem din T o unitate de timp si mergem mai departe (ignorand nodul f de acum inainte). Daca, la un moment dat, avem T = Tmin[f][s(f)], atunci se demonstreaza (nu foarte usor, dar nici prea greu) ca nodul i trebuie sa trimita mesaj nodului j care este al s(f)+1-lea nod la care ar trimite mesaj nodul f in cadrul strategiei sale optime. In felul acesta, taiem subarborele nodului j, scadem T cu 1 unitate si trecem nodul f din starea s(f) in starea s(f)+1 (pentru ca deja s-a efectuat o mutare din cadrul strategiei sale optime). Daca, la un moment dat, T < Tmin[f][s(f)], atunci trebuie incercata o valoare mai mare in cadrul cautarii binare.

Inainte de a calcula Tmin[i][j+1] dupa ce am calculat Tmin[i][j], memoram in Mut[i][j] nodul la care a trimis mesaj nodul i prima data (adica al j+1-lea nod din cadrul strategiei optime a nodului i) si in F[i][j] fiul din subarborele caruia face parte nodul Mut[i][j]. De asemenea, starile fiiilor nodului i se seteaza la valorile pe care le aveau inainte de a calcula Tmin[i][j], incrementand doar starea fiului F[i][j] cu 1 (sau eliminand de tot fiul F[i][j], daca F[i][j] = Mut[i][j]). Vom termina calculul acestor valori atunci cand Tmin[i][j]=0.

Partea cea mai grea de demonstrat a algoritmului este data de cazul in care numarul de unitati de timp T este egal cu maximul dintre Tmin[f][s(f)]. Intai vom observa ca e clar ca trebuie sa trimitem mesajul unui nod din subarborele lui f, in caz contrar, la momentul de timp urmator vom avea T < Tmin[f][s(f)]. Problema consta in alegerea nodului caruia sa trimitem acest mesaj. Observam ca, in acest caz, problema este similara cazului in care nodul f, aflat in starea s(f), a primit anterior mesajul de la cineva si trebuie sa il trimita unui nod din subarborele sau; dar aceasta problema am rezolvat-o deja, nodul care trebuie sa primeasca mesajul fiind Mut[f][s(f)].

Pentru reconstituirea solutiei, vom initializa toate nodurile ca aflandu-se in starea 0 si vom tine un vector cu nodurile la care a ajuns deja mesajul. Prima mutare va fi de la nodul 1 la nodul j = Mut[ 1 ][ 0 ]. Pentru toate nodurile de pe calea de la 1 (inclusiv) la j (exclusiv), vom incrementa starea in care se afla acestea, apoi vom marca ca nodul j a primit mesajul. La urmatorul moment de timp, vom lua fiecare nod care detine mesajul, vom verifica daca mai are de efectuat pasi din strategia sa optima si daca da, vom efectua pasul corespunzator in mod similar mutarii descrise mai sus.

Complexitatea solutiei descrise este O(N³ * logN).

O dificultate suplimentara apare in momentul in care avem mai multi fii f ai unui nod i, pentru care Tmin[f][s(f)] are aceeasi valoare maxima. In aceasta situatie, va trebui sa il alegem pe cel pentru care sirul Tmin[f][s(f)], Tmin[f][s(f)+1], .. este maxim din punct de vedere lexicografic. Justificarea este ca vrem sa scapam de acel fiu care ne-ar restrictiona cel mai mult mutarile ulterioare daca nu l-am taia acum. Mai exact, daca la un moment dat ajungem cu T-ul egal cu Tmin[f][s(f)] (deoarece am eliminat altii fii si nu pe f), vrem ca acest fiu f sa aiba sirul respectiv cat mai mic din punct de vedere lexicografic, pentru a ne restrictiona cat mai putin timpul.

Link-uri utile

• Information Dissemination in Restricted Routing Networks / CiteSeer -> in acest articol este prezentata o solutie de complexitate O(N³) la aceasta problema

Zvon

Solutia "oficiala" are complexitatea O(N*logN) si presupune calculul urmatoarelor valori:

• TMIN[i] = timpul minim necesar pentru a propaga zvonul in subarborele lui i, din momentul in care i afla zvonul. In mod clar, TMIN¹ reprezinta rezultatul cautat.

Pentru a calcula TMIN[i], vom calcula intai valorile TMIN ale fiiilor lui i, pe care le vom sorta apoi descrescator: TMIN[f1] ≥ TMIN[f2] ≥ .. ≥ TMIN[fK]. Ordinea in care i va transmite zvonul fiilor sai este chiar ordinea descrescatoare a valorilor TMIN a acestora. In aceste conditii, TMIN[i] = maxim { 1 + TMIN[f1], 2 + TMIN[f2], .., K + TMIN[fK] }.

Probleme asemanatoare

• Consiliul tribului / BOI 2003
• Optic / Happy Coding 2007

Cerc2

Observam ca distanta dintre oricare 2 puncte in care fotonul atinge cercul este aceeasi ca cea dintre punctul initial si punctul (R*cos(alfa), R*sin(alfa)). Fie aceasta distanta D. Dupa S secunde, fotonul se afla la o distanta S mod D de ultimul punct in care a atins cercul. Operatia modulo se poate defini si pentru numere reale, scriind S ca fiind k*D + r, unde k este un numar intreg (si r este restul impartirii). Putem folosi acum Teorema lui Pitagora generalizata, pentru a determina distanta de la foton la centrul cercului, in triunghiul format din punctul curent, ultimul punct de atingere a cercului si centrul cercului. O metoda mai simpla de a calcula aceasta distanta este de a calcula distanta de la centrul cercului la segmentul dintre 2 puncte consecutive in care fotonul atinge cercul (aceasta distanta este R*sin(beta)). Cum perpendiculara din centrul cercului pe acest segment il intersecteaza exact in mijloc, putem folosi distanta fotonului fata de mijlocul segmentului si apoi Teorema lui Pitagora intr-un triunghi dreptunghic, pentru a calcula distanta de la foton la centrul cercului (in triunghiul format de centrul cercului, mijlocul segmentului si pozitia fotonului, distanta respectiva este lungimea ipotenuzei).

Probleme asemanatoare

• Cercuri / Happy Coding 2005 [2]
• Cercuri3 / Happy Coding 2007

Puteri2

Problema cere determinarea radicalului de ordin P dintr-un numar mare. Exista mai multe metode de realiza acest lucru, dintre care voi mentiona doua:

• Determinarea radicalului de ordin P cifra cu cifra: Se determina intai numarul de cifre ale numarului (se incadreaza radicalul intre un 10^x si 10^x+1), apoi se determina, pe rand, fiecare cifra a rezultatului; pentru fiecare pozitie, se incearca, pe rand, toate cifrele de la 0 la 9 si ne oprim la ultima cifra pentru care numarul ridicat la puterea P (considerand ca cifrele de dupa cifra curenta sunt egale cu 0), nu depaseste N-ul dat. Eventual, cifra curenta se poate cauta binar (poate fi util daca rezultatul este tinut intr-o baza mai mare decat 10).
• Cautarea binara a rezultatului, intre o limita inferioara si o limita superioara. Numarul fixat in cadrul cautarii binare se ridica la puterea P si daca depaseste N-ul dat, se pastreaza jumatatea inferioara a intervalului de cautare; in caz contrar, se pastreaza jumatatea superioara a intervalului.

Pe langa alegerea uneia dintre cele 2 metode, sunt necesare cateva optimizari suplimentare, precum:

• ridicarea la puterea P trebuie realizata folosind exponentiere logaritmica; in plus, chiar si in cadrul exponentierii logaritmice, putem sa nu efectuam toti pasii daca, la un moment dat, numarul de cifre ale numarului obtinut depaseste numarul de cifre ale lui N
• efectuarea tuturor calculelor intr-o baza mai mare decat 10 (solutia oficiala foloseste baza {10⁴}), deoarece, astfel, numarul de cifre ale numerelor ce intervin in calcule scade simtitor.
• in cazul cautarii binare, intervalul initial de cautare nu trebuie sa fie [1,N], ci un interval mai restrans (de exemplu, [10^(X/P)-1, 10^(X/P)+1]), unde X este numarul de cifre ale numarului N dat.

O alta optimizare care ar fi putut avea un impact simtitor asupra timpului de executie este inmultirea a doua numere mari in complexitate O(C*logC), unde C este numarul de cifre ale acestora, insa implementarea unei astfel de operatii ar fi fost mai complicata (si nu era necesara pentru a obtine punctaj maxim la problema) (vezi aici)

Aimin

Solutia de complexitate O(N³) este evidenta. Se calculeaza HMIN[i, j], reprezentand inaltimea minima a unui arbore ce contine frunzele din intervalul i, .., j. HMIN[i, i] = L_i, iar HMIN[i, j] = 1 + min { max {HMIN[i,k], HMIN[k+1,j]} } (pentru i < j si i ≤ k < j ). Raspunsul il avem in HMIN[1, N]. In mod evident, pentru limitele date, algoritmul nu are nici o sansa sa se incadreze in limita de timp (sau de memorie).

Pentru rezolvarea acestei probleme vom folosi un algoritm greedy, avand complexitatea O(N). Vom parcurge sirul frunzelor de la stanga la dreapta si vom mentine o stiva ce corespunde drumului cel mai din dreapta a arborelui de inaltime minima de pana atunci. Sa presupunem ca am calculat arborele de inaltime minima ce corespunde primelor i frunze si acest arbore are pe drumul cel mai din dreapta niste noduri aflate la nivelele 0, 1, 2, .., K (deci K+1 noduri in total). Pentru fiecare nod de pe acest drum, cunoastem nivelul acestuia, precum si inaltimea subarborelui ce are radacina in nodul respectiv (H[i]). Vom avea H[ 0 ] ≥ 1 + H[ 1 ] ≥ 2 + H[ 2 ] ≥ .. ≥ K + H[K]. Cand introducem a i+1-a frunza, ea va fi ultimul nod de pe drumul cel mai din dreapta al arborelui. Pentru a o introduce pe acest drum, va trebui sa introducem un nod suplimentar deasupra unui nivel x, care sa aiba ca fiu dreapta frunza i+1 si ca fiu stanga subarborele ce corespundea nivelului x dinainte (si care avea inaltimea H[x]) - vom numi aceasta operatie split deasupra nivelului x. In urma acestei operatii, inaltimea subarborelui de pe nivelul x si de pe drumul cel mai din dreapta va deveni egala cu Hnou[x]=1+max{L[i+1], H[x]}. Vom dori sa aplicam operatia de split unui nivel cat mai de jos, dar care sa nu determine cresterea inaltimii arborelui nostru (daca se poate). Mai exact, vom incerca sa aplicam operatia split deasupra unui nivel x, pentru care are loc proprietatea 1+Hnou[x] ≤ H[x-1] (adica nu se mareste inaltimea subarborelui de pe nivelul x-1). In mod clar, daca un astfel de nivel x ≥ 1 nu exista, va trebui creata o radacina noua, iar inaltimea arborelui va creste (fiind egala cu 1+max{H[ 0 ],L[i+1]}). Vom observa ca acest cel mai din dreapta drum al arborelui se comporta ca o stiva, deoarece, daca la un moment dat nu putem realiza operatia de split deasupra celui mai de jos nivel de pe drum, atunci va trebui neaparat sa o realizam mai sus si subarborele respectiv nu se va mai afla, dupa aceea, pe cel mai din dreapta drum al arborelui.

Corectitudinea algoritmului prezentat poate fi demonstrata folosind urmatoarele elemente:

• Presupunem ca avem un arbore de inaltime minima pana la pasul i. Daca la pasul i+1 nu aplicam operatia split deasupra nivelului 0, atunci inaltimea arborelui nu creste si cum inaltimea minima pentru i+1 frunze nu poate fi mai mica decat cea pentru i frunze, raspunsul este corect.
• Daca pana la pasul i avem un arbore de inaltime minima HMIN[i] si la pasul i+1 ajungem sa aplicam operatia split deasupra radacinii, atunci avem 2 cazuri:
  • Daca L[i+1] ≥ HMIN[i], atunci noua inaltime HMIN[i+1] va fi 1+L[i+1] si este optima (deoarece inaltimea minima este mai mare sau egala cu 1+max{L[orice frunza]})
  • Daca L[i+1]<HMIN[i], atunci avem ca H[ 0 ]=1+H[ 1 ]=2+H[ 2 ]=...=K+H[K] (in caz contrar nu am ajunge sa aplicam operatia de split deasupra radacinii). Vom presupune prin absurd ca ar exista un alt arbore de inaltime minima pana la pasul i, care sa aiba un drum cel mai din dreapta diferit de cel la care am ajuns, care ar fi permis introducerea frunzei i+1 fara a creste inaltimea arborelui. Aceasta este etapa cea mai importanta a demonstratiei si, in urma analizei catorva cazuri, se va ajunge la o contradictie; contradictia va consta in faptul ca acest presupus arbore ar urma sa aiba o inaltime mai mica decat HMIN[i], ceea ce este absurd.

Pentru o abordare matematica formala a problemei, care foloseste notiuni de calcul algebric pentru obtinerea unui algoritm liniar, puteti citi urmatorul articol.

Pentru a obtine punctaj maxim, datorita limitei de timp nu foarte stricte, se putea implementa si un algoritm cu complexitatea O(N*logN), folosind structuri de date precum arbori indexati binar sau arbori de intervale ; de exemplu, o solutie asemanatoare constructiei unui arbore Huffman, bazata pe unirea repetata a cate doi subarbori alaturati pentru care maximul inaltimilor este minim.

Multimi

Se considera matricea M cu n linii si m coloane, unde M[i][j]=1, daca i este in A_j si 0, altfel. Deoarece A₁,...,A_m separa multimea [n], rezulta ca oricare 2 linii ale matricei sunt diferite (daca liniile k si l ar fi egale, atunci k si l nu pot fi separate). De aici rezulta ca n ≤ 2^m (numarul de linii posibile, astfel incat oricare 2 sa fie diferite). Asadar, m ≥ log₂n. Vom arata ca m=(log₂n) + 1. Presupunem prin absurd ca m=log₂n. Din principiul lui Dirichlet se obtine cu usurinta faptul ca fie apare in matrice linia 00..0 (contradictie cu conditia de acoperire), fie matricea contine 2 linii identice, ceea ce este absurd.

Pentru m=(log₂n)+1 se poate da exemplul urmator: A_j este multimea numerelor mai mici sau egale cu n care au 1 pe bitul (j-1) din reprezentarea lor binara pe m biti (am numarat bitii de la stanga catre dreapta, incepand cu bitul 0)

Nrbanda

Se roteste intreg sirul la stanga, pana cand pe prima pozitie se afla numarul 1. Apoi problema se rezolva incremental, pas cu pas. La pasul i (2 ≤ i ≤ N), avem numerele de la 1 la i-1 pe primele i-1 pozitii si vom dori sa aducem numarul i pe pozitia i (daca nu se afla deja acolo). Pentru aceasta, rotim sirul spre dreapta pana cand numarul i ajunge pe ultima pozitie. Apoi separam sirul intre pozitiile N-1 si N pana cand pe pozitiile N-i+1, N-i+2, .., N-1 se afla numerele 1, 2, .., i-1 (la fiecare separare, numarul i ramane pe ultima pozitie, iar numerele de pe pozitiile 1,..,N-1 se rotesc spre stanga). Apoi se roteste intregul sir spre stanga, pana cand numerele 1, .., i ajung pe pozitiile 1, .., i.

Probleme asemanatoare

• Order2 / Lista lui Francu

Tramvai

Se construieste un graf al punctelor de intersectie dintre oricare 2 drepte. Acest graf are O(N²) noduri, insa fiecare nod are cel mult 4 vecini (cate 2 pe fiecare din cele 2 drepte care il determina). Problema se reduce acum la determinarea drumului minim intre 2 puncte in acest graf. Algoritmul folosit de solutia oficiala este Dijkstra's_algorithm cu heap, care are complexitatea O(N²*logN), insa se poate folosi cu succes si algoritmul Bellman-Ford, implementat folosind o coada (aceasta varianta, cunoscuta ca algoritmul Bellman-Ford-Moore, are o complexitate teoretica mare, dar, in practica, merge foare bine; este, posibil, insa, ca, in cazul acestei probleme, sa fie necesare unele optimizari pentru a se incadra in limita de timp - de exemplu, folosirea euristicii "parent checking").

Biti3

Vom considera bitii fiecarui sir numerotati de la N la 1 (de la stanga la dreapta) si vom calcula num[i, j] = numarul de siruri de i biti, continand exact j biti de 1. num[i, 0] = 1. Pentru j > i, avem num[i, j] = 0 ; altfel, num[i, j] = num[i-1, j] + num[i, j-1] (cele 2 variante corespund deciziei de a plasa un bit de 0 pe pozitia i, caz in care pe pozitiile 1,..,i-1 se afla j biti de 1, respectiv un bit de 1 pe pozitia i, caz in care pe pozitiile 1,..,i-1 se mai afla doar j-1 biti de 1). Alt mod de a calcula aceste valori este urmatorul: num[i,j] = Combinari de i luate cate j.

Folosind aceste valori, vom determina bitii celui de-al M-lea sir, unul cate unul, pornind de la al N-lea bit. La fiecare pas, va trebui sa determinam cate siruri incep cu bitul 0 si cate siruri incep cu bitul 1. La inceput, vor exista num[N-1,3] siruri care incep cu bitul 0 si num[N-1,2] siruri care incep cu bitul 1. Este evident ca, la un anumit pas, toate sirurile care incep cu 0 se vor afla inaintea tuturor sirurilor care incep cu 1. De aceea, daca M < numarul sirurilor care incep cu 0, bitul respectiv va fi 0; in caz contrar, bitul va fi 1. Daca bitul este 1, inainte de a trece la pasul urmator, va trebui sa actualizam valoarea lui M, in asa fel incat sa sarim peste toate sirurile care incep cu 0 ({M = M - numarul de siruri care incep cu 0), precum si sa tinem cont de faptul ca am mai consumat inca un bit de 1. Algoritmul in pseudocod este urmatorul:

nrbiti = 3  
for i = N -> 1  
  daca num[i-1, nrbiti] >= M atunci  
    bitul i este 0  
  altfel  
    bitul i este 1  
    M = M - num[i-1, nrbiti]  
    nrbiti = nrbiti - 1

Probleme asemanatoare

• Stringsobits / USACO 1998
• Word Encoding / ACM ICPC NWERC 2004
• Coding of Permutations / POJ
• Bits of Trinity / ACM ICPC NWERC 1999'
• Parantezari / Baraj ONI 2000

Clear

Probleme cere acoperirea cu numar minim de drumuri/cicluri a unui subgraf al grafului-grid MxN. Problema este foarte asemanatoare cu problema Kcity , propusa in cadrul rundei 3 a concursului Autumn-Warmup 2007 si, daca numerotam nodurile grafului incepand de la 1, parcurgand matricea pe linii, iar pentru fiecare linie, pe coloane, obtinem un graf care are aceeasi proprietate cu cel din Kcity (modulul diferentei dintre numerele asociate a doua noduri conectate printr-o muchie este limitat de o constanta: 7, respectiv 10). Totusi, aplicand direct ideea de rezolvare de la Kcity, se obtine un numar prea mare de stari, care nu permite incadrarea solutiei in limita de timp stabilita.

Solutia 1 (O(M * nr_stari(N) * O(4^N)))

Acoperirea cu numar minim de drumuri

Vom calcula valorile minp[i, S], reprezentand numarul minim de drumuri cu care pot fi acoperite toate zonele afectate de pe liniile 1,..,i, iar pe linia i, configuratia drumurilor este data de starea S. Starea S contine, pentru fiecare coloana de pe linie, un numar reprezentand starea coloanei respective:

• 0 - zona de pe coloana respectiva are gradul 2 (este in interiorul unui drum) sau are valoarea 0 in matrice
• num > 0 - zona respectiva este capatul unui drum (avand identificatorul num)

In cadrul unei stari, identificatorul unui drum se poate repeta de cel mult 2 ori (deoarece un drum are maxim 2 capete). Identificatorii din starea S au valori ordonate crescator in functie de prima aparitie in cadrul starii S. Observam ca nu mai trebuie sa identificam explicit un nod avand gradul 0 (reprezentand un drum format dintr-un nod), deoarece orice nod din starea S mai poate fi conectat doar la cel mult un alt vecin (de pe linia urmatoare). Proprietatea importanta care reduce mult numarul de stari este ca drumurile existente in starea S respecta conditia de "parantezare": mai exact, daca cele 2 capete ale unui drum X se afla pe coloanele c1 si c2, iar cele 2 capete ale unui drum Y se afla pe coloanele c3 si c4, atunci [c1, c2] este inclus in [c3, c4] (sau invers). Aceasta proprietate se datoreaza faptului ca orice subgraf al grafului-grid este planar.

Pentru a calcula starile asociate liniei i, vom porni de la fiecare stare S' asociata liniei i-1 si vom folosi un algoritm de backtracking pe linia i care va genera starile S ce pot fi obtinute din starea S', alegand, pentru fiecare zona afectata de pe linia i, cate o varianta posibila dintre urmatoarele:

• incepe drum nou (in cazul functiei de backtracking vom diferentia nodurile ce au grad 0, de celelalte noduri, insa atunci cand se calculeaza starea corespunzatoare liniei, aceste noduri vor primi un identificatior de drum strict pozitiv) -> numarul de drumuri creste cu 1
• uneste nodul curent de nodul din stanga -> numarul de drumuri ramane constant
• uneste nodul curent de nodul de sus -> numarul de drumuri ramane constant
• uneste nodul curent de nodul de sus, precum si de cel din stanga (numai daca nodul din stanga si cel de sus nu fac parte din acelasi drum si amandoua sunt capete de drumuri) -> numarul de drumuri scade cu 1

La final, vom alege valoarea minima dintre valorile minp[M, S]. Acest algoritm are, insa, o complexitate de timp prea mare si nu se incadreaza in limita de timp.

Acoperirea cu numar minim de cicluri

Vom calcula valorile minc[i, S], reprezentand numarul minim de cicluri (inchise), astfel incat fiecare nod de pe liniile 1,..,i sa se afle pe un ciclu inchis sau deschis. Starea S contine, pentru fiecare coloana de pe linie, un numar reprezentand starea coloanei respective:

• 0 - zona de pe coloana respectiva are gradul 2 (este in interiorul unui ciclu inchis sau deschis) sau are valoarea 0 in matrice
• num > 0 - zona respectiva este capatul unui ciclu deschis (avand identificatorul num)

In cadrul unei stari, fiecare identificator al unui capat de ciclu deschis apare de exact 2 ori (nu pot ramane capete de cicluri deschise in spate, caci aceste cicluri nu ar mai putea fi inchise ulterior). La fel ca si in cazul acoperirii cu cicluri, identificatorii ciclurilor sunt numerotati de la 1, crescator, in functie de prima aparitie in cadrul starii, avand si ei proprietatea de "parantezare".

Pentru a calcula starile asociate liniei i, vom porni de la fiecare stare S' asociata liniei i-1 si vom folosi un algoritm de backtracking pe linia i care va genera starile S ce pot fi obtinute din starea S', alegand, pentru fiecare zona afectata de pe linia i, cate o varianta posibila dintre urmatoarele:

• incepe ciclu deschis nou (in cazul functiei de backtracking vom diferentia nodurile ce au grad 0, de celelalte noduri, insa atunci cand se calculeaza starea corespunzatoare liniei, aceste noduri vor primi un identificatior de ciclu strict pozitiv) / aceasta varianta este aplicabila numai daca nodul din stanga nu este si el un ciclu deschis nou si daca nodul de deasupra este in starea 0 -> numarul de cicluri inchise ramane constant
• uneste nodul curent de nodul din stanga / aceasta varianta este aplicabile numai daca nodul de deasupra se afla in starea 0 iar cel din stanga nu se afla in starea 0 -> numarul de cicluri inchise ramane constant
• uneste nodul curent de nodul de deasupra / aceasta varianta este aplicabila numai daca in nodul de deasupra nu avem starea 0, iar in nodul din stanga nu s-a deschis un ciclu nou -> numarul de cicluri inchise ramane constant
• uneste nodul curent de nodul de sus, precum si de cel din stanga / numai daca atat nodul de sus, cat si cel din stanga nu se afla in starea 0
  • daca nodul din stanga si cel de sus fac parte din acelasi ciclu -> numarul de cicluri inchise creste cu 1
  • daca nodul din stanga si cel de sus nu fac parte din acelasi ciclu -> numarul de cicluri inchise ramane constant (cele 2 cicluri deschise se combina intr-un singur ciclu deschis)

La final, rezultatul dorit il gasim in minp[M, S₀], unde S₀ este starea in care toate nodurile de pe linia M se afla in starea 0 (sunt in interiorul unui ciclu). Ca si in cazul acoperirii cu drumuri, nici aceasta solutie nu se incadreaza in limita de timp. Totusi, din cauza restrictiilor suplimentare de generare a starilor (trebuie sa nu se "uite" cicluri deschise in urma), algoritmul de backtracking are, in general, mai putine optiuni de continuare. Din acest motiv, numarul de coloane pentru acest caz este 10 (fata de 7 in cazul acoperirii cu drumuri).

Solutia 2 (O(M * N * nr_stari(N)))

Acoperirea cu numar minim de drumuri

Vom parcurge matricea pe linii, si pentru fiecare linie, pe coloane. Vom mentine o stare S asemanatoare celei din solutia prezentata mai sus, la care se mai adauga un indice C (1 ≤ C ≤ N), avand semnificatia ca valorile de la C+1 la N se refera la pozitiile de pe linia de deasupra, iar valorile de pe pozitiile de la 1 la C (din cadrul starii) se refera la linia curenta. Mentinand starea in acest fel, cand ajungem la elementul de pe linia L si coloana C, vom calcula toate starile pentru care indicele este egal cu C. Pentru aceasta, vom parcurge toate starile S' corespunzatoare coloanei anterioare ($C-1$ sau N, daca C este prima coloana) si vom genera toate starile S cu indicele egal cu C, avand de ales dintre urmatoarele optiuni:

• incepe drum nou -> numarul de drumuri creste cu 1
• uneste nodul curent de nodul din stanga -> numarul de drumuri ramane constant
• uneste nodul curent de nodul de sus -> numarul de drumuri ramane constant
• uneste nodul curent de nodul de sus, precum si de cel din stanga (numai daca nodul din stanga si cel de sus nu fac parte din acelasi drum) -> numarul de drumuri scade cu 1

Sunt, practic, aceleasi optiuni ca si cele din prima solutie, numai ca acum nu mai facem backtracking pe fiecare linie. Fata de solutia anterioara, care memora starile numai la sfarsitul unei linii, acum avem si stari "partiale", pana la o anumita coloana de pe o linie. Din cauza ca avem stari "partiale", va trebui sa consideram, pentru coloana curenta, si posibilitatea ca elementul respectiv sa fie singurul element de pe un drum (folosind, de exemplu, valoarea -1 pentru a codifica acest lucru). Pentru starile ce corespund ultimei coloane, aceasta posibilitate nu este necesar sa fie luata in considerare.

Acoperirea cu numar minim de cicluri

Solutia pentru acoperirea cu numar minim de cicluri se bazeaza tot pe memorarea unor stari "partiale" (pentru fiecare coloana de pe o linie), spre deosebire de solutia ce memora doar stari pentru cate o linie completa. Prin memorarea acestor stari "partiale", se evita backtracking-ul pe fiecare linie.

O problema care trebuie luata in considerare in cadrul algoritmului este aceea de a asocia fiecarei stari un numar de la 1 la numarul total de stari (sau incepand de la 0), precum si, dat fiind numarul unei stari, sa gasim repede starea ce corespunde acelui numar. Pentru a doua problema, putem tine un vector al tuturor starilor si pur si simplu sa accesam stare[i], unde i este indicele starii care ne intereseaza. Prima problema este ceva mai complicata si pentru rezolvarea ei exista cel putin urmatoarele variante:

• memoram starile intr-un vector si le tinem sortate lexicografic, astfel ca putem sa cautam binar o stare S in acest vector
• putem folosi o functie de hash, care sa calculeze pentru fiecare stare o valoare unica (de exemplu. privind-o ca un numar in baza X, unde X este numarul total de valori distincte ce ar putea aparea in cadrul unei stari); apoi, mentinem o tabela hash sau un arbore echilibrat (de exemplu, set sau map in STL), care sa asocieze fiecarei valori hash a unei stari, indicele acesteia (un numar intre 1 si numarul total de stari, sau intre 0 si numarul total de stari minus 1).

Probleme asemanatoare

• Kcity / Autumn Warmup 2007
• Pipes / ACM ICPC NWERC 2004

H

Solutie O(N*log²(N))

Pentru fiecare segment vertical (X₁,Yj₁,Ys₁), vom dori sa determinam un segment vertical din stanga sa (X₂,Yj₂,Ys₂), impreuna cu care formeaza o litera H de lungime maxima, in fiecare din urmatoarele 4 cazuri (ce depind de pozitia celui de-al doilea segment fata de primul):

• Yj₁ ≤ Ys₂ ≤ Ys₁ si Yj₂ ≤ Yj₁ : in acest caz, litera H va avea YjosH = Yj₁ si YsusH = Ys₂
• Yj₂ ≤ Yj₁ ≤ Ys₁ ≤ Ys₂ : in acest caz, litera H va avea YjosH = Yj₁ si YsusH = Ys₁
• Yj₁ ≤ Yj₂ ≤ Ys₂ ≤ Ys₁ : in acest caz, litera H va avea YjosH = Yj₂ si YsusH = Ys₂
• Yj₁ ≤ Yj₂ ≤ Ys₁ si Ys₁ ≤ Ys₂ : in acest caz, litera H va avea YjosH = Yj₂ si YsusH = Ys₁

Constatam ca, o data ce am fixat unul din cele 4 cazuri, este foarte clara contributia fiecaruia din cele 2 segmente la lungimea literei H:

• cazul 1: contributia segmentului 1 este L₁ = X₁ - 2 * Yj₁, iar cea a segmentului 2 este W = -X₂ + 2 * Ys₂
• cazul 2: contributia segmentului 1 este L₁ = X₁ + 2 * (Ys₁ - Yj₁), iar cea a segmentului 2 este W = -X₂
• cazul 3: contributia segmentului 1 este L₁ = X₁, iar cea a segmentului 2 este W = -X₂ + 2*(Ys₂-Yj₂)
• cazul 4: contributia segmentului 1 este L₁ = X₁ + 2 * Ys₁, iar cea a segmentului 2 este W = -X₂ - 2 * Yj₂

In aceste conditii, pentru fiecare caz, putem privi fiecare segment ca un punct intr-un alt sistem de coordonate 2D, in care coordonata X corespunde lui Yj, iar coordonata Y corespunde lui Ys. In plus, fiecare punct are asociata o pondere W. Pentru fiecare caz construim cu toate cele N puncte un arbore de intervale 2D, care utilizeaza O(N*logN) memorie. Acest arbore de intervale este, de fapt, un arbore de intervale obisnuit pentru coordonatele X, insa fiecare nod al arborelui mentine un vector cu coordonatele Y ale punctelor ce corespund intervalului nodului respectiv. In plus, pentru fiecare coordonata Y se mentine si ponderea asociata punctului.

Pentru fiecare caz C si fiecare segment vertical, vom dori sa gasim segmenetul vertical din stanga sa cu care poate forma o litera H de lungime maxima. Acest segment corespunde unui punct ce se afla intr-un dreptunghi ce corespunde constrangerilor pentru coordonatele Yj si Ys corespunzatoare cazului C si care are ponderea W maxima. Pentru fiecare caz, interogarile pot fi astfel puse incat dreptunghiul [a,b]x[c,d] in care cautam punctul sa aiba ori coordonata c egala cu - infinit, ori coordonata d egala cu + infinit. In aceste conditii, pentru fiecare nod din arborele de intervale in care se ajunge prin "spargerea" segmentului [a,b], va trebui sa determinam ponderea maxima a unui punct care are coordonata Y printre primele z sau printre ultimele z (unde z este determinat folosind cautare binara in fiecare nod al arborelui de intervale al coordonatelor X in care ajungem). Din acest motiv, putem sa mentinem pentru fiecare nod un vector wmax[z] cu ponderea maxima a unui punct dintre primele z puncte ce corespund intervalului nodului, precum si un vector similar ce corespunde ultimelor z puncte ale intervalului; daca unul dintre capetele c sau d nu era egal cu +/- infinit, atunci trebuia sa folosim RMQ (Range Minimum Query) pentru fiecare nod din arbore.

Observam ca, in modul in care am pus interogarile, nu am specificat nicaieri ca punctul cu pondere maxima sa corespunda unui segment aflat in stanga segmentului pentru care facem interogarea. Totusi, daca punctul cu pondere maxima obtinut nu corespunde unui segment aflat in stanga segmentului curent, atunci vom obtine in mod sigur o litera H de lungime mai mare in momentul in care vom efectua interogarea pentru segmentul corespunzator punctului obtinut (acest lucru se datoreaza modului in care sunt definite ponderile).

Mai trebuie sa avem grija ca, atunci cand realizam interogarea, punctul de pondere maxima sa nu corespunda chiar segmentului pentru care facem interogarea (ceea ce se poate intampla, intrucat nu am impus nici o conditie pentru a evita aceasta situatie). Pentru a evita acest lucru, o posibilitate este sa folosim niste limite ale dreptunghiului de interogare care sa excluda punctele ce corespund unor segmente ce au exact acelasi Yjos si acelasi Ysus ca si segmentul curent. In felul acesta, insa, ajungem sa nu luam in considerare H-uri formate din 2 segmente care au acelasy Yjos si acelasi Ysus (dar coordonate X diferite). Acest caz trebuie tratat separat, printr-o simpla sortare si parcurgere a segmentelor (segmentele avand acelasi Yjos si Ysus aflandu-se unul dupa altul in ordinea sortata).

Complexitatea acestei solutii este O(N*log²N) si foloseste memorie O(N*logN).

Solutie O(N*logN)

Solutia prezentata poate fi optimizata la complexitate O(N*logN), folosind o tehnica standard. Orice query de acest tip corespunzator unui arbore de intervale 2D poate fi redus de la o complexitate O(log²N) la o complexitate O(log N). Practic, se va efectua o cautare binara a coordonatei Y inferioare si superioare numai in cadrul radacinii arborelui de intervale. Apoi, din constructia arborelui, vom memora pentru fiecare punct P al fiecarui nod, 4 pointeri:

• un pointer catre punctul cu cea mai mica coordonata Y mai mare sau egala cu cea a punctului P si care se afla in intervalul de coordonate X al fiului stanga
• un pointer catre punctul cu cea mai mica coordonata Y mai mare sau egala cu cea a punctului P si care se afla in intervalul de coordonate X al fiului dreapta
• un pointer catre punctul cu cea mai mare coordonata Y mai mica sau egala cu cea a punctului P si care se afla in intervalul de coordonate X al fiului stanga
• un pointer catre punctul cu cea mai mare coordonata Y mai mica sau egala cu cea a punctului P si care se afla in intervalul de coordonate X al fiului dreapta

O parte din acesti pointeri pot fi calculati in momentul in care, in faza de constructie a arborelui de intervale 2D, se interclaseaza coordonatele Y corespunzatoare fiului stanga si fiului dreapta. Cealalta parte a pointer-ilor se calculeaza realizand inca 2 parcurgeri ale coordonatelor Y sortate, una de la stanga la dreapta si alta de la dreapta la stanga (in conditiile in care am memorat pentru fiecare coordonata Y de la care din cei doi fii provine).

Unul dintre concurenti a obtinut 100 de puncte folosind o structura de date 2D numita kd-tree, care poate oferi aceleasi operatii ca si un arbore de intervale 2D. Diferenta consta in cantitatea de memorie folosita ($O(N)$, in loc de O(N*logN)), dar si in complexitatea cautarii in interiorul unui dreptunghi ($O(sqrt(N))$, in loc de O(log²N) sau O(logN) cu optimizarea mentionata).

Link-uri utile

• Cautari Ortogonale / infoarena , articol scris de Cosmin Negruseri
• Arbori de intervale / infoarena , articol scris de d-na. prof. Dana Lica
• Range Minimum Query and Lowest Common Ancestor / TopCoder , articol scris de catre Daniel Pasaila
• Orthogonal Range Queries / MIT

Probleme asemanatoare

• Zoo / .campion 2003
• Kth Number / ACM ICPC NEERC Northern Subregion 2004

Permavg

Observam ca, pentru ca media aritmetica a doua numere sa fie un numar intreg, ambele numere trebuie sa aiba aceeasi paritate. Acesta observatie ne-ar putea conduce la ideea de a separa, in cadrul permutarii, numerele pare de numerele impare. Sa presupunem ca vrem sa amplasam la inceputul permutarii toate numerele pare, apoi toate numerele impare. Sa consideram cazul numerelor pare, cazul numerelor impare tratandu-se similar. Avem N/2 numere pare: 2, 4, 6, ... pe care trebuie sa le ordonam in asa fel incat media aritmetica a oricare doua numere sa nu se afle intre ele. Vom renumerota numerele pare ca fiind 1, 2, .., N/2 si vom observa ca acum problema s-a redus la a gasi o permutare de N/2 elemente pentru care media a oricare 2 numere sa nu se afle intre ele (exact problema initiala, dar pentru N injumatatit). Vom aplica in mod recursiv acest algoritm, pana ajungem la permutari cu 1 sau 2 elemente.

Daca aplicam algoritmul direct, obtinem o solutie de tipul Divide et Impera , ce are complexitatea O(N*logN). O imbuntataire a acestei solutii (care nu este necesara pentru a obtine punctajul maxim la problema) consta in observatia ca, de fapt, va trebui sa rezolvam cel mult 2*logN probleme distincte. Sa consideram urmatorul caz (cea mai proasta situatie):

• N=2*k+1: La primul nivel de recursivitate trebuie sa rezolvam problema pentru valorile k si k+1. Avem urmatoarele 2 subcazuri:
  • k=2*p si k+1=2*p+1: Pentru k, va trebui sa rezolvam la nivelul urmator de recursivitate problema pentru valoarea p, iar pentru k+1 va trebui sa rezolvam problema pentru valorile p si p+1 ; asadar, la urmatorul nivel de recursivitate va trebui sa rezolvam problema doar pentru valorile distincte p si p+1.
  • k=2*p-1 si k+1=2*p: Pentru k, va trebui sa rezolvam la nivelul urmator de recursivitate problema pentru valorile p-1 si p, iar pentru k+1 va trebui sa rezolvam problema pentru valoarea p ; asadar, la urmatorul nivel de recursivitate va trebui sa rezolvam problema doar pentru valorile distincte p-1 si p.

In concluzie, la fiecare nivel al recursivitatii, avem de rezolvat, de fapt, doar 2 probleme distincte. Prin urmare, daca memoizam rezultatele pentru fiecare valoare pentru care generam cate o permutare in cadrul algoritmului descris anterior, vom ajunge la o complexitate O(N), in loc de O(N*logN). Aceasta complexitate se obtine din urmatoarea relatie: N + 2 * (N/2 + N/4 + N/8 + ...) = 3*N.

Kboard

Avem urmatoarele cazuri:

• K=1: Daca N este impar, atunci primul jucator castiga; in caz contrar, al doilea jucator castiga.
• K > 1: Pentru K > 1, va trebui sa folosim teoria numerelor Grundy (vezi link1 , link2 , link3 ). Vom calcula pentru fiecare i de la 1 la 3000 o valoarea grundy[i], reprezentand numarul Grundy corespunzator unei table formate din i patratele. Pentru 0 ≤ i ≤ K-1, grundy[i]=0. Pentru i ≥ K, vom genera toate starile in care putem ajunge dupa prima mutare efectuata: S_j (0 ≤ j ≤ i-K) - plasam piesa pe patratelele j+1,..,j+K, impartind tabla in 2 bucati, una de dimensiune j, alta de dimensiune i-j-K; calculam apoi numarul Grundy asociat acestei stari "compuse", ca fiind grundy_compus[S_j] = grundy[j] xor grundy[i-j-K]. Vom calcula apoi primul numar natural (mai mare sau egal cu 0) care nu apare in multimea numerelor grundy_compus[S_j]. Aceasta valoare corespunde numarului grundy[i] (pe care doream sa-l calculam). Pentru o dimensiune i a tablei, jucatorul 1 are strategie sigura de castig daca grundy[i] > 0; in caz contrar, va avea strategie sigura de castig jucatorul 2. Este evident ca, pentru o valoare M, putem calcula numerele Grundy pentru dimensiuni ale tablei de la 1 la M in complexitate O(M²). Dupa ce calculam aceste valori, va trebui sa observam niste reguli pentru a putea rezolva problema pentru limitele date:
  • K > 2 si max{3000, 69*K-19} = 3000: Pentru acest caz nu trebuie sa facem nimic special. Pur si simplu calculam numerele Grundy conform algoritmului descris mai sus si, pentru fiecare test, raspundem in complexitate O(1).
  • K > 2 si max{3000, 69*K-19} = 69*K-19: Dimensiunile tablei de la 1 la K-1 sunt pierzatoare pentru primul jucator, iar dimensiunea K este castigatoare. Vom observa ca, dupa dimensiunea K-1, exista 12 stari pierzatoare pentru primul jucator, de forma a*K+b, care sunt aceleasi indiferent de K (in sensul ca sunt aceleasi constante a si b). Cel mai simplu mod de a observa acest lucru este de a afisa diferenta dintre dimensiunea X a tablei corespunzatoare unei stari pierzatoare si dimensiunea Y a tablei anterioare ce corespunde unei stari pierzatoare. Cele 12 diferente sunt, in ordine: 2*K, 2*K, 4*K-2, 4*K-2, 4*K, 4*K-2, 8*K-2, 4*K-2, 8*K, 8*K-2, 16*K-6, 4*K . Aceasta regula este valida pentru K ≥ 4 (dar noi o vom folosi doar pentru K ≥ 44, deoarece pentru K < 44, ne vom afla in cazul anterior).
  • K=2: In acest caz ne vom uita, din nou, la diferentele dintre doua stari pierzatoare (pentru primul jucator) consecutive. Vom observa ca sirul acestor diferente (considerand prima stare pierzatoare "interesanta" ca fiind K-1) consta dintr-un prefix de lungime 8 (4,4,6,6,4,4,6,4), dupa care sirul devine periodic, cu perioada 5 (4,12,4,4,10).

Probleme asemanatoare

• Obj / Happy Coding 2006
• Pawns / Bursele Agora 2004
• Game / Bursele Agora 2004
• Pietre / infoarena
• Otilia / .campion 2005