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

Nu exista diferente intre titluri.

Diferente intre continut:

==Include(page="template/preoni-2007")==
==Include(page="template/todo")==
 
h1. Solutii Runda 2
h2. 'Amlei':problema/amlei
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 {_bttom-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.
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
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':http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor. 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^$.
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])$.
h3. (problema grea, clasa a 10-a, problema medie, clasele 11-12)
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)
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.