Diferente pentru preoni-2007/runda-2/solutii intre reviziile #3 si #40

Nu exista diferente intre titluri.

Diferente intre continut:

h1. Solutii Runda 2
h2. Amlei
h2. 'Amlei':problema/amlei
h3. (problema usoara, clasa a 9-a, clasa a 10-a)
h2. Tricouri
Primul pas al algoritmului este eliminarea conjunctiilor elementare care se repeta, deoarece $A$ OR $A$ = $A$. In continuare, se observa usor ca daca o conjunctie elementara apare doar intr-una din formule, distributia variabilelor care o face adevarata va conduce la rezultate diferite. Asadar, formulele sunt echivalente daca si numai daca contin aceleasi conjunctii elementare, facand abstractie de ordinea termenilor.
 
Problema se poate rezolva astfel sortand termenii fiecarei conjunctii si conjunctiile dupa un criteriu oarecare.
 
h2. 'Tricouri':problema/tricouri
h3. (problema medie, clasa a 9-a)
h2. Zone
Dupa ce citim cele $N$ numere din fisierul de intrare, vom realiza o preprocesare ({_filtrare_}) in urmatorul mod:
{$M{~i, j~}$} va fi o lista ( implementata fie ca vector, fie ca lista liniara simplu inlantuita ) care va retine in ordine descrescatoare numerele din fisierul de intrare care dau restul $j$ la impartirea cu {$i$}. Deoarece pentru fiecare interogare numarul de termeni este cel mult 5, este suficient ca aceasta lista sa retina cel mult 5 termeni. Astfel, in momentul in care citim un element de valoare {$x$}, pentru fiecare $i$ de la 2 la 20, vom introduce elementul in lista {$M{~i, x mod i~}$} daca si numai daca aceasta lista nu contine inca 5 termeni sau $x$ este mai mare decat minimul din lista ( in acest ultim caz $x$ va fi copiat peste acest minim, asigurand ca in lista vor ramane cele mai mari numere posibile ).
In momentul in care citim o interogare de forma {$K P$}, vom genera toate posibilitatile de resturi la impartirea cu $P$ ale primelor $K-1$ numere din suma, al {$K$}-lea rest fiind unic determinat. Pentru o astfel de configuratie de resturi stim in timp {$O(1)$} care este cea mai mare suma ( daca exista ) a unor elemente care sa aiba resturile astfel stabilite, prin utilizarea informatiilor din tabloul {$M$}.
De exemplu, daca $K = 3$ si {$P = 4$}, pentru primele doua resturi stabilite ale primelor doua numere ( sa zicem ca aceste resturi au valoarea $3$ si respectiv {$2$}), restul celui de-al treilea numar la impartirea cu $4$ nu poate fi decat $3$. Acum, folosind tabloul {$M$} calculat anterior, trebuie sa stim care sunt cele mai mari doua numere care dau la impartirea cu $4$ restul $3$ si care este cel mai mare numar care la impartirea cu $4$ da restul {$2$}. Aceasta suma poate fi calculata deci in {$O(1)$}. Vom genera ( prin metoda backtracking sau folosind mai multe for-uri imbricate ) toate configuratiile posibile de resturi, si o vom retine pe cea care genereaza suma cea mai mare, suma pe care ulterior o vom afisa. Complexitatea finala este deci {$O(N + M * P^K-1^)$}, care asigura punctajul maxim, folosind nivelul cunostintelor de clasa a IX-a.
 
O alta solutie mai eleganta dar care depaseste cunostintele de clasa a IX-a ar fi cea care foloseste programarea dinamica in modul urmator: se noteaza cu {$D{~i,j,r~}$} care este suma maxima folosind $i$ numere din primele $j$ resturi posibile la impartirea cu $P$ si pana in momentul curent sa avem format restul {$r$}. Se construieste acest tablou in mod {_bottom-up_}. Raspunsul se va afla in {$D{~K,P-1,0~}$}. Complexitatea unui astfel de algoritm este {$O(N + M * K^2^ * P^2^)$}, care de asemenea obtine 100 de puncte.
 
h2. 'Zone':problema/zone
h3. (problema grea, clasa a 9-a)
Pentru linia l1 si sumele corespunzatoarele zonelor 1, 2 si 4 o solutie potentiala ( adica un cvadruplu de forma l1, l2, c1, c2 ) este unic determinata deoarece elementele matricii initiale sunt pozitive. Astfel, vom determina intai coloana c1 pentru ca suma din regiunea 1 sa fie S1. Pentru c1 stabilit vom afla c2 astfel incat suma din regiunea 2 sa fie S2. Pentru a determina
Se observa ca daca stim linia {$L{~1~}$} si suma asociata zonei {$1$}, coloana {$C{~1~}$} este unic determinata deoarece elementele matricii initiale erau pozitive: pornind cu submatricea de colturi {$(1, 1)$} si {$(L, 1)$}, va trebui sa crestem $C{~1~}$ pana cand suma submatricii de colturi {$(1, 1)$} si {$(L{~1~}, C{~1~})$} va deveni cat am stabilit initial. Cum suma submatricii de colturi {$(1, 1)$} si {$(L{~1~}, X)$} este mai mica decat suma submatricii de colturi {$(1, 1)$} si {$(L{~1~}, X+1)$}, cautarea coloanei {$C{~1~}$} poate fi realizata prin cautare binara. Dupa ce am determinat {$C{~1~}$}, stabilim care dintre cele 8 sume ramase este valoarea zonei {$2$} si determinam in mod similar valoarea coloanei {$C{~2~}$}. Apoi stabilim care dintre cele 7 sume ramase este valoarea pe care o vom asocia zonei {$4$} si determinam si {$L{~2~}$}. Pentru un cvadruplu astfel determinat, {$L{~1~}$}, {$C{~1~}$}, {$L{~2~}$} si {$C{~2~}$}, vom determina toate cele 9 sume care se formeaza si daca ele sunt egale cu sumele impuse initial, atunci inseamna ca avem o solutie. Dintre toate solutiile posibile o vom afisa in final pe cea care respecta conditiile de minimalitate enuntate.
 
In momentul in care cautam binar o linie sau o coloana va trebui sa aflam suma pentru o anumita submatrice. Pentru a realiza acest lucru eficient, vom construi de la inceput matricea de sume partiale {$S$}, unde {$S{~i,j~}$} reprezinta suma elementelor din submatricea care are coltul stanga-sus in {$(1, 1)$} si coltul dreapta-jos in {$(i, j)$}. Astfel, suma submatricii de colturi {$(x{~1~}, y{~1~})-(x{~2~}, y{~2~})$} va fi egala cu {$S{~x2,y2~}$} - {$S{~x1-1,y2~}$} - {$S{~x2,y1-1~}$} + {$S{~x1-1,y1-1~}$}.
Pentru a afla suma unei submatrici in O(1) se foloseste o matrice auxiliara de sume partiale: M[i][j] = suma elementelor din submatricea care are coltul stanga-sus in (1, 1) si coltul dreapta-jos in (i, j).
Problema este astfel rezolvata in intregime. Complexitatea algoritmului este {$O(N^2^)$}.
h2. Plantatie
h2. 'Plantatie':problema/plantatie
h3. (problema medie, clasa a 10-a)
h2. Culori
O prima idee de solutie ar fi sa construim o matrice $A[i][j][k]$ = elementul de valoare maxima dintr-un patrat cu coltul stanga-sus pe linia $i$ si coloana $j$ si latura $k$. Aceasta  matrice se poate calcula in $O(N^3^)$ astfel:
$A[i][j][k] = max(A[i][j][k-1], A[i+1][j][k-1], A[i][j+1][k-1], A[i+1][j+1][k-1])$
Fiecare intrebare poate fi rezolvata in $O(1)$, dar constructia matricei $A$ nu se va incadra in timp pentru testele mari.
Problema poate fi consideranta o varianta clasica a problemei de $RMQ$ in $2D$. Un articol foarte detaliat (in engleza) despre problema $RMQ$ gasiti 'aici':https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/. Asadar, pentru a rezolva cazul $2D$ vom folosi ideile care se folosesc in rezolvarea cazului $1D$. Astfel, vom calcula matricea $A$ dar doar pentru laturi puteri ale lui $2$. $A[i][j][k]$ va fi elementul de valoare maxima dintr-un patrat cu coltul stanga-sus pe linia $i$ si coloana $j$ si latura $2^k^$.
$A[i][j][k] = max(A[i][j][k-1], A[i][j+2^k-1^][k-1], A[i+2^k-1^][j][k-1], A[i+2^k-1^][j+2^k-1^][k-1])$
Pentru o raspunde la o intrebare $i j k$ in $O(1)$ vom determina cea mai mare putere $p$ a lui $2$ astfel incat $2^p^ ≤ k$, si vom lua maximul din $4$ patrate cu colturile in patratul din intrebare si latura $2^p^$. Astfel, raspunsul pentru o intrebare $i j k$ este $max(A[i][j][p], A[i][j+k-2^p^][p], A[i+k-2^p^][j][p], A[i+k-2^p^][j+k-2^p^][p])$.
 
h2. 'Culori':problema/culori
h3. (problema grea, clasa a 10-a, problema medie, clasele 11-12)
h2. Reguli
Observam ca algoritmul de parcurgere al lui Bob reprezinta de fapt parcurgerea Euler a arborelui. Singura diferenta consta in faptul ca el nu noteaza nodurile prin care trece, ci doar culorile acestora.
 
Fie un arbore cu radacina in $T$, aceasta avand fii $F{~1~}$, $F{~2~}$, ... $F{~k~}$. Notand cu $[T]$ vectorul de culori generat de arborele de radacina $T$, obtinem $[T] = T$, daca arborele contine un singur nod si $[T] = T + [F{~1~}] + T + [F{~2~}] ... [F{~k~}] + T$ altfel (unde $"+"$ este operatorul de concatenare).
 
De aici se contureaza repede ideea de programare dinamica. Construim matricea $A{~i,j~} = numarul de arbori care ar fi putut genera subsecventa i..j a sirului initial de culori$.
 
Din constructia sirului de culori reiese ca are sens sa calculam $A{~i,j~}$ numai daca $C{~i~} = C{~j~}$ (unde $C$ este vectorul de culori). In acest caz subarborele determinat de primul fiu al radacinii curente va genera sirul de culori cuprins $i+1$ si un indice $k$. Fixandu-l pe acesta, problema se reduce la numararea posibilitatilor de a forma arbori care sa corespunda intervalului $i+1..k$ si cea de a forma arbori pentru intervalul $k+1..j$
 
Astfel avem $A{~i,i~} = 1$ si $A{~i,j~} = Suma(A{~i+1,k~} * A{~k+1,j~} | i < k < j si C{~i+1~} = C{~k~})$.
 
Complexitatea algoritmului este $O(N^3^)$, dar daca este implementat cu grija poate fi facut sa ruleze in aprox. 0.5 secunde pentru oricare din testele folosite la evaluare. O ultima optimizare (mica, dar care imbunatateste codul in mod simtitor) consta in faptul ca, deoarece orice parcurgere euler este de lungime impara, are rost sa calculam $A{~i,j~}$ numai daca $i+j$ este numar par.
 
h2. 'Reguli':problema/reguli
h3. (problema usoara, clasele 11-12)
h2. Ghiozdan
Problema se rezolva folosind cunostinte de potrivire a sirurilor. Fie sirul $D$ sirul diferentelor dintre termeni consecutivi ai sirului {$x$}. Astfel, trebuie sa determinam cea mai scurta perioada a acestui sir. Pentru a calcula aceasta informatie in {$O(N)$}, vom calcula functia prefix corespunzatoare sirului conform algoritmului de potrivire Knuth-Morris-Prat (KMP). Avand aceasta functie calculata, putem determina in {$O(1)$} daca primele $L$ elemente din $D$ reprezinta o perioada astfel: fie $r$ restul impartirii lui $N$ la {$L$} ( cate elemente raman la sfarsit intr-o posibila perioada incompleta ) si $c$ catul acestui rest ( numarul de perioade ). $L$ poate fi deci lungimea unei perioade daca si numai daca sunt indeplinite simultan conditiile:
 
* $PI{~N-r~}$ > 0
* {$(N-r)$} divizibil la {$(N-r-PI{~N-r~})$}
* {$(N-r)$} / {$(N-r-PI{~N-r~})$} = $c$,
* {$ok{~r~}$} este $adevarat$ ( adica ultimele $r$ caractere se potrivesc ),
 
unde $PI{~i~}$ este vectorul reprezentat de functia prefix si {$ok{~i~}$} este adevarat daca si numai daca sufixul de lungime $i$ din sir este egal cu prefixul de lungime $i$. Acest vector se poate construi tot in complexitate liniara, tinand cont de faptul ca toate sufixele care sunt si prefix pentru sirul initial au lungimile de forma $PI[N]$, $PI[PI[N]]$, $PI[PI[PI[N]]]$, etc.
 
Dintre toate lungimile $L$ care indeplinesc conditiile de mai sus se alege cea care are lungimea minima. Aceasta abordare nu este unica abordare optima. Algoritmul mentionat obtine 100 de puncte.
 
h2. 'Ghiozdan':problema/ghiozdan
h3. (problema grea, clasele 11-12)
O prima solutie clasica ar fi folosind metoda programarii dinamice. Se construieste o matrice $A[i][j]$ = numarul minim de obiecte necesare din primele $i$ obiecte pentru a obtine o greutate $j$. Relatia de recurenta este:
$A[i][j] = min(A[i-1][j], A[i-1][j-V[i]]+1)$ unde $V[i]$ este greutatea obiectului $i$ ({$i &le; N, j &le; G$}).
Aceasta solutie are complexitate $O(N*G)$ si nu se incadreaza in timp datorila limitelor mari pentru $N$ si $G$. De asemenea, pentru reconstructie trebuie pastrata o matrice $T$ de dimensiune $N*G$, care nu incape in memorie. Deoarece avem numai greutati intre $1$ si $200$, putem folosi o alta abordare: $A[i][j]$ = numarul minim de obiecte necesare cu greutate $&le; i$ pentru a obtine o greutate $j$. Relatia de recurenta este:
$A[i][j] = min(A[i-1][j], A[i-1][j-i]+1, A[i-1][j-2*i]+2 ... A[i-1][j-C[i]*i]+C[i])$ unde $C[i]$ este numarul de obiecte de greutate $i$ care exista ({$i &le; 200, j &le; G$}).
O implementare triviala ar avea aceeasi complexitate $O(N*G)$, dar putem imbunatati solutia folosind o structura de date numita _deque_. Puteti citi mai mult despre aceasta structura 'aici':http://infoarena.ro/USACO-dec-2004-divizia-GOLD (problema Divide), 'aici':http://infoarena.ro/preoni-2005/runda-3/solutii (problema Ferma) si 'aici':http://infoarena.ro/preoni-2006/runda-2/solutii (problema Struti).
Vom calcula elemente din linia $i$ a matricei astfel: intai elementele de forma $k*i$, apoi elementele $k*i+1$, $k*i+2$, ... $k*i+(k-1)$. Cand calculam $A[i][j]$ cu $j = k*i+r$ , vom avea in deque toate elementele $A[i-1][x*i+r] + (k-x)$ cu $k-C[i] &le; x &le; k$. Astfel $A[i][j]$ se determina in $O(1)$ folosind capatul stanga al deque-ului. Cand se trece la calculul elementului $(k+1)*i+r$ se elimina din deque elementul $A[i-1][(k-C[i])*i+r]+...$ , si se insereaza elementul $A[i-1][(k+1)*i+r]$. Conform relatiei, inainte de inserare toate elementele din deque ar trebui marite cu $1$, dar acest lucru este echivalent cu a scadea $1$ din elementul care se insereaza. Astfel, se poate determina matricea $A$ in timp $O(200*G)$. Deoarece se pot retine doar ultimele doua linii din matricea $A$ , memoria folosita este $O(G)$.
Desigur, pentru reconstituire ar trebui retinuta o alta matrice $T$ de dimensiuni $200*G$ ,dar nu este destula memorie pentru a construi o astfel de matrice. O solutie ar fi pastrarea liniilor din matricea $A$ din $&radic;200$ in $&radic;200$. O scurta descriere despre aceasta metoda gasiti 'aici':http://infoarena.ro/winter-challenge-1/solutii (problema Smen). Memoria folosita ar fi fost $O(&radic;200*G)$.
Din fericire existe o metoda _divide et impera_ mult mai usor de implementat pentru a reconstitui solutia folosind doar $O(G)$ memorie. Presupunem ca rezolvam problema initiala folosind dinamica de mai sus si pastrand doar ultimele doua linii din matrice. Stim acum ca greutatea maxima care se poate obtine este $H &le; G$. Consideram o solutie optima (cu numar minim de obiecte) de a lua obiecte in ghiozdan de greutate $H$. Putem imparti aceasta solutie in doua bucati: sa determinam o solutie optima de a obtine greutatea $X$ folosind obiecte cu greutati $&le; 100$ si o solutie optima de a obtine greutatea $H-X$ folosind obiecte cu greutati $> 100$. Putem determina aceasta valoare $X$ in timp ce facem dinamica initiala (folosind inca o matrice $B$ si pastrand ultimele doua linii) si apoi putem rezolva recursiv cele doua subprobleme. Asfel, la fiecare pas avem un interval $[st...dr]$ in care sunt greutatile pe care le folosim si o valoare $H$ care reprezinta greutatea pe care vrem s-o obtinem. La fiecare apel putem folosi aceleasi matrici, deci necesarul de memorie nu va depasi $O(G)$. Vom face si o analiza a complexitatii. Fie $T(st, dr, H)$ complexitatea pentru a rezolva o subproblema.
$T(st, dr, H) = O((dr-st+1)*H) + T(st, (st+dr)/2, X) + T((st+dr)/2+1, dr, H-X)$
Se poate demonstra prin inductie ca $T(st, dr, H) = O((dr-st+1)*H)$.
O prezentarea mult mai detaliata a acestei metoda si despre cum aceasta se poate aplica pentru a determina cel mai lung subsir comun a doua siruri folosind memorie liniara gasiti 'aici':http://www.ics.uci.edu/~eppstein/161/960229.html.
 
==Include(page="template/preoni-2007/footer")==

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.