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

_Comentarii aici..._
 

h1. Solutii Runda Finala
h2. 'Orase':problema/orase
h3. (problema usoara, clasa a 9-a)

La primul pas se vor sorta orasele crescator dupa $D{~i~}$. Renumerotand orasele in ordinea sortarii, putem calcula distanta care trebuie parcursa intre doua orase $j < i$: $L{~i~}+D{~i~}+L{~j~}-D{~j~}$. Pentru fiecare $i$ vrem sa determinam un oras $j < i$ astfel incat sa se maximizeze aceasta distanta. Alegerea optima va fi un oras $j$ cu valoarea $L{~j~}-D{~j~}$ maxima; astfel, pe masura ce se avanseaza cu indicele $i$ se pastreaza si un indice $j$ maxim pana in prezent. Complexitatea rezolvarii este $O(N*lg N)$ datorita sortarii.
 

h2. 'Sarpe':problema/sarpe
h3. (problema medie, clasa a 9-a)

table(example). | 1 | 2 | 3 | ... |
| 2N | 2N-1 | 2N-2 | ... |

* $2$ este asezat in coltul dreapta jos caz in care vom avea de completat tabla ramasa cu numerele {$3$}, {$4$}, ... {$2N$} punand $3$ la dreapta lui $2$ lucru care este echivalent cu completarea unei table cu $N-1$ coloane cu $1$ fixat in unul din colturi.

* $2$ este asezat in coltul din stanga jos caz in care vom avea de completat tabla ramasa cu numerele {$3$}, {$4$}, ... {$2N$} punand $3$ la dreapta lui $2$ lucru care este echivalent cu completarea unei table cu $N-1$ coloane cu $1$ fixat in unul din colturi.

table(example). | 1 |   | ... |
| 2 | 3 | ... |

table(example). |i | ... | 2 | 1 | ... |
| i+1 | ... | 2*i - 1  | 2*i | ... |

Deci vor ramane de completat N-i coloane care trebuie completate cu 2*i+1 pus intr-un colt fixat. Deci vom avea in total N-i posibilitati. In mod analog daca $2$ se afla in dreapta vom avea $i-1$ posibilitati. Numarul total de posibilitati cand $1$ se afla pe una din coloanele {$2, 3, ... N-1$} va fi suma de la $2$ la $N-1$ din {$2(N-i+i-1)$} adica {$2(N-2)(N-1)$} deoarece se poate incepe de sus sau de jos. Raspunsul cautat va fi {$4N + 2(N-1)(N-2)$}, {$N > 1$}. Operatiile trebuiau efectuate pe numere mari.

Deci vor ramane de completat $N-i$ coloane care trebuie completate cu $2*i+1$ pus intr-un colt fixat. Deci vom avea in total $N-i$ posibilitati. In mod analog daca $2$ se afla in dreapta vom avea $i-1$ posibilitati. Numarul total de posibilitati cand $1$ se afla pe una din coloanele {$2, 3, ... N-1$} va fi suma de la $2$ la $N-1$ din {$2(N-i+i-1)$} adica {$2(N-2)(N-1)$} deoarece se poate incepe de sus sau de jos. Raspunsul cautat va fi {$4N + 2(N-1)(N-2)$}, {$N > 1$}. Operatiile trebuiau efectuate pe numere mari.

h2. 'Sate':problema/sate

Rezolvarea {$O(N+M)$} se bazeaza pe faptul ca nu avem nevoie sa stim lungimile tuturor segmentelor, ci doar a celor care au unul din capete punctul {$A{~X~}$}. Notam cu {$D{~i~}$} lungimea segmentului {$A{~X~}A{~i~}$}. Fiecare punct va fi identificat printr-un nod intr-un graf. Lungimea muchiei intre intre doua noduri va fi lungimea segmentului dat de punctele corespunzatoare nodurilor. Acum putem aplica o parcurgere BF din nodul $X$ si respectam toate cazurile care apar. In final, in {$D{~Y~}$} se afla lungimea segmentului {$A{~X~}A{~Y~}$}.

h2. 'Branza':problema/branza
h3. (problema medie, clasa a 10-a)

Este evident ca cele doua poligoane convexe pot fi separate de o dreapta care sa treaca printr-un varf $A$ de pe primul poligon si un varf $B$ de pe cel de-al doilea. Astfel, dreapta imparte planul in doua semiplane si in fiecare din cele doua semiplane se afla cate un poligon convex.
Dintre cele $N$ puncte alegem toate perechile de puncte {$(X Y)$} si presupunem ca dreapta determinata de aceste doua puncte separa cele doua poligoane, iar punctul $X$ este varf pentru primul poligon si punctul $Y$ pentru cel de-al doilea. Pentru o dreapta fixata, putem aplica pentru fiecare din cele semiplane un algoritm de infasuratoare convexa ( verificand apoi daca infasuratoarea convexa contine toate punctele din semiplanul respectiv ) in {$O(N log N)$}, rezultand o complexitate totala de {$O(N^3^ log N)$}. Pentru a obtine complexitatea {$O(N^3^)$}, putem sorta punctele in functie de ordonata si apoi in functie de abscisa de la inceput. Astfel, in algoritmul Graham pentru poligoane convexe nu mai este necesara resortarea punctelor si algoritmul, pentru o dreapta fixata, dureaza {$O(h1) + O(h2)$}, unde $h1$ si $h2$ sunt numarul de puncte din cele doua semiplane. Cum {$O(h1 + h2)$} = {$O(N)$}, complexitatea algoritmului este {$O(N^3)$}.

h2. 'P-Sir':problema/psir
h3. (problema usoara, clasele 11-12)

Problema se rezolva prin metoda programarii dinamice. Conditia din enunt se poate enunta astfel: elementul $a{~i~}$ dintr-un p-sir trebuie sa fie inclus strict in intervalul determinat de $a{~i-1~}$ si $a{~i-2~}$. Vom calcula $Nr[i][j]$ numarul de p-subsiruri care au ultimiii doi termeni $P{~i~}$ si $P{~j~} (i < j)$.
Vom presupune ca $P{~i~} < P{~j~}$, cazul $P{~i~} > P{~j~}$ putand fi tratat asemanator. $Nr[i][j]$ se va calcula ca suma de $Nr[k][i]$ cu proprietatea $P{~i~} < P{~j~} < P{~k~}$. O implementare directa a acestei rezolvari are complexitatea $O(N^3^)$ si ar fi obtinut $30$ de puncte. Daca sortam vectorul $P$ dat la intrare, valorile $k < i$ care respecta conditia $P{~j~} < P{~k~}$ vor forma un interval continuu ca indici. Vom calcula sume partiale pentru coloana $i$ din matricea $Nr$ parcurgand liniile matricii in ordinea sortarii. Astfel, calculul lui $Nr[i][j]$ se reduce la scaderea a doua sume partiale. Pentru a identifica exact ce sume se scad se poate folosi o cautare binara, reducand astfel rezolvarea la $O(N^2^*lg N)$.
Mentionam ca se poate obtine si o solutie $O(N^2^)$ daca se calculeaza valorile de pe linia $i$ din matricea $Nr$ in ordinea sortarii. Putem astfel renunta la cautare binara, deoarece indicele in care se face scaderea sumelor partiale va fi monoton.
Ca o ultima precizare, nu era necesar folosirea tipurilor de date pe $64$ de biti pentru a efectua operatii modulo $2^32^$. Mai mult, nu este necesar nici macar folosirea operatiei modulo. Daca se foloseste un tip intreg pe $32$ fara semn ({$unsigned$} in $C/C++$) orice operatie cu variabile de acest tip este automat modulo $2^32^$.
 
 

h2. 'Eval':problema/eval
h3. (problema medie, clasele 11-12)

Este evident ca o solutie care simula evaluarea expresiei nu s-ar fi incadrat ca timp sau ca memorie, deoarece rezultatele obtinute pe parcurs pot fi foarte mari, desi rezultatul final este limitat de $10^1000^$. Pentru rezolvarea acestei probleme este necesara 'teorema chineza a resturilor':http://en.wikipedia.org/wiki/Chinese_remainder_theorem :
Fie $K$ numere prime distincte $P{~1~}, P{~2~},... ,P{~K~}$ si $K$ resturi $R{~1~}, R{~2~},... R{~K~}$.
Exista un numar natural unic $N$ mai mic decat produsul celor $K$ numere prime care satisface relatiile $N = R{~i~} (mod P{~i~})$.
Vom rezolva intai problema de $70%$, adica variabilele si rezultatul sunt numere naturale. Daca alegem un numar suficient de numere prime astfel incat produsul lor sa fie mai mare decat $10^1000^$, putem calcula rezultatul expresiei modulo fiecare numar prim in timp liniar si putem reconstitui rezultatul (care va fi unic) folosind teorema chineza a resturilor. O prezentare detaliata a acestei teoreme se gaseste si in 'acest articol':downloads?action=download&file=mate.pdf.
Putem reduce varianta cu numere intregi la problema initiala cu numere naturale adunand constanta $10^1000^$ la expresie. Astfel se garanteaza ca rezultatul expresiei este in intervalul $[0, 2*10^1000^]$.
Deoarece lungimea expresiei este de $100.000$ trebuiau se se foloseasca numere prime relativ mari. Solutia oficiala foloste aproximativ $120$ de numere prime din intervalul $[10^9^, 2*10^9^]$.
 

h2. 'Obiective':problema/obiective
h3. (problema grea, clasele 11-12)