Diferente pentru preoni-2007/runda-2/solutii intre reviziile #20 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 este consta in faptul ca el nu noteaza nodurile prin care trece, ci doar culorile acestora.
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).
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$.
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. exista avem numai greutati intre $1$ si $200$, putem folosi o alta abordare: $A[i][j]$ = numarul minim de obiecte necesare cu greutate $≤ 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.
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.
$A[i][j] = min(A[i-1][j], A[i-1][j-V[i]]+1)$ unde $V[i]$ este greutatea obiectului $i$ ({$i ≤ N, j ≤ 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 $≤ 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 ≤ 200, j ≤ 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] ≤ x ≤ 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 $√200$ in $√200$. O scurta descriere despre aceasta metoda gasiti 'aici':http://infoarena.ro/winter-challenge-1/solutii (problema Smen). Memoria folosita ar fi fost $O(√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 ≤ 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 $≤ 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.