Solutii Runda 1

Imagine

Observam ca fiecare din operatiile S D O V nu face decat sa permute intre ele cele 4 cadrane. De exemplu initial cadranele se afiseaza in ordinea 1,2,3,4 iar dupa o operatie O vor trebui afisate 3,4,1,2, apoi dupa aplicarea unei operatii V va trebui afisat 4,3,2,1. Pentru operatiile N va trebui sa retinem doar paritatea si in cazul in care numarul acestor operatii este impar va trebui sa afisam n in loc de a si invers. De aceea nu trebuie decat sa retinem in ce ordine vom prezenta cadranele si daca acestea vor fi sau nu negate.

Problema care se ridica este lipsa memoriei. Vom reprezenta imagina ca un arbore in care fiecare nod fie este frunza fie are 4 fii(cate unul pentru fiecare cadran). O parcurgere a arborelui in care fii oricarui nod sunt parcursi in ordinea permutarii noastre va fi exact codificarea cautata. Obervam ca nu putem avea mai mult de N/5 nodui interne deci maxim 200.000. Pentru fiecare nod vom retine primul fiul si fratele nodului curent. Din felul in care vom construi arborele (cu ajutorul unei stive) se vede ca primul fiu al unui nod in cazul in care exista va fi exact nodul curent + 1 de aceea nu va mai fi necesara si retinerea fiului. In plus in fiecare nod vom mai retine 8 biti grupati cate 2 pentru a retine pentru fiecare din cei 4 fii daca este sau nu o frunza si in cazul in care este o frunza retinem si culoarea ei. In total se poate folosi cu usurinta sub 8M memorie.

Strigat

Flux

Vom forma un sistem de ecuatii in care necunoscutele X_i vor fi suma fluxurilor de pe drumul de la 0 la nodul i (care se garanteaza ca este aceeasi indiferent de drum). Fluxul trimis de la i la j va fi exact n_i,j * ( X_j - X_i) unde n_i,j este numarul de muchii dintre i si j. Vom pune conditiile de conservare a fluxului pentru fiecare nod i: suma fluxurilor care intra sa fie egala cu suma fluxurilor care ies. Pentru nodul 1 nu este necesar sa scriem ecuatia deoarece se stie X₁=0, iar pentru nodul N vom pune ecuatia suma fluxurilor care intra in el sa fie 1. Sistemul de N-1 cu N-1 necunoscute se rezolva folosind Gauss.

Pana acum am satisfacut conditiile de flux si restrictia impusa de enunt, mai avem doar de satisfacut restrictiile de capacitate de pe fiecare muchie. Observam ca daca pentru ecuatia pentru nodul N in loc de 1 fixam o valoare S fluxurile trimise pe fiecare muchie se vor inmulti cu S. Asadar pentru a satisface conditiile de capacitate trebuie doar sa inmultim fluxurile de pe fiecare muchie cu minimul dintre C_i,j / F_i,j unde F_i,j este fluxul trimis pe muchie (i,j) si C_i,j este capacitatea muchiei (i,j).