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])$.

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

* $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.

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.

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 detemrina 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)$.

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)$