==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
h3. (problema grea, clasa a 9-a, problema usoara, clasa a 10-a)

Putem considera $N$ puncte coliniare {$A{~1~}$}, {$A{~2~}$}... {$A{~N~}$}. Problema cere, daca cunoastem lungimile a exact $M$ segmente, sa determinam lungimea segmentului {$A{~X~}$}{$A{~Y~}$}. O rezolvare {$O(N^3^)$} nu este dificil de gasit. Vom afla lungimea tuturor segmentelor care se pot forma. Vom retine intr-o coada toate acele segmente carora le stim lungimea. Initial, in coada se afla doar cele $M$ segmente. Cand suntem pe un element in coada si vrem sa aflam ce noi segmente putem introduce, iteram un punct "de rupere" {$K$}. Sa presupunem ca stim lungimea segmentului {$A{~i~}A{~j~}$}. Distingem urmatoarele cazuri:
 
* {$K < i$} si stim lungimea segmentului {$A{~K~}A{~i~}$} => inseram in coada segmentul {$A{~K~}A{~j~}$} cu lungimea egala cu suma lungimilor segmentelor {$A{~K~}A{~i~}$} si {$A{~i~}A{~j~}$}
* {$i < K < j$}
** stim lungimea segmentului {$A{~i~}A{~K~}$} => inseram in coada segmentul {$A{~K~}A{~j~}$} cu lungimea egala cu diferenta dintre lungimilor segmentelor {$A{~i~}A{~j~}$} si {$A{~i~}A{~K~}$}
** stim lungimea segmentului {$A{~K~}A{~j~}$} => inseram in coada segmentul {$A{~i~}A{~K~}$} cu lungimea egala cu diferenta dintre lungimilor segmentelor {$A{~i~}A{~j~}$} si {$A{~K~}A{~j~}$}
* {$K > j$} si stim lungimea segmentului {$A{~j~}A{~K~}$} => inseram in coada segmentul {$A{~i~}A{~K~}$} cu lungimea egala cu suma lungimilor segmentelor {$A{~i~}A{~j~}$} si {$A{~j~}A{~K~}$}
 
Daca in final segmentul {$A{~X~}A{~Y~}$} a fost inserat in coada, atunci afisam lungimea acestuia.
 
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)

h3. (problema grea, 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)

Dupa sortarea listelor de adiacenta, se efectueaza o parcurgere DF din radacina lui {$G*$}.

_Propozitie 1_: Arborele DF rezultat din parcurgerea de mai sus contine numai muchii de arbore sau muchii inainte.
Cum {$G*$} este aciclic, nu pot exista muchii de intoarcere ( inapoi ). Vom demonstra ca nu exista muchii transversale. Definim {$nivel{~x~}$} ca fiind numarul de noduri de la $x$ la radacina parcurgand numai muchii de arbore.

* _Propozitie 1_: Arborele DF rezultat din parcurgerea de mai sus contine numai muchii de arbore sau muchii inainte.
 
 
Cum {$G*$} este aciclic, nu pot exista muchii de intoarcere ( inapoi ). Vom demonstra ca nu exista muchii transversale. Definim {$nivel{~x~}$} ca fiind numarul de noduri de la $x$ la radacina pe drumul format din numai muchii de arbore.

Presupunem prin reducere la absurd ca exista o muchie transversala {$x->y$}. Selectam acea muchie transversala {$x->y$} pentru care {$nivel{~y~}$} este minim. $Y$ nu poate fi radacina lui {$G*$}, pentru ca, in caz contrar, muchia {$x->y$} ar fi muchie de intoarcere si ar forma un ciclu, dar {$G*$} este aciclic. Deci exista un nod $u$ care este tatal lui {$y$}. Demonstram ca pentru tripletul {$(x u y)$} conditia (*) nu este indeplinita.
Exista drum de la $x$ la $y$ si de la $u$ la {$y$}. Drum de la $x$ la $u$ nu poate exista deoarece $u$ se afla in alt subarbore si, pentru a trece dintr-un subarbore in altul, trebuie se parcurgem muchii transversale. Dar {$x->y$} era muchia transversala pentru care {$nivel{~y~}$} era minim, si cum {$nivel{~u~}$} < {$nivel{~y~}$} si nu exista muchii de intoarcere => nu putem ajunge din $x$ in {$u$}. Nu putem ajunge nici din $u$ in $x$ datorita modului in care au fost sortate listele de adiacenta. Sa presupunem ca putem ajunge din {$u$} in {$x$}. Cum avem muchia {$x->y$}, $x$ apare inaintea lui $y$ in sortarea topologica, deci va aparea in listele de adiacenta mai devreme. Cand facem parcurgerea DF din nodul {$u$}, vom trece mai intai prin nodul $x$ si de abia dupa aceea prin nodul {$y$}, iar muchia {$x->y$} nu mai este muchie transversala.
Propozitia a fost demonstrata.

 
* _Propozitie 2_: Orice arbore DF care are doar muchii de arbore si muchii inainte indeplineste proprietatea (*).
 
 
Daca exista numai muchii de arbore si avem un triplet {$(A B C)$} care respecta ca exista drum de la $A$ la $C$ si de la $B$ la {$C$}, atunci si $A$ si $B$ se afla in lista predecesorilor lui {$C$}. Unul din nodurile $A$ sau $B$ trebuie sa apara primul in aceasta lista, deci vom avea drum fie de la $A$ la {$B$}, fie de la $B$ la {$A$}.
Cand inseram muchiile inainte nu apar triplete noi pentru care sa existe drum de la $A$ la $C$ si de la {$B$} la {$C$}, deci propozitia a fost demonstrata.
 
 
Arborele DF contine deci numai muchii de arbore si muchii inainte. Pentru un query {$(x y)$} vom aplica o strategie de tip greedy. Fie {$L$} = {$Lowest_Common_Ancestor(x, y)$}. Pentru a reorienta un numar minim de muchii, trebuie sa reorientam acele muchii care ne duc cat mai aproape de radacina. Astfel, trebuie sa ajungem intr-un nod {$u$}, stramos al lui {$x$}, pentru care {$nivel{~u~}$} ≤ {$nivel{~L~}$}. Daca putem ajunge din $x$ in {$u$}, putem cobori in arbore pana in {$y$}. Pentru acest pas vom folosi un algoritm liniar, de genul celui folosit in determinarea muchiilor critice in grafuri neorientate.
Fie {$low{~x~}$} nodul cel mai apropiat de radacina in care se poate ajunge din $x$ prin reorientarea a exact unei singure muchii si {$level{~x~}$} nivelul lui {$low{~x~}$}. Relatia de recurenta este:
 
{$level{~x~}$} = minim({$level{~parinte[x]~}$}; {$level{~y~}$} | y fiu al lui x; {$level{~u~}$} | {$u->x$} muchie inainte )
 
Simultan cu vectorul {$level$} construim si vectorul {$low$}.
 
Pe baza informatiilor astfel calculate, construim un arbore cu $N$ noduri in care tatal nodului {$i$}, $i$ de la $1$ la {$N$}, va fi {$low{~i~}$}. Acum trebuie sa aflam nodul $u$ din acest arbore care indeplineste {$nivel{~u~}$} ≤ {$nivel{~L~}$} si {$u$} se afla cat mai aproape de {$x$}. Raspunsul pe query va fi dat de diferenta de nivel dintre $u$ si {$x$}.
Pentru a afla nodul $u$ in timp logaritmic ne putem intoarce pe stramosi ai lui $x$ pe baza de puteri ale lui 2 sau putem afla nodul $u$ in {$O(1)$}, demonstrand ca nodul cautat $u$ este fie {$L$}, fie {$parinte{~L~}$} in acest arbore.
 

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