Tehnici avansate de programare dinamică

(Categoria Tehnici de programare, autori Catalin Tiseanu, Andrei Homescu)

TODO://ok..to do...dar do mai repede...k e foarte bun articolul si vreau sa citesc si partea cealalta...e pacat sa lasati articolul neterminat asa...vede lumea...bine..e si funny ;)) peace out ;) 

1. Reparat link de la ugly numbers

Plan de atac (probleme-candidat):

1. http://www.main.edu.pl/user.phtml?op=showtask&task=wie&con=PA2009&lang=en (Reducerea complexitatii, transformarea problemei intr-una de construire a unui arbore binar.)

2. http://code.google.com/codejam/contest/dashboard?c=32001#s=p0&a=3 (Boolean tree, programare dinamica simpla pe arbore binar.)

3. http://code.google.com/codejam/contest/dashboard?c=32001#s=p3&a=3 (PermRLE, permutari cu N*2^N)

4. http://code.google.com/codejam/contest/dashboard?c=32010#s=p3&a=3 (problema cu DP pe matrici, aplicam ridicarea la putere pt calcul rapid)

5. http://infoarena.ro/problema/doipatru (joc cu solutie DP, stare in 6 dimensiuni)

Sugestii Silviu

  • poate ca nu trebuie sa spunem tot despre programare dinamica intr-un singur articol; spre exemplu putem facem doua articole: PD basic si PD advanced
  • cred ca era si ceva prin Cartea lui Francu' despre programare dinamica; ar merge incorporat (eventual in pd_basic).

Introducere

Programarea dinamică este o metodă utilă pentru a rezolva probleme care pot fi obţinute prin compunerea a mai multor bucăţi, a căror soluţie poate fi apoi determinată optim. Se bazează în principal pe proprietatea unei probleme de a putea fi rezolvată optim dacă se cunosc soluţii optime la sub-problemele ei.
De menţionat că 'programare' nu se referă aici la scrierea de cod într-un limbaj de programare, ci la 'programare matematica', care constă în optimizarea unei funcţii prin alegerea de valori dintr-o mulţime anume.

Scopul acestui articol nu este să ofere o introducere in programare dinamică (pentru aceasta poate fi consultat excelentul tutorial de pe TopCoder Dynamic Programming : From novice to advanced). În schimb, acest articol îşi propune să ofere nişte 'smenuri' mai avansate de rezolvare a problemelor cu programare dinamică.

Reducerea loop-ului interior

În problemele de programare dinamică de multe ori prima complexitate obţinută nu este optimă. Mai exact, recurenţa obţinută iniţial poate fi îmbunătăţită sau calculată mai rapid. De multe ori, pentru aceasta se optimizeaza loop-ul interior din calculul recurenţei. Acest lucru se poate face bazat fie pe observaţii specifice problemei, fie pe tehnici mai clasice.

Să considerăm următoarea problema:

Problema 1: Drilling (Algorithmic Engagements 2009, Round 3)

Se da un şir de N numere naturale (a1, a2, ..., aN). Se ştie că un prefix al acestui şir (adică o subsecvenţă de la începutul şirului, posibil nulă) este defect. Toate elementele din acel prefix (şi doar din acel prefix) sunt defecte. Se ştie de asemenea că se poate testa orice poziţie i în timp ai pentru a afla dacă este defectă. Să se determine timpul minim în cazul cel mai defavorabil pentru aflarea lungimii maxime a prefixului şirului care este defect.

Exemplu:

Pentru secvenţa de numere (8 24 12 6), răspunsul ar fi 42. Astfel, se testează mai întâi poziţia 2. Dacă nu este defectă, mai rămâne de testat poziţia 1. Altfel, în cel mai rău caz mai trebuie testate poziţiile 3 şi 4, aducând timpul total la 24 + 12 + 6 = 42.

Rezolvare:

O să începem prin a da altă îmbrăcăminte problemei. Astfel, să ne imaginăm că am construi un arbore binar de căutare pe şirul dat, având drept chei poziţiile din şir, şi drept valori auxiliare valorile poziţiilor respective din şir (un nod cu cheia i va avea valoarea auxiliara ai.
Acum, există mulţi arbori binari de căutare posibile pentru şirul iniţial. Totuşi, să presupunem că am construit unul, pe care îl considerăm de acum ca fixat. Atunci, strategia noastra de testare a elementelor din şir se va desfăşura conforma arborelui. Astfel, testăm mai întâi în poziţia din rădăcină. Dacă poziţia respectivă este defectă, ne ducem în fiul drept. Altfel, mergem in fiul stâng. În ambele cazuri se reia procedeul. Căutarea se termină cand nu mai putem merge într-un fiu.

Să observăm că dacă considerăm costul unui drum în arbore de la rădăcină la o frunză ca suma valorilor auxiliare din drumul (unic) respectiv, atunci se observă că costul strategiei bazate pe acest arbore este chiar costul maxim al unui drum ! De acum încolo, vom defini costul unui arbore ca costul maxim al unui drum de la rădăcină la o frunză. Să exemplificăm pe şirul din exemplu:

Fig. 1: În paranteză sunt valorile auxiliare ataşate cheilor

Se observă că costul maxim al unui drum este 42, minim posibil, exact ca răspunsul din exemplu. Deci, am redus problema la construirea unui arbore binar de căutare, care are costul minim.

Acum devine clară o primă soluţie folosind programarea dinamică. Astfel, să presupunem că notăm cu opt[ i ][ j ] costul minim al unui arbore construit pe cheile din [i,j] (prin asta notăm (i, i + 1, ..., j). Fie r[ i ][ j ] poziţia rădăcinii arborelui cu costul minim. În cazul existenţei mai multor rădăcini posibile, se alege cea mai din stânga. Cum am putea construi arborele de cost minim pe cheile [i,j] ştiind răspunsul pentru instanţele mai mici (subsecvenţele de lungime mai mică ca j-i+1 pe [i,j])? (!) Simplu, arborele de cost minim pe [i,j] se obţine alegând drept rădăcină în mod optim o poziţie k, cu $i \le k \le j$, la care se pune ca fiul stâng arborele optim pentru [i, k-1], şi ca fiu drept arborele optim pentru [k+1, j]. Relaţia de recurenţă devine:

opt[ i ][ j ] = \displaystyle\min_{i \le k \le j} \{a_{k} + \max( opt[i][k-1], opt[k+1][j] )\}
r[ i ][ j ] = \displaystyle\arg \min_{i \le k \le j}\{a_{k} + \max (opt[i][k-1], opt[k+1][j] )\}

Avem opt[i][j] = 0, pentru j < i.
Cazurile de bază sunt opt[i][i] = ai si r[i][i] = i.

Se observă că răspunsul problemei se află în opt[1][N].
Astfel, am obţinut o soluţie în timp O(N^3).

Aici trebuie remarcată asemănarea acestei probleme cu cea a determinării arborelui de căutare optim, atunci cand se dau probabilităţile relative de căutare a cheilor. Această problemă se numeşte 'Optimal Binary Search Tree' în literatura de specialitate şi poate fi găsită şi în Introduction to Algorithms. În aceasta problemă, se poate aplica o reducere a complexităţii datorită faptului că $ r[i][j-1] \le r[i][j] \le r[i+1][j] $ pentru a reduce complexitatea la O(N^2). Această proprietate nu se poate aplica din păcate şi în cazul problemei noastre.

Până acum avem următorul pseudocod pentru calculul recurenţei:

Algoritmul este:
    iniţializează opt şi r
    pentru len = 1, N execută
        pentru i = 1, N - len + 1 execută
            j = i + len - 1;
            opt[i][j] = inf;
            pentru k = i, j execută
                dacă opt[i][j] < a[k] + max(opt[i][k-1], opt[k+1][j]) atunci
                    opt[i][j] = a[k] + max(opt[i][k-1], opt[k+1][j]);
                    r[i][j] = k;
            sfârşit_pentru;
       sfârşit_pentru;
    sfârşit_pentru;

    return opt[1][N];
Sfârşit.

Acum ca să obţinem o complexitate mai bună, ţinând cont şi de numele capitolului, vom încerca să reducem complexitatea loop-ului interior (cel după k).
Să ne uităm mai atent la acest loop.

Fie un interval [i,j] fixat. Acum, opt[i][j] < opt[i][j'], pentru orice j < j'. Similar, opt[i][j] < opt[i'][j], pentru orice i' < i.
Atunci, există un indice k, $i \le k \le j$ astfel încât max(opt[i][o-1], opt[o+1][j]) = opt[o+1][j], pentru orice $i \le o \le k$, şi max(opt[i][o-1], opt[o+1][j]) = opt[i][o-1] pentru orice $k \le o \le j$. După cum ştim, trebuie să aflăm \displaystyle\min_{i \le k \le j} \{a_{k} + \max( opt[i][k-1], opt[k+1][j] )\} . Să definim acum 3 matrici auxiliare:

to_left[ i ][ j ] = ai + opt[ i + 1 ][ j ]
to_right[ i ][ j ] = aj + opt[ i ][ j - 1 ]
inter[ i ][ j ] = \displaystyle\arg \max_{i \le k \le j}\{opt[i][k-1] \le opt[k+1][j]\}

Se observă că inter[i][j] nu reprezintă altceva decât indicele k tratat in paragraful precedent.
De asemenea, inter poate fi calculată în O(N^2) observând o proprietate simplă: $ inter[i][j-1] \le inter[i][j] \le inter[i+1][j] $. Aceasta reiese imediat din monotonia lui opt discutată mai sus. Pseudocodul pentru calculul lui inter este:

Algoritmul este:
    iniţializează opt, inter şi r
    pentru len = 1, N execută
        pentru i = 1, N - len + 1 execută
            j = i + len - 1;
            calculează opt[i][j]
            pentru k = inter[i][j-1], inter[i+1][j] execută
                dacă opt[i][k-1] <= opt[k+1][j] atunci
                    inter[i][j] = k;
            sfârşit_pentru;
       sfârşit_pentru;
    sfârşit_pentru;
Sfârşit.

De menţionat că trebuie avut grijă la cazul când len este mai mic ca 3. Pseudocodul prezentat mai sus este orientativ.
Să vedem acum de ce această modalitate de calcul a lui inter duce la o complexitate de O(N^2).

Alternativ, se poate căuta binar inter[i][j] pentru orice [i,j].

Acum vine ideea decisivă pentru a reduce complexitatea loop-ului: pentru a afla opt[i][j], este suficient să aflăm minimul dintre 2 valori:

  • \displaystyle\min_{i \le k \le inter[i][j]} \{$to\_left[k][j]$\} şi
  • \displaystyle\min_{inter[i][j] < k \le j } \{$to\_right[i][k]$\}

Mai exact,

opt[ i ][ j ] =  \min( \displaystyle\min_{i \le k \le inter[i][j]} \{$to\_left[k][j]$\},
                              \displaystyle\min_{inter[i][j] < k \le j } \{$to\_right[i][k]$\} )

Diferenţa faţă de prima recurentă este evidentă: acum trebuie să aflăm minimul pe un interval de linii, în cazul to_left, şi minimul pe un interval de coloane, în cazul to_right. Atât aflarea mnimului pe un interval, cât şi update-ul acestei valori se poate face în O(logN), folosind arbori de intervale.

Astfel, am redus complexitatea loopului interior de la O(N) la O(logN).

Programare dinamică folosind măşti de biţi şi codificări k-are

Unele probleme de programare dinamica au drept componentă a stării unei subprobleme o mulţime de elemente care fac parte din subproblemă. Astfel, subproblema nu este o reducere a problemei iniţiale la un subset continuu de elemente (1..i sau i..j) ci la un subset oarecare. În acest caz, codificăm submulţimea curentă în stare, ca vector sau ca număr întreg. Dacă dimensiunea submulţimii este suficient de mic putem folosi un întreg pentru a codifica această informaţie astfel:

Fie mulţimea A = { x1, x2, ... xn }.
Atunci masca de biţi a unei partitii a lui A, MASK, va avea bitul i egal cu 1 dacă şi numai dacă xi apartine partitiei. Desigur, această reprezentare duce la o complexitate direct proporţională cu 2 card(A). Putem intui dacă trebuie să folosim o astfel de rezolvare din limitele valorilor de intrare; pentru N cu valori cuprinse între 10-20, deducem că trebuie să căutăm o astfel de soluţie.

Pentru multe probleme, fiecare element poate face parte din subproblemă în mai mult de 2 feluri. De exemplu, dacă starea reprezintă o linie de maxim K elemente dintr-o matrice iar fiecare element de pe linie poate avea valorile 0, 1 sau 2 atunci există 3^K variante distincte posibile pentru o astfel de linie. Un alt exemplu este o problemă de optimizare în care fiecare element (participant) se poate afla în una din câteva stări (dacă N persoane trebuie să treacă un pod peste un râu, cele 3 stări pot fi: pe malul stâng, pe pod şi pe malul drept).

Problema 1: Be a Smart Raftsman (SGU)

Sunteţi membri ai unui echipaj de rafting care constă din N ≤ 10 participanţi. Puteţi naviga pe râu, şi scopul vostru este să treceţi de M ≤ 1000 curenţi consecutivi şi să ajungi de la punctul de început la punctul de sfârşit în timp minim. Cel de-al i-lea curent se caracterizează prin greutatea critică ci, iar al j-lea participant este caracterizat greutatea sa wj. În cazul în care pluta trece prin al i-lea curent cu oameni la bord cu greutatea totală mai mare de ci, ea se răstoarnă. Această parte a rafting-ului este cea mai interesantă, dar este nevoie de timp suplimentar pentru a te urca pe plută după răsturnare. Deci, uneori este mai bine să se urce un grup de oameni cu greutate totală care nu depăşeşte greutatea critică a plutei, în timp ce restul parcurg distanţa pe jos.
Mai formal, vom considera M + 1 puncte P0, P1 ,..., PM, în cazul în care P0 este începutul şi PM este punctul final. Fiecare dintre punctele intermediare Pi (1 ≤ i ≤ M-1) este situat între i-lea şi (i + 1)-lea curent. Dacă pluta se răstoarnă, sunt necesare Di minute pentru a ajunge de la Pi-1 la Pi, altfel sunt necesare di minute. Cel de-al j-lea participant poate merge pe jos de la Pi-1 la Pi în tj minute, iar pentru a se urca sau a coborî din plută are nevoie de sj minute. Înainte de fiecare curent, grupul vostru este împărţit în două părţi. Prima parte trece prin curent cu pluta, iar a doua parte merge pe mal spre următorul punct. Cei care ajung primii îi aşteaptă pe toţi ceilalţi. Apoi, unii participanţi care sunt pe plută se pot da jos, în timp ce alţi participanti care sunt pe mal se pot urca pe plută. Această activitate începe când ajung pluta şi toţi cei de pe mal la punctul stabilit. Timpul total necesar pentru această acţiune este egal cu suma valorilor sj pentru toate persoanele care schimbă locul (persoanele urcă şi coboară pe rând). Nimeni nu poate începe deplasarea la următorul punct, până când nu s-au mutat toţi membrii.
începeţi de la punctul de P0 cu tot grupul pe mal şi trebuie să terminaţi la punctul PM cu toţi participanţii şi pluta pe mal. Nu aveţi voie să părăsiţi pluta la început sau într-un un punct intermediar şi să mergeţi pe jos spre linia de sosire fără ea. Aveţi posibilitatea să urcaţi tot grupul de salvare în plută, dar nu puteţi lăsa pluta goală în timpul călătoriei printr-un curent.
Sarcina voastră este să calculaţi timpul minim necesar pentru a ajunge la linia de sosire.

Rezolvare:

Din enunţ intuim că o componentă a stării trebuie să fie submulţimea participanţilor aflaţi în plută în punctul curent, intuiţie confirmată de numărul mic al participanţilor (N ≤ 10). Există 210 astfel de variante, din care vom exclude varianta în care pluta este goală. O stare a problemei, reprezentănd soluţia unei subprobleme, va fi alcătuită din poziţia curentă a plutei (punctul Pi unde se află) şi submulţimea oamenilor care se află în plută. Observăm că de la punctul precedent pluta a traversat curentul, au urcat nişte oameni apoi au coborât alţii; aceşti paşi contribuie la timpul total şi reprezintă 2 părţi ale recurenţei soluţiei. Dacă notăm cu Tm[i][S] timpul minim necesar pentru a ajunge în punctul i cu submulţimea S a oamenilor din plută, putem descrie problema prin relaţiile:

 $T_m[0][0] = 0$
 $T_m[0][S] = T_u[0][S], \forall S \neq 0$
 $T_m[i][S] = \min_{S' \neq \emptyset} \{T_m[i-1][S'] + T_t[i][S'] + T_u[S'][S] + T_c[S'][S]\}, \forall 1 \le i \le M$

unde Tu[S'][S] este timpul necesar pentru urcarea participanţilor care se găsesc în mulţimea S dar nu fac parte din mulţimea S' (aceşti participanţi alcătuiesc mulţimea Su), Tc[S'][S] este timpul necesar pentru coborârea participanţilor din plută (participanţii din mulţimea Sc), iar Tt[i][S] este timpul necesar traversării curentului de la punctul i-1 la punctul i dacă în plută se află participanţii din S. Formulele pentru valorile Tu, Tc şi Tt sunt:

 $T_u[S_1][S_2] = \sum_{i \in S_2 - S_1}{s_i} = \sum_{i \in S_u}{s_i}$
 $T_c[S_1][S_2] = \sum_{i \in S_1 - S_2}{s_i} = \sum_{i \in S_c}{s_i}$
 $T_t[i][S] = \left\{ 
\begin{array}{l l}
  D_i & \quad \sum_{j \in S}{w_j} > c_i\
  d_i & \quad \sum_{j \in S}{w_j} \le c_i\ 
\end{array} \right. $

Calcularea directă a soluţiei pe baza recurenţelor de mai sus are complexitatea O(M*N*2N + M*2N*2N). Primul termen al complexităţii este dat de calcularea valorilor Tt, iar al doilea de calcularea matricii Tm.

Valoarea rezultatului nu depinde de ordinea în care urcă şi coboară participanţii din plută, deci o putem alege noi. Dacă aranjăm ordinea în doi paşi astfel încât în primul pas doar să urce, apoi în al doilea pas doar să coboare, vom obţine o îmbunătăţire semnificativă a timpului de execuţie. Se observă că dacă am efectua doar adăugări de elemente (daca în plută s-ar putea doar urca persoane, fără să poată coborî), atunci  $S' \in S$ şi deci reprezentarea în cod binar a mulţimii S' ar avea o valoare mai mică decât reprezentarea binară a mulţimii S. Dacă ar avea voie doar să coboare persoane, relaţia ar fi inversă. De aceea, vom ordona operaţiile de urcare şi coborâre astfel încât să aibă loc întâi toate urcările (astfel încât să putem parcurge crescător valorile binare ale mulţimilor) apoi toate coborârile (astfel încât să putem efectua a doua parcurgere, în ordine descrescătoare). Introducem matricea auxiliară Tum[i][S] care reprezintă timpul minim necesar la care se poate afla pluta în punctul i cu mulţimea S de oameni, dacă după ultima traversare nu a coborât încă nici o persoană. Starea S a fost obţinută prin una sau mai multe urcări de persoane în plută sau direct prin traversarea curentului. Recurenţele pentru Tum[i][S] sunt:

 $T_{um}[i][S] = \min \left(T_m[i-1][S] + T_t[i][S], \min_{j \in S}\{T_{um}[i][S - j] + s_j\} \right)
 $T_m[i][S] = \min \left(T_{um}[i][S], \min_{j \not\in S}\{T_m[i][S \cup j] + s_j\} \right)

Am eliminat calcularea matricilor Tu, Tc. Toate matricile rămase au dimensiunea Mx2N iar calcularea fiecărui element necesită un timp O(N), deci soluţia astfel obţinută are complexitatea O(M*N*2N).

iniţializează toate Tm[0];
    pentru i = 1, M execută
        calculează toate Tt[i];
        pentru fiecare S în ordine crescătoare a reprezentării binare execută
            Tum[i][S] = Tm[i-1][S] + Tt[i][S];
            pentru fiecare j din S execută
                Tum[i][S] = min(Tum[i][S], Tum[i][S - j] + s[j]);
            sfârşit pentru;
        sfârşit pentru;
        pentru fiecare S în ordine descrescătoare a reprezentării binare execută
            Tm[i][S] = Tum[i][S];
            pentru fiecare j care nu există în S execută
                Tm[i][S] = min(Tm[i][S], Tm[i][S + j] + s[j]);
            sfârşit pentru;
        sfârşit pentru;
    sfârşit pentru;
    returnează Tm[M][0];

Mai există două optimizări de spaţiu pe care le putem efectua în soluţia prezentată. Putem elimina matricea Tum, calculând toate valorile direct pe matricea Tm, deoarece aceasta va fi parcursă în ambii paşi în câte o singură direcţie. A doua optimizare se bazează pe observaţia că nu avem niciodată nevoie de alte linii în afară de ultimele 2 (i si i-1), deci putem înlocui matricea cu 2 vectori de dimensiune 2N. Valorile Tt pot fi calculate în cadrul primei bucle, reducând astfel spaţiul necesar soluţiei la O(2N).

Programare dinamica pe mai multe dimensiuni

Unele probleme nu pot fi împărţite în subprobleme doar după o submulţime a datelor de intrare ale problemei curente, ci trebuie adăugate criterii suplimentare. De multe ori, aceste valori sunt similare sumei din problema rucsacului, dar calculele se fac pe 2 sau chiar mai multe dimensiuni, obţinând o descriere destul de complexă a unei subprobleme. De exemplu, o subproblemă poate fi reprezentată printr-un vector de valori de dimensiuni variate.

Problema 1: Ugly numbers (Google Code Jam 2008, Round 1C)

Un număr se numeşte urât dacă este divizibil prin oricare dintre numerele prime de o singură cifră, mai exact 2, 3, 5, 7. Se dă un şir de N cifre. Între fiecare 2 cifre consecutive se poate insera unul dintre semnele + sau -. Dacă nu se inserează un semn, cele 2 cifre sunt concatentate astfel încât să se obţină un număr. Pentru un şir dat de cifre si o variantă de a adăuga semne, prin evaluarea expresiei matematice obţinute prin inserarea semnelor se obţine un număr, numit numărul generat. Să se calculeze câte dintre cele 3N-1 variante de a insera semnele generează numere urâte.

Exemplu:

Pentru cifrele 123456, expresia 1+234-5+6 = 236 care este număr urât, iar 123+4-56 = 71 nu este număr urât.

Rezolvare:

Observăm că un număr este urât dacă dă cel puţin o dată restul 0 la împărţirea la numerele 2, 3, 5, 7. O abordare a problemei este parcurgerea tuturor variantelor de inserare şi calcularea celor 4 resturi, verificând dacă cel puţin unul este 0.
Vom folosi aritmetica modulară pentru a obţine o soluţie mai eficientă a problemei. Vom împărţi cele 3N-1 variante în clase, fiecare clasă reprezentând toate numerele care dau resturile (r2, r3, r5, r7) la împărţirea la cele 4 numere. Calculând pentru fiecare clasă numărul de numere generate, rezultatul final va fi suma valorilor calculate pentru toate clasele pentru care cel puţin un rest este egal cu 0. Intuim că putem utiliza clasele de resturi într-o soluţie cu programare dinamică.
Vom utiliza şirul auxiliar V[i][j] reprezentând numărul format prin concatenarea cifrelor de pe poziţiile consecutive i, i+1, ..., j din şirul dat, fără inserarea unor semne între cifre. De exemplu, V[2][4] = 234. Dacă notăm cu C[i][r2][r3][r5][r7] numărul de variante formate cu primele i cifre pentru care clasa de resturi este (r2, r3, r5, r7). Observăm că orice astfel de variantă se obţine dintr-o variantă cu j < i cifre după care adăugam + sau - apoi concatenăm restul cifrelor până la i fără semne. Dacă resturile pentru varianta cu j cifre erau (r2, r3, r5, r7) atunci resturile pentru varianta nouă (r'2, r'3, r'5, r'7) sunt:
 $r_2' = (r_2 +/- V[j+1][i])\% 2$
 $r_3' = (r_3 +/- V[j+1][i])\% 3$
 $r_5' = (r_5 +/- V[j+1][i])\% 5$
 $r_7' = (r_7 +/- V[j+1][i])\% 7$
Atunci numărul total de variante cu i cifre este suma după toate valorile j ale numerelor de variante cu j cifre:
 $C[i][r_2'][r_3'][r_5'][r_7'] = \sum_{j<i} C[j][r_2][r_3][r_5][r_7]$

pentru i = 1, N execută
        V[i][i] = A[i]
        pentru j = i + 1, N execută
            V[i][j] = V[i][j - 1] + A[i];
        sfârşit pentru;
    sfârşit pentru;

    C[0][0][0][0][0] = 1;
    S = 0;
    pentru i = 1, N execută
        pentru r_2 = 0, 1 execută
            pentru r_3 = 0, 2 execută
                pentru r_5 = 0, 4 execută
                    pentru r_7 = 0, 6 execută
                        C[i][r_2][r_3][r_5][r_7] = 0;
                        pentru j = 0, i - 1 execută
                            C[i][r_2][r_3][r_5][r_7] += C[j][(r_2 + 2 - V[j+1][i])%2)][(r_3 + 3 - V[j+1][i])%3)]
                                                            [(r_5 + 5 - V[j+1][i])%5)][(r_7 + 7 - V[j+1][i])%7)];
                            C[i][r_2][r_3][r_5][r_7] += C[j][(r_2 + V[j+1][i])%2)][(r_3 + V[j+1][i])%3)]
                                                            [(r_5 + V[j+1][i])%5)][(r_7 + V[j+1][i])%7)];
                        sfârşit pentru;

                        dacă i == N şi (r_2 == 0 sau r_3 == 0 sau r_5 == 0 sau r_7 == 0)
                            S += C[i][r_2][r_3][r_5][r_7]
                        sfârşit pentru;
                    sfârşit pentru;
                sfârşit pentru;
            sfârşit pentru;
        sfârşit pentru;
    sfârşit pentru;
    returnează S;

O problemă în abordarea precedentă este calcularea matricii V, ale cărei valori devin foarte mari şi ies din precizia tipurilor de date disponibile. O soluţie posibilă este calcularea câte unei matrici de sume modulo R pentru fiecare rest R, adica a 4 matrici V2, V3, V5 si V7 ale resturilor împărţirii valorilor lui V la cele 4 numere prime. Folosind aritmetica modulară, aceste matrici pot fi calculate direct, fără a calcula V. Altă variantă este utilizarea teoremei chineze a resturilor, prin care un sistem de ecuaţii modulo câteva numere prime între ele poate fi redus la o ecuaţie modulo produsul numerelor date. În cazul nostru, numerele sunt prime, deci putem aplica teorema. Astfel, putem reduce problema resturilor împărţirii la (2, 3, 5, 7) la problema restului împărţirii la 2*3*5*7=210, deci fiecare clasa (r2, r3, r5, r7) se reduce la un rest R < 210. Modificăm pseudocodul astfel:

pentru i = 1, N execută
        V[i][i] = A[i] % 210
        pentru j = i + 1, N execută
            V[i][j] = (V[i][j - 1] + A[i]) % 210;
        sfârşit pentru;
    sfârşit pentru;

    C[0][0] = 1;
    S = 0;
    pentru i = 1, N execută
        pentru r = 0, 209 execută
            C[i][r] = 0;
            pentru j = 0, i - 1 execută
                C[i][r] += C[j][(r + 210 - V[j+1][i]) % 210];
                C[i][r] += C[j][(r + V[j+1][i]) % 210];
            sfârşit pentru;

            dacă i == N şi (r % 2 == 0 sau r % 3 == 0 sau r % 5 == 0 sau r % 7 == 0)
                S += C[i][r];
            sfârşit pentru;
        sfârşit pentru;
    sfârşit pentru;
    returnează S;

Problema 2: Doipatru

Membrii Lotului Naţional de Informatică sunt foarte mândri de noul joc inventat de ei, pe care l-au denumit asemănător cu o problemă de la Olimpiada Internaţională de Informatică din anul 2001, care le-a plăcut foarte mult. Astfel, jocul se numeşte DoiPatru.
Pentru acest joc se folosesc 3 ≤ N ≤ 30 grămezi, fiecare conţinând cel puţin 0 şi cel mult 4 bile. Numărul total de bile din toate grămezile este 2*N. Doi jucători mută alternativ. Atunci când ii vine rândul, fiecare jucător este obligat să efectueze o mutare validă.
O mutare validă constă din alegerea a două grămezi, dintre care prima grămadă are mai multe bile decât cea de a doua. Jucătorul ia o bilă din prima grămadă şi o mută în cealaltă. Mutarea se consideră validă, doar dacă numărul de bile rezultat în a doua grămadă după mutarea bilei nu este mai mare decât numărul de bile rămas în prima grămadă.
Jocul se termină atunci când nu mai poate fi efectuată nici o mutare validă (dacă vă gândiţi puţin, veţi constata că acest lucru se întâmplă atunci când fiecare grămadă conţine două bile).
Câştigătorul jocului este desemnat cel care deţine mai multe grămezi la sfârşitul jocului. Bineînţeles, dacă cei doi jucători deţin un număr egal de grămezi, jocul se consideră a fi remiză.
Un jucător deţine o grămadă dacă grămada are două bile, iar acest număr (de două bile) a rezultat în urma unei mutări efectuate de jucătorul respectiv. De exemplu, dacă un jucător alege o grămadă cu 4 bile şi una cu o bilă, în urma efectuării mutării, el va deţine cea de-a doua grămadă (care va avea două bile), dar prima nu va aparţine deocamdată nici unuia dintre jucători. Dacă alege o grămadă cu 3 bile şi una cu 0 bile, jucătorul va deveni proprietarul primei grămezi, deoarece, în urma mutării efectuate, grămada respectivă va rămâne cu două bile. În cazul în care alege o grămadă cu 3 bile şi una cu o bilă, după efectuarea mutării, el va deţine ambele grămezi (amândouă au acum doua bile).
Dacă un jucător este proprietarul unei grămezi la un moment dat în timpul jocului, nu înseamnă că această grămadă va rămâne în posesia lui până la sfârşit. De exemplu, să presupunem că jucătorul 1 deţine o grămadă cu două bile şi este rândul jucătorului 2 să mute. Dacă acesta alege o grămadă cu 4 bile şi grămada cu două bile ce aparţine jucătorului 1, după efectuarea mutării, ambele grămezi vor avea 3 bile, iar numărul de grămezi aflate în posesia jucătorului 1 va scădea cu 1 (grămada deţinută de el anterior nu mai aparţine nici unuia din cei doi jucători, căci nu mai are doua bile).
Dacă la începutul jocului există unele grămezi având două bile, acestea sunt distribuite în mod egal celor doi jucători. Dacă numărul de grămezi cu două bile este impar, atunci jucătorul 2 va primi cu o grămadă mai mult decât jucatorul 1. Jucătorul 1 este cel care efectuează prima mutare.
Scrieţi un program care, pentru un N dat şi un set de configuraţii iniţiale ale jocului cu N grămezi, decide rezultatul fiecărei configuraţii de joc.

Rezolvare:

Începem rezolvarea cu observaţia că există 5 tipuri de grămezi (0, 1, 2, 3 şi 4 bile), dar pentru fiecare grămadă de 2 bile aparţine doar unuia dintre jucători, informaţie esenţială pentru stabilirea câştigătorului. Vom separa deci toate grămezile de 2 bile în 2 categorii: 2A care reprezintă grămezile de 2 bile deţinute de primul jucător şi 2B care sunt grămezile de 2 bile deţinute de al doilea jucător. Orice moment al jocului poate fi reprezentat identificând jucătorul care urmează la mutare şi numărul de bile din fiecare dintre cele N grămezi. O variantă alternativă este de a reprezenta numerele de grămezi din fiecare tip, starea fiind reprezentată prin valorile (J, n0, n1, n2A, n2B, n3, n4), unde nk reprezintă numărul de grămezi care au k bile (cu excepţiile 2A şi 2B, descrise înainte).
Vom nota prin R[J, n0, n1, n2A, n2B, n3, n4] cel mai bun rezultat pe care îl poate obţine jucătorul care urmează (J). Valorile posibile ale rezultatului vor fi alese ca numere întregi crescătoare, astfel: 0 dacă din configuraţia curentă jucătorul nu are nici o şansă să câştige, 1 dacă jucătorul poate obţine o remiză şi 2 dacă jucătorul are o strategie sigură de câştig. Fiecare jucător va alege mutarea potrivită astfel încât să maximizeze valoarea R, care este în acelaşi timp rezultatul cel mai prost pentru celălalt jucător. Vom nota jucătorii prin 0 şi 1 şi putem calcula valoarea optimă pentru R astfel:

 $R[J, n_0, n_1, n_{2A}, n_{2B}, n_3, n_4] = 2 - \min\{R[\(1 - J\), n_0', n_1', n_{2A}', n_{2B}', n_3', n_4'] \}$ dacă (n'0, n'1, n'2A, n'2B, n'3, n'4) reprezintă o stare accesibilă din starea curentă printr-o singură mutare. Observăm că rezultatul este cu atât mai bun pentru unul dintre jucători cu cât este mai prost pentru celălalt, deci rezultatele sunt invers proporţionale, 2 pentru J reprezentănd 0 pentru jucătorul 1 - J. Fiecare jucător alege mutarea care îi va obţine rezultatul maxim, acesta fiind corespunzător rezultatului defavorabil (de valoare minimă) pentru celălalt.

Stările pentru care nu mai există decât grămezi de tipuri 2A şi 2B sunt, conform enunţului, stări finale.
 $R[J, 0, 0, n_{2A}, n_{2B}, 0, 0] = \left\{ 
\begin{array}{l l}
  0 & \quad J = 0, n_{2A} < n_{2B}\
  0 & \quad J = 1, n_{2A} > n_{2B}\ 
  1 & \quad n_{2A} = n_{2B}\
  2 & \quad J = 0, n_{2A} > n_{2B}\ 
  2 & \quad J = 1, n_{2A} < n_{2B}\
\end{array} \right. $

Notând cu S tuplul distribuţiei bilelor în grămezi (J, n0, n1, n2A, n2B, n3, n4) atunci vom folosi o notaţie echivalentă dar mai scurtă, R[J, S]. Vom iniţializa toate valorile din acest tablou multidimensional la -1 şi apoi vom calcula recursiv valorile, obţinând o complexitate polinomială prin memoizare.

calculR(J, S)
  dacă R[J, S] != -1 atunci
    returnează R[J, S];
  dacă S e stare finală
    returnează 0, 1 sau 2 în funcţie de câştigător;

  R[J, S] = 0;
  pentru toate stările S' în care se poate ajunge din S printr-o mutare
    R[J, S] = max(R[J, S], 2 - calculR(1 - J, S'));
  sfârşit pentru;
  returnează R[J, S];

La prima vedere, numărul stărilor este 2 * (2N)6 = 2 * 606 = 93,312 * 109, deci numărul stărilor este prea mare pentru a intra în limite rezonabile de spaţiu şi timp. Observăm totuşi că toate stările îndeplinesc condiţia n0 + n1 + n2A + n2B + n3 + n4 = N. Numărul total al stărilor este numărul tuplurilor care îndeplinesc egalitatea şi condiţiile nk ≥ 0. Vom numerota cele 6 tipuri de grămezi prin numere de la 0 la 5. Vom calcula valorile NS[g, b, v] care reprezintă numărul de variante de a grupa b bile în g grămezi, astfel încât cea mai mică grămadă să aibă cel puţin mărimea tipului de indice 0 ≤ v ≤ 5. Notăm cu D şirul dimensiunilor tipurilor, (0, 1, 2, 2, 3, 4) şi observăm că o stare descrisă prin (g, b, v) ori are o grămadă de dimensiune Dv ori toate grămezile sunt mai mari decât această dimensiune. Atunci recurenţa de calcul pentru NS este: NS[g, b, v] = NS[g, b, v + 1] + NS[g - 1, b - Dv, v] cu cazul particular NS[0, 0, 5] = 1. Numărul total de stări este valoarea NS[N, 2*N, 0]. Pentru valoarea maximă a lui N din enunţ, am obţinut NS(30) = NS[30, 60, 0] = 8266. Rezultă deci că numărul total real al stărilor este relativ mic, iar soluţia noastră se încadrează în limitele de timp şi spaţiu date.

Pentru o stare S dată, numărul stărilor posibile S' în care putem ajunge este foarte mic. În cel mai rău caz, perechile de grămezi care reprezintă mutarea din pasul curent sunt din mulţimea {(0, 2A), (0, 2B), (0, 3), (0, 4), (1, 3), (1, 4), (2A, 4), (2B, 4)}, deci un jucător are maxim 8 mutări posibile de efectuat. După ce am ales tipurile de grămezi pe care efectuăm mutarea, este irelevantă alegerea grămezilor cu dimensiunile date, deoarece toate alegerile duc la aceeaşi stare următoare.

Un mod de a stoca tabloul R astfel încât spaţiul necesar să fie minim este folosirea unui dicţionar care să stocheze valorile R[J, n0, n1, n2A, n2B, n3, n4] pentru toate stările valide, folosind astfel doar O(NS(N)) spaţiu. Dicţionarul poate fi implementat printr-o tabelă de dispersie sau arbori binari de căutare, în C++ folosind chiar map sau hash_map din STL. Altă opţiune este codificarea fiecărei stări S printr-un număr întreg cuprins între 1 şi NS(N), caz în care tabloul R poate fi stocat într-o matrice de dimensiune 2xNS(N). Asocierea dintre descrierea unei stări (numărul de grămezi de fiecare tip) şi numărul său de ordine poate fi precalculată şi stocată într-un dicţionar sau poate fi calculată în O(N) cu ajutorul unor formule. În primul caz, vom genera prin backtracking toate variantele posibile de stări într-o ordine oarecare şi vom aloca fiecărei stări câte un număr, stocând izomorfismul într-un dicţionar.

Varianta mai complexă, dar mai elegantă presupune stabilirea unei ordini fixe a stărilor şi apoi folosirea unor tehnici combinatoriale pentru a calcula numărul corespunzător unei stări sau starea corespunzătoare unui număr. Vom defini mai formal o stare ca un 6-tuplu (n0, n1, n2A, n2B, n3, n4) şi vom ordona toate stările lexicografic (stările sunt ordonate după n0; în caz de egalitate, sortarea se face după n1 ş.a.m.d.). Atunci numărul de ordine al unei stări calculat de formula de mai sus este numărul de stări care au o valoare mai mică pentru n0 plus numărul de stări care au aceeaşi valoare pentru n0 dar o valoare mai mică pentru n1 ş.a.m.d.

IS = 1;
  G = N;
  B = 2 * N;
  pentru k = 0, 4 execută
    dacă n[k] > 0 atunci
       pentru i = 1, n[k] execută
         IS = IS + S[G][B][k + 1];
         G = G - 1;
         B = B - D[k];
       sfârşit pentru;
  sfârşit pentru;
  returnează IS;

Operaţia inversă calculează o stare S pe baza valorii I(S) a indicelui stării.

G = N;
  B = 2 * N;
  pentru k = 0, 4 execută
    n[k] = 0;
    cât timp IS > S[G][B][k + 1] execută
      IS = IS - S[G][B][k + 1];
      G = G - 1;
      B = B - D[k];
      n[k] = n[k] + 1;
    sfârşit cât timp;
  sfârşit pentru;
  n[5] = G;
  returnează n;

Aceşti algoritmi pot fi integraţi în funcţia recursivă de calcul a matricii R.

To be continued ...