Soluţii Summer Challenges 2009, Runda 2

• Lista de probleme
• Biti4
• Padurari
• Centru2
• Simpla

Biti4

Soluţia foloseşte metoda programării dinamice. Pentru început, considerăm un şir binar canonic ca fiind un şir corect şi orice două poziţii consecutive care conţin cifre diferite o schimbare de cifră.

Vom determina succesiv cifrele şirului căutat. Definim cw(a₁a₂..a_m) ca fiind numărul şirurilor corecte care au prefixul a₁a₂..a_m. Prefixul de lungime 0 îl vom nota cu eps. Astfel, modelul soluţiei este următorul:

prefix := eps;
pentru i = 0, N - 1 execută:
    dacă I <= cw(prefix0) atunci:
        prefix := prefix0;
    altfel:
        I -= cw(prefix0);
        prefix := prefix1;
    sfârşit_dacă;
sfârşit_pentru;
return prefix;

Introducem încă o notaţie: cw(a₁..a_m,b_l..b₁), desemnând numărul şirurilor corecte care au prefixul a₁..a_m şi sufixul b_l..b₁. Dacă m + l > n atunci prefixul şi sufixul se suprapun. Astfel, fiecare şir corect care începe cu prefixul a₁..a_m are una din următoarele forme:

• ultimele l cifre ale şirului (0 ≤ l < m) citite de la sfârşit spre început sunt primele l cifre ale şirului, 0 este a (l+1)-a cifră a prefixului, iar 1 a (l+1)-a cifră a sufixului.
• ultimele m cifre ale şirului citite în sens invers sunt primele m cifre ale şirului.

Întrucât, când calculăm valoarea lui cw(prefix) întotdeauna vom extinde prefixul cu cifra 0, putem presupune că a_m = 0. Aceste observaţii ne conduc la formula:

unde [a_l+1 = 0] are valoarea 1 dacă egalitatea are loc şi 0 în caz contrar. Notăm cu k_m numărul schimbările de cifră în şirul a₁a₂..a_m iar cu k_l numărul schimbărilor de cifră în şirul 1a_l..a₁.

În continuare, observăm că cw(a₁..a_m,a_m..a₁) este egal cu numărul şirurilor corecte de lungime n-2m+2 care încep şi se termină cu cifra a_m şi care au cel mult k-2k_m schimbări de cifră. Pe de altă parte, cw(a₁..a_m,1a_l..a₁) este egal cu numărul tuturor şirurilor de lungime n-(m-1)-l care încep cu cifra a_m şi se termină cu cifra 1 şi care au cel mult k-k_m-k_l schimbări de cifră. Pentru a determina aceste valori, calculăm două matrici C şi A, C contorizând şirurile corecte iar A toate şirurile. Matricile sunt 4-dimensionale. reprezintă numărul şirurilor corecte de lungime n, cu cel mult k schimbări de cifră, începând cu cifra b şi terminându-se cu cifra e. se defineşte similar. Ne vom concentra asupra calculării elementelor matricii C. Matricea A se calculează asemănător şi se lasă temă cititorului. Cazurile limită sunt:

• ;
• ;
• ;
• ;

Dacă niciunul din cazurile limită nu are loc, atunci pentru n ≥ 3 şi k ≥ 1 avem:

• ;
• ;
• .

În final, dacă prefixul şi sufixul se suprapun (2m > n sau m+l+1 > n) atunci numărul şirurilor cu prefixul şi sufixul dorite este egal cu 0 sau cu 1, număr ce se poate determina direct.

Complexitatea soluţiei este O(n²).

Padurari

O primă observaţie aproape evidentă este că pădurarii vor alege mereu copaci consecutivi. Pornind de la această observaţie se poate construi un algoritm trivial bazat pe programare dinamică având complexitatea O(N*K) şi care ar fi obţinut 20 de puncte.
Pentru a ajunge la un algoritm eficient, o abordare posibilă este să modelăm problema ca un graf. Nodurile vor fi reprezentate de copaci, iar muchiile de posibilităţile de alegere ale pădurarilor. Astfel, va exista muchie între două noduri dacă şi numai dacă acestea sunt consecutive. Se observa uşor ca acest graf este unul bipartit. Problema se reduce acum la găsirea unui cuplaj de cardinal K si cost minim în graful construit. Daca studiem modul de comportare al algoritmului pentru determinarea cuplajului de cost minim pe acest graf, se observă ca o muchie de întoarcere va fi folosită doar în cazul în care dorim să selectăm ulterior cele două muchii vecine. Folosind această observaţie, putem prevedea comportarea algoritmului în acest pas, înlocuind muchia de întoarcere ce ar trebui introdusă şi cele două muchii vecine, cu o nouă muchie ca in desenul următor:

Acum se poate construi un nou algoritm care selectează la fiecare din cei K pasi muchia minimă din graf si face transformările necesare. Inserările şi ştergerile muchiilor se pot face în timp logaritmic folosind un heap, astfel algoritmul având complexitatea O(K*logN).
Există un caz particular ce trebuie tratat cu atenţie. Când muchia aleasă este prima sau ultima din graf, abordarea de mai sus nu funcţionează. Totuşi, în acest caz este uşor de observat că va fi mereu de preferat să alegem această muchie în locul vecinei, deoarece are costul mai mic şi nu crează restricţii asupra altor muchii din graf.

Centru2

Considerăm intervalele noduri ale unui graf şi vom adăuga muchie între două noduri dacă intervalele corespunzatoare se suprapun. Pe acest graf, ne propunem sa determinăm cea mai mică lexicografic mulţime independentă maximală de vârfuri (maximum independence set sau MIS).
Pentru claritatea explicaţiei vom presupune ca nu există intervale complet incluse unul în celălalt. Algoritmul care tratează şi acest caz urmează aproximativ la fel paşii celui prezentat în continuare.
Sortăm intervalele după capătul din dreapta. Definim D[i] = min{j > i | i si j nu sunt legate printr-o muchie}. Vom construi o subrutina MIS{i,j} pe care o vom utiliza ulterior şi care va determina cardinalul MIS-ului vârfurilor din graf curprinse între i şi j, i ≤ j. Se observă că MIS{i,j} = 1 + max{k | D^k[i] ≤ j}. Vom construi o matrice , cu ajutorul căreia vom determina biţii rezultatului (asemănător cu modul de funcţionare al căutarii binare bazate pe ideea lui Mihai Pătraşcu prezentată în acest articol).
Parcurgem nodurile în ordinea iniţială. Fie i₀ primul nod. Fie i, i+1, ..., j vecinii nodului i₀. Aceştia pot fi determinaţi în O(logN) folosind cautare binară. Nodul i₀ poate face parte din soluţie dacă şi numai dacă MIS{1, i-1} + 1 + MIS{j+1, N} = MIS{1, N}. Această verificare poate fi făcută în complexitate O(logN) folosind subrutina descrisă mai sus. Să presupunem în continuare că nodul i₀ a trecut testul. Luăm apoi nodul i₁, următorul în ordinea iniţială. Dacă i₁ aparţine intervalului [i, j], el nu aparţine soluţiei deoarece ar intra în conflict cu nodul ales precedent. Să presupunem că i₁ apartine intervalului [j+1, N] şi vecinii acestuia sunt p, p+1, ..., q, unde j < p ≤ q ≤ N. Trebuie din nou verificat dacă MIS{j+1, N} = MIS{j+1, p-1} + 1 + MIS{q+1, N}. Este intuitiv că acest algoritm conduce la obţinerea MIS-ului minim lexicografic.
Pentru a realiza operaţiile descrise mai sus in timp logaritmic este nevoie de un arbore de intervale cu ajutorul căruia sa verificăm dacă noile intervale se intersectează cu cele deja existente în soluţie şi un arbore binar echilibrat de căutare (treap, AVL sau set din STL) pentru a localiza intervalele pe care trebuie făcute verificările.

Simpla

Pornim de la observaţia că în intervalul [0, 10ⁿ-1] există exact jumătate numere naturale cu suma cifrelor pară. Rezultă că avem 5 * 10^n-1 numere naturale cu suma cifrelor pară. Pentru a rezolva problema pe intervalul [a, b], vom folosi o funcţie f(x) egală cu numărul numerelor cu suma cifrelor pară din intervalul [0, x]. Astfel, rezultatul va fi f(b) - f(a - 1).

Pentru a calcula valoarea returnată de un f(x), să presupunem că x = x₁x₂..x_m-1x_m. Avem f(x) = x₁ * 5*10^m-2 + x₂ * 5*10^m-3 + .. + x_m-1 * 5 + v. Acest lucru este posibil deoarece pentru un x_i nu are importanţă suma x₁ + .. + x_i-1, întrucât numărul numerelor cu suma cifrelor pară este egal cu al celor cu suma cifrelor impară. Cazul ultimei cifre, se tratează prin a considera toate numerele cuprinse în intervalul [x - x_m, x] care se vor aduna la rezultat dacă au suma cifrelor pară, rezultat reţinut în v în formula de mai sus. Sau mai simplu, f(2*k+1) = k si f(2*k) = f(2*k+1)-(1-S(2*k+1))%2, unde S(x) = suma cifrelor lui x.