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

La prima vedere, problema este asemanatoare cu problema 'rucsacului':http://en.wikipedia.org/wiki/Knapsack_problem, deci se poate aborda folosind metoda programarii dinamice. Avand in vedere limita mare pentru numarul $L$ o astfel de abordare nu ar fi obtinut punctaj maxim.   Avand in vedere ca toate monezile sunt puteri ale numarului $C$, exista o rezolvare greedy: se determina cel mai mare tip de moneda $C^A{~i~}^$ disponibil si se foloseste un numar maxim posibil de astfel de monede (minimul dintre $L/C^A{~i~}^$ si $B{~i~}$).

La prima vedere, problema este asemanatoare cu problema 'rucsacului':http://en.wikipedia.org/wiki/Knapsack_problem, deci se poate aborda folosind metoda programarii dinamice. Avand in vedere limita mare pentru numarul $L$ o astfel de abordare nu ar fi obtinut punctaj maxim.   Avand in vedere ca toate monezile sunt puteri ale numarului $C$, exista o rezolvare greedy: se determina cel mai mare tip de moneda $C^A{~i~}^$ disponibil si se foloseste un numar maxim posibil de astfel de monede (minimul dintre $L/C^A{~i~}^$ si $B{~i~}$). Complexitatea unei astfel de solutii este $O(log{~C~} L)$. O solutie care ar fi efectuat scaderi repetate ale cele mai mari monezi ar fi obtinut de asemenea punctaj maxim.

h2. 'Dezastru':problema/dezastru
h3. (problema grea, clasa a 9-a)

Daca o problema de probabilitati ar fi putut incurca o parte a concurentilor de clasa a 9-a, exemplele date in enunt reprezinta un indiciu destul de clar in legatura cu modalitatea de rezolvare. Din moment ce evenimentele pot aparea in orice ordine, avem $N!$ posibilitati. Ar trebui, deci, sa generam toate permutarile, sa calculam pentru fiecare permutare produsul primelor $K$ valori, si sa facem media aritmetica a rezultatelor obtinute. Problema se reduce succesiv la aranjamente si apoi la combinari, fiind suficient sa consideram toate modurile de a alege $K$ evenimente, indiferent de ordine. Solutiile cu permutari si aranjamente obtin punctaje partiale, in functie de grija acordata implementarii.
 
Problema se poate rezolva si folosind programarea dinamica. Se construieste matricea $A{~i,j~}$ cu semnificatia suma tuturor produselor de $j$ factori alesi din primele $i$ numere. Recurenta se poate calcula usor {$A{~i,j~}=A{~i-1,j~}+A{~i-1,j-1~}*P{~i~}$}. Probabilitatea ceruta va fi $A{~n,k~}$ impartita la $C{~n,k~}$ (combinari de $n$ luate cate {$k$}). Complexitate $O(n*k)$.
 

h2. 'Bowling':problema/bowling
h3. (problema usoara, clasa a 10-a)

In primul rand, pentru a intelege solutia acestei probleme si altor probleme asemanatoare se recomanda citirea urmatoarelor documente despre teoria jocurilor:
 
* 'Teoria jocurilor: numerele Sprague-Grundy':http://www.ginfo.ro/revista/14_5/mate.pdf, 'GInfo Mai 2004':http://www.ginfo.ro, Cosmin Negruseri
* 'Game Theory Text: Impartial Combinatorial Games':http://www.math.ucla.edu/~tom/Game_Theory/comb.pdf, Thomas Ferguson
 
Aceasta problema se regaseste in literatura de specialitate si cu titlul de _Kayles_. Rezultatul pentru un joc se poate calcula in functie de $XOR$-ul numerelor _Grundy_ pentru fiecare secventa de popice din sir. Cum $N ≤ 50.000$, trebuie calculate valorile Grundy pentru fiecare secventa de $i$ popice cu $i ≤ 50.000$. Acestea se pot calcula in complexitate patratica si se pot pune in sursa ca un sir de constante. O alta solutie se foloseste de observatia ca incepand cu $i = 72$ sirul de valori se repeta cu perioada $12$. Pentru fiecare test din fisier, complexitatea rezolvarii este $O(N)$.
 

h2. 'Regiuni':problema/regiuni
h3. (problema medie, clasa a 10-a, problema usoara, clasele 11-12)

Aceasta problema a aparut din cauza faptului ca autorul a inteles gresit problema Druizi de la concursul .campion. Dupa ce am discutat problema cu mai multe persoane am observat ca majoritatea pornesc de la problema mai simpla de a vedea daca doua puncte sunt sau nu in acelasi grup. Ideea mea initiala este putin diferita: rezolvam problema adaugand pas cu pas cate o dreapta si mentinand informatia despre grupuri. Cand adaugam o dreapta iteram peste toate grupurile. Un grup va fi impartit in alte doua: punctele din stanga dreptei si punctele din dreapta. E posibil ca unul din aceste doua grupuri sa fie vid si atunci nu il mai retinem. Un grup il impartim in doua in $O(a)$ operatii unde a este numarul de elemente din grup. Toate grupurile vor avea in total $a1 + a2 + ... + ai + ... = M$ elemente, deci pentru a actualiza grupurile adaugand o dreapta facem $O(M)$ pasi. Astfel solutia are complexitatea finala $O(N * M)$, si este foarte usor de implementat.
 
Alte solutii ar fi determinarea pentru fiecare punct a unui vector ce ne spune pentru fiecare dreapta in ce parte e situat punctul. Daca doi astfel de vectori asociati la doua puncte sunt egali, atunci cele doua puncte sunt situate in aceiasi regiune. Pentru determinarea egalitatii vectorilor s-ar fi putut folosi o sortare naiva si astfel am fi avut o solutie de complexitate $O(MN log M)$ sau am fi putut folosi radix sort pentru a o aduce la $O(MN)$. Aceste doua solutii folosesc $O(MN)$ memorie. Alta solutie ar fi sa obtinem un cod hash pentru fiecare vector, aceasta solutie are complexitatea $O(MN)$ ca timp si $O(M + N)$. memorie. Pentru a face probabilitatea de coliziune cat mai mica putem folosi cate doua coduri diferite pentru fiecare vector. Alta observatie ar fi ca vectorii sunt binari si pastrand informatia pe biti folosim mai putina memorie si avem mult mai putine operatii la comparare daca vrem sa folosim solutia in $O(MN log M)$.
 

h2. 'Elimin 2':problema/elimin2
h3. (problema grea, clasa a 10-a)

* folosim cifra a $i$-a ( notata $c$ ) in solutia optima. Pentru ca numarul intre $i$ si $j$ sa fie palindrom, este suficient sa aflam ultima pozitie $p$ inainte de $j$ a cifrei c, solutia optima intre $i$ si $j$ obtinandu-se din solutia optima intre $i+1$ si $p-1$ la care adaugam 2 cifre ( cele din capete ).
* folosim cifra a $j$-a ( notata $c$ ) in solutia optima. Se trateaza similar.

Daca tablourile $LEFT$ si $RIGHT$ sunt construite inainte de a incepe programarea dinamica ( preprocesare ), putem construi tabloul $L$ in complexitate {$O(NR_CIF^2^)$}, unde $NR_CIF$ este numarul de cifre ale lui {$N$}. Dupa ce am construit acest tablou, putem reconstitui solutia optima. Sa presupunem ca dorim sa cautam aceasta solutie intre pozitiile {$i$} si {$j$} si {$L{~i,j~}$} = {$X$}. Vom pune la capetele solutiei cea mai mare cifra $c$ care indeplineste:
{$L{~LEFT[c,i]+1,RIGHT{@[c,j]@}-1~}$} = {$X-2$}.
 

Daca tablourile $LEFT$ si $RIGHT$ sunt construite inainte de a incepe programarea dinamica ( preprocesare ), putem construi tabloul $L$ in complexitate {$O(NR_CIF^2^)$}, unde $NR_CIF$ este numarul de cifre ale lui {$N$}. Dupa ce am construit acest tablou, putem reconstitui solutia optima. Sa presupunem ca solutia optima incepe cu cifra nenula {$c$}. Fie $x$ prima aparitie a cifrei $c$ in numarul $N$, si $y$ ultima aparitie. Vom selecta acea cifra $c$ pentru care valoarea {$L{~x,y~}$} este maxima. Pentru valori egale se alege cifra maxima. Dupa ce am determinat valoarea primei cifre, putem presupune ca dorim sa cautam solutia optima intre pozitiile {$i$} si {$j$} si {$L{~i,j~}$} = {$X$}. Vom pune la capetele solutiei cea mai mare cifra $c$ care indeplineste: {$L{~LEFT[c,i]+1,RIGHT{@[c,j]@}-1~}$} = {$X-2$}.

In final, eliminam {$0$}-urile terminale ( de la ambele capete ale numarului palindrom ) si afisam acest numar. De precizat ca un algoritm de complexitate {$O(NR_CIF^2^)$} si constanta $10$ ar fi obtinut in jur de 50 de puncte.

De precizat ca un algoritm de complexitate {$O(NR_CIF^2^)$} si constanta $10$ ar fi obtinut in jur de 50 de puncte.

h2. 'Distincte':problema/distincte
h3. (problema medie, clasele 11-12)

Vom calcula in timp liniar urmatorul vector:
$urm{~i~} = min { j / i < j AND A{~j~} = A{~i~}}$
Astfel, $urm{~i~}$ va fi prima pozitie din dreapta egala ca valoare cu elementul de pe pozitia $i$ (daca nu exista $urm{~i~}$ consideram ca $urm{~i~}$ este egal cu $N+1$). Considerand $N$ puncte in plan cu coordonatele $(i, urm{~i~})$ la care se ataseaza valoarea $A{~i~}$, o intrebare $st &le; dr$ se rezolva facand un query in dreptunghiul $[st..dr] x [dr+1..N]$, adica suma acelor elemente care se afla in interval, iar urmatoarea aparitie la dreapta este in afara intervalului. Acest query ne garanteaza ca se va face doar suma elementelor distincte din intervalul $st..dr$. O rezolvare care imparte vectorul in bucati de $&radic;N$ si rezolva intrebarile in $O(&radic;N)$ ar fi obtinut cel putin $50$ de puncte, desi este probabil sa obtina si punctaj maxim optimizand codul. O rezolvare mai buna din punct de vedere al complexitatii este folosirea arborilor de intervale, tehnica descrisa 'aici':downloads?action=download&file=arbori_de_intervale.zip si care poate fi folosita si la rezolvarea problemei 'Zoo':problema/zoo. Din pacate, aceasta solutie este greu de implementat, iar solutia in $O(lg^2^ N)$ probabil ar fi fost prea inceata pentru a obtine punctaj maxim.
Rezolvarea problemei se simplifica mult daca se sorteaza intervalele care se dau ca intrebari dupa capatul dreapta, si se proceseaza in aceasta ordine, apoi se afiseaza in ordinea initiala. Parcurgand intervalele descrescator dupa capatul dreapta se poate mentine suma punctelor care au coordonata $y$ in afara capatului dreapta curent, si se pot calcula raspunsurile pentru intervale in timp $O(log N)$ folosind fie un arbore de intervale, fie, si mai simplu, cu un arbore indexat binar.
 

h2. 'Laser':problema/laser
h3. (problema grea, clasele 11-12)

Vom considera semidreptele ce pleaca din origine si trec printr-un capat al unui segment. Vor exista $2*N$ astfel de semidrepte. Pentru fiecare din cele $2*N$ unghiuri formate consideram bisectoarea sa. Orice alta semidreapta ce pleaca din origine va intersecta aceleasi segmente cu una din cele $2*N$ bisectoare. Deci Gigel nu trebuie sa traga decat in unele din aceste bisectoare. In loc de bisectoare se putea considera orice alta semidreapta strict in interiorul unghiului, dar bisectoarea este mai usor de calculat. Avand maxim $2*N$ bisectoare ne vom incadra in limitarea de $10.000$ de trageri.
 
Vom forma un sistem cu $N$ ecuatii si $2*N$ necunoscute astfel: pentru un segment $i$ se formeaza o ecuatie de forma
 
* $B{~i~} = X{~1~} * A{~i,1~} + X{~2~} * A{~i,2~} + ... + X{~2*N~} * A{~i,2*N~}$
** $B{~i~}$ este starea initiala a neonului $i$
** $X{~1~}, X{~2~}, ..., X{~2*N~}$ sunt cele $2*N$ necunoscute care semnifica faptul ca se trage pe directia respectivei bisectoare
** $A{~i,j~} = 1$ in caz ca bisectoarea $j$ intersecteaza segmentul {$i$}, $0$ in caz contrar.
 
Sistemul se va rezolva modulo $2$ folosind algoritmul lui 'Gauss':http://en.wikipedia.org/wiki/Gauss_algorithm.
 
Pentru calcularea valorilor $A{~i,j~}$ se calculeaza unghiul format de semidreptele ce trec prin capetele segmentului $j$ si se testeaza daca semidreapta i se afla in interiorul sau. Trebuie avut grija la eventualele cazuri care apar, in special cand unghiul are o semidreapta in cadranul $4$ si alta in cadranul {$1$}.
 
Complexitate $O(n^3^)$
 
O optimizare, care insa nu era necesara pentru obtinerea punctajului maxim, ar fi reprezentarea sistemului format pe biti reducand complexitatea la {$O(n^3^ / log n)$}.
 

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