Buna ziua,

Trimit rezolvarea problemei 1 de la Olimpiada de Informatica, etapa
pe municipiul Bucuresti, clasa a XI-a, cu scuze pentru cei pe care
nu ii intereseaza.

ENUNT (formalizat): Se da o piramida de cutii: o cutie este
asezata peste doua cutii, care sunt asezate pe trei cutii... care
sunt asezate pe N cutii (deci fiecare cutie se sprijina pe alte
doua). Se mai da un numar S. Limite: N<=16, S<=200000. Se cere sa
se scrie cate un numar natural strict pozitiv in fiecare cutie
astfel incat: 

a) Numarul dintr-o cutie sa fie egal cu suma numerelor din cele
doua cutii de dedesubt;
b) Suma numerelor din toate cutiile sa fie S.

Iesirea: Se va afisa piramida de sus in jos, sau "NU EXISTA
SOLUTIE" daca nu exista solutie (evident :) ).

Exemplu: N=3, S=34. Piramida poate fi:

13
6 7
1 5 2

Complexitate ceruta: O(N*S+N^2).

----------------------------

REZOLVARE: Problema s-a mai dat sub multe forme; multumesc celor
care au avut ideea originala si ii rog sa nu se supere ca le-am
preluat enuntul, incercand sa il fac mai interesant.

Problema se rezolva cu programare dinamica, mai exact seamana cu
problema rucsacului - varianta in care fiecare tip de obiecte este
disponibil in cantitati infinite.

In primul rand, trebuie observat ca fiecare element de pe a N-a
linie a piramidei se regaseste de un anumit numar de ori si mai
sus in piramida. De pilda, 5-ul din exemplu intervine de 5 ori in
toata piramida: o data la baza piramidei, apoi de doua ori pe linia
a doua (si in stanga, si in dreapta), si de inca doua ori in 13-le
din varful piramidei. De asemenea, 2-ul de la baza piramidei
intervine de 3 ori in suma totala (in elementele 2, 7 si 13), si
asa mai departe. 

De aceea, ideea de rezolvare este de a calcula N coeficienti C1,
C2, ..., CN care sa arate de cate ori intervine fiecare element al
bazei in suma totala, apoi sa incercam sa plasam niste valori
naturale nenule S1, S2, ..., SN in cutiile de la baza astfel incat

C1*S1 + ... + CN*SN = S

De exemplu, pentru N=3 avem C1=3, C2=5, C3=3 si deci putem da
solutia S1=1, S2=5, S3=2 pentru ca 3*1 + 5*5 + 3*2 = 34 = S.

A) Sa vedem cum se calculeaza C1...CN. Pai treaba seamana de minune
cu calculul recurent al combinarilor. Sa notam cu D[i,j] numarul de
ori de care al j-lea element de pe a i-a linie a piramidei
contribuie la suma totala. Atunci elementul (i,j) se va propaga si
la locatiile (i-1,j) si (i-1,j-1) si se va scrie o data si la
locatia (i,j). Deci putem scrie

D[i,j] = D[i-1,j] + D[i-1,j-1] + 1,

cu mentiunea ca daca vreo valoare D[i,j] are indicii aiurea (i<0,
j<0 sau j>i) se va considera D[i,j]=0. Atunci C[i]=D[N,i]. Cred ca
nu sunt prea clar; nici nu am cum fiindca mi-e prea somn ca sa fac o
poza explicativa. Cert e ca rezulta exact coeficientii asteptati:

1
2 2
3 5 3
4 9 9 4
5 14 19 14 5
...

si a N-a linie este tocmai vectorul de coeficienti care ne trebuie.

B) Cum se face rucsacul: In primul rand ca trebuie ca Si>0 pentru
orice i, lucru care este cam enervant. De aceea facem substitutia
Ti = Si-1, deci Ti>=0 (poate fi si egal !) si scriem:

C1*T1 + ... + CN*TN = S - (C1 + ... + CN) = (prin notatie) T

Imi permit sa fac observatia ca C1 + ... + CN este suma
coeficientilor de pe linia N si este egala cu 2^(N+1) - N - 2,
ceea ce se poate demonstra prin inductie (dar va asigur ca eu n-am
facut o asemenea demonstratie, ci am observat pur si simplu ca asa
este, cel putin pana la N=16. Cu alte cuvinte, am facut inductia
completa :) ). 

Acum deja totul devine familiar si turuim poezia: Cream un vector X
cu T+1 elemente numerotate de la 0 la T, unde X[k] ne va indica
daca putem cumva obtine suma k si daca da, care e ultimul obiect
folosit. Scopul este sa aflam X[T]. 

Pai, se observa ca suma 0 se poate obtine foarte usor cand
T1=T2=...=TN=0. Pe urma, suma k se poate obtine daca exista vreun
coeficient Ci astfel incat suma k-Ci sa se poata obtine. In acest
caz, X[k] va retine valoarea i (indicele coeficientului Ci).

De exemplu, pentru vechiul nostru exemplu, N=3, S=34, obtinem
T=34-(3+5+3)=23 si C=(3, 5, 3) si spunem asa:

i    | 0 1 2 3 4 5 6 7 8 9 10 ....
X[i] | 0 ? ? 1 ? 2 1 ? 1 1  2 ....

ceea ce vrea sa spuna ca sumele 1, 2, 4 si 7 nu se pot obtine ca o
combinatie liniara de numerele 3, 5 si 3, ca suma 9 se poate obtine
din suma 5 prin folosirea coeficientului C1 etc.

Dupa aceea se parcurge inapoi vectorul X, se afla valorile lui Ti,
se revine la Si=Ti+1 si se genereaza piramida.

Calculul complexitatii: coeficientii se genereaza in O(N^2).
Completarea vectorului X se face in O(N*S), deoarece T are ordinul
de marime al lui S, si pentru fiecare suma cuprinsa intre 0 si T
trebuie sa parcurg toti cei N coeficienti (sau N/2 daca observ ca
vectorul C este palindrom). Reconstituirea solutiei se face in
O(T) in cel mai rau caz. Generarea piramidei se face in O(N^2).

Cam asta e. Felicitari celor trei care au gasit rezolvarea cu
dinamica in timp de concurs - Irina Dumitrescu, Bogdan Batog si
Catalin Drula (precum si altora, in caz ca au mai existat si nu
i-am remarcat).

Catalin

+--------------------------+---------------------------------------+
|  Catalin Andrei Francu   | "War does not determine who's right,  |
| fcatalin@sundy.cs.pub.ro |      war determines who's left"       |
+--------------------------+---------------------------------------+


