s = smax = 0;
pentru i = 1, n executa
   s = max(s+A[i], A[i]);
   smax = max(smax, s);
sfarsit pentru
==
O prezentare detaila a acestei probleme si metode de rezolvare gasiti 'aici':http://www.ginfo.ro/revista/11_2/focus2.pdf.

h3. (problema usoara, clasa a 9-a)

h2. 'Zero 2':problema/zero2

h3. (problema medie, clasa a 9-a)

h2. 'Puteri':problema/puteri

h3. (problema grea, clasa a 9-a, problema medie, clasa a 10-a)

h2. 'Balanta':problema/balanta

h3. (problema usoara, clasa a 10-a)

h2. 'Expresii 2':problema/expresii2

h3. (problema grea, clasa a 10-a)

h2. 'Ograzi':problema/ograzi

h3. (problema usoara, clasele 11-12)

Problema este una clasica de cautari ortogonale si se poate face usor o solutie in care se sorteaza dreptunghiurile si punctele dupa coordonata $x$, iar apoi se foloseste o linie de baleiere. Se proceseaza updateuri si querieruri pe un arbore de intervale in o dimensiune. Aceasta solutie are complexitate $O(M*lg N + N*lg N)$. S-au obtinut in jur de $70$ de puncte folosind asemenea abordari.
Pentru a obtine o solutie mai eficienta trebuia exploatata particularitatea problemei, adica faptul ca toate dreptunghiurile erau egale. Solutia autorului continea doi pasi: 

* Intai folosim grila de puncte de coordonate $(i*W+0.5, j*H+0.5)$ unde $i$ si $j$ sunt numere intregi. Orice dreptunghi din enunt contine exact un punct din aceasta grila. Vom folosi o tabela de dispersie (hash) ce grupeaza in perechi dreptunghiurile din intrare si punctele din grila interioare lor. 
* Pentru a determina daca un punct din cele $M$ este continut in vreun dreptunghi, ne uitam care sunt cele patru puncte din grila vecine acestuia, si vom gasi maxim patru dreptunghiuri asociate acelor 4 puncte din grila. Apoi testam incluziunea punctului nostru in fiecare dintre cele patru dreptunghiuri, astfel putem raspunde la orice test de incluziune in $O(1)$. 

Complexitatea toatala a algoritmului este $O(N + M)$. Felicitam pe Berzan Constantin care a folosit aceasta abordare si a fost singurul ce a luat punctaj maxim pe aceasta problema.

h2. 'KPerm':problema/kperm

h3. (problema medie, clasele 11-12)

Fie $sigma$ o {$K$}-permutare cu $N$ elemente => pentru orice {$i$}, {$1 ≤ i ≤ N-K$} avem relatiile:

* {$sigma{~i~} + sigma{~i~} + ... sigma{~i+K-1~}$} congruent cu $0$ ( mod $K$ )
* {$sigma{~i+1~} + sigma{~i+2~} + ... sigma{~i+K~}$} congruent cu $0$ ( mod $K$ )

Scazand cele doua relatii, obtinem $sigma{~i~}$ congruent cu $sigma{~i+K~}$ ( mod {$K$} ).
Fie $N$ = {$C * K + R$}, {$0 &le; r < K$}.
Se observa ca intr-o {$K$}-permutare nu conteaza decat resturile numerelor la impartirea cu $K$, si nu numerele propriu-zise. Deci putem privi o permutare in functie de cate resturi r sunt in permutare, pentru orice {$r$} de la $0$ la {$K-1$}. Se observa ca resturile de la $1$ la $R$ apar de exact {$C+1$} ori, in timp ce toate celelalte resturi apar de exact $C$ ori.

I. {$N &ge; 2 * K$}, sau, echivalent {$C &ge; 2$}. Se observa ca in primele $C$ numere din permutarea care constituie o solutie nu putem pune acelasi rest de cel putin $2$ ori. Observatia este evidenta, deoarece, cum avem relatia $sigma{~i~}$ congruent cu $sigma{~i+K~}$ ( mod {$K$} ), atunci restul care ar aparea de 2 ori in primele $C$ numere ar aparea de cel putin {$2*C$} ori ( pe primele {$C*K$} pozitii ), dar avem maxim {$C+1$} resturi disponibile egale, si cum {$2*C > C+1$}, am ajuns la o contradictie.
II. {$K &le; N < 2*K$}. In acest caz, resturile de la $1$ la $R$ apar de $2$ ori fiecare, iar toate celelalte resturi apar o singura data. Cum doar pozitiile de la $R+1$ la $C$ au un rest unic in permutare ( toate celelalte resturi apar pe exact doua pozitii de forma $i$ si $i + K$ ) => pe aceste pozitii trebuie sa punem toate resturile care apar o singura data. Este evident si ca in primele $R$ pozitii trebuie sa punem resturile diferite doua cate doua, pentru ca fiecare rest apare de doua ori si trebuie pus pe doua pozitii.

Din ambele cazuri a rezultat ca pentru orice valori ale numerelor $N$ si $K$, o {$K$}-permutare trebuie sa respecte urmatoarele proprietati: 

* pe primele $K$ pozitii din permutare trebuie sa se gaseasca toate resturile {$0$}, {$1$}, ... {$K-1$}
* resturile de la $1$ la $R$ trebuie sa fie asezate pe primele $R$ pozitii
* pe fiecare pozitie $i$ incepand cu $K+1$ trebuie sa punem un numar care sa aiba restul din impartirea la $K$ egal cu restul impartii numarului de pe pozitia $i-K$ la {$K$}

Pentru $K$ par, {$K = 2p$}, cum {$0+1...+(2p-1)$} = {$p*(2p-1)$} si acest numar nu se divide cu {$2p$} pentru ca {$2p-1$} este impar => raspunsul este 0.

Pentru $K$ impar, {$K = 2p+1$}, cum {$0+1...+2p$} = {$p*(2p+1)$}, care este dizibil la {$(2p+1)$}, vom construi permutarea astfel:

* fixam ordinea primelor $R$ resturi ( in total {$R!$} variante )
* fixam ordinea celorlalte $K-R$ resturi ( in total {${@(K-R)!@}$} variante )
* pentru fiecare rest din primele $R$ sunt $C+1$ pozitii pe care trebuie sa il asezam. Pentru fiecare rest putem pozitiona numerele atasate in {$(C+1)!$} variante, si, cum sunt $R$ resturi, avem {$[(C+1)!]^R^$} variante
* pentru fiecare din celelalte resturi sunt $C$ pozitii pe care trebuie sa le asezam. Pentru fiecare rest putem deci pozitiona numerele atasate in {$C!$} variante, si, cum sunt $K-R$ resturi, avem {$(C!)^K-R^$} variante.

Pentru $K$ impar raspunsul este, dupa cum am demonstrat mai sus, {$(R!)$} * {${@(K-R)!@}$} * {$[(C+1)!]^R^$} * {$(C!)^K-R^$}.

OBS. In relatia de mai sus nu are importanta daca {$R = 0$}, caci {$0! = 1$} si {$A^0^ = 1$}, pentru orice {$A$}. Deci demonstratia a fost facuta fara a restrange generalitatea.


h2. 'Magazin':problema/magazin

h3. (problema grea, clasele 11-12)


==Include(page="template/preoni-2007/footer")