h1. Solutii preONI 2006 - Runda 1

(Categoria _Competitii_, autor(i) _Echipa info-arena_)

(Categoria _Competitii_, autor(i) _Echipa infoarena_)

Runda 1 a concursului preONI 2006 s-a incheiat. Acest articol contine solutiile oficiale pentru toate probleme propuse spre rezolvare, cat si comentarii referitoare la concurs.
Fiecare grupa a avut spre rezolvare 3 probleme, fiecare fiind catalogata de catre comisie ca fiind usoara, medie sau grea. Batalia pentru calificarea la finala este abia la inceput!

Pentru mai multe detalii despre finala, cat si despre concursul preONI 2006 si sponsorii nostri va rugam sa consultati "pagina preONI-2006":http://infoarena.ro/preONI-2006.

Pentru mai multe detalii despre finala, cat si despre concursul preONI 2006 si sponsorii nostri va rugam sa consultati "pagina preONI-2006":preONI-2006.

Rezultatele finale sunt disponibile la:

Cazul cu $3$ dreptunghiuri {$A$}, {$B$}, $C$ se rezolva similar. Cea mai simpla metoda este de a "vizualiza" formula facand un desen. Mai jos aveti un astfel de desen ajutator.

!http://infoarena.ro/preoni-2006/runda-1/solutii?action=download&file=reuniune.png!

!preoni-2006/runda-1/solutii?reuniune.png!

Asadar, obtinem formula:

* $Arie(A+B+C) = Arie(A) + Arie(B) + Arie(C) - Arie(AxB) - Arie(BxC) - Arie(AxC) + Arie(AxBxC)$

* $Arie(A+B+C) = Arie(A) + Arie(B) + Arie(C) - Arie(AxB) - Arie(BxC) - Arie(AxC) + Arie(AxBxC)$

(pentru perimetru formula este asemanatoare)

* $a{~1~} a{~2~} a{~3~} ... a{~n-2~} a{~n-1~} a{~n~}$
* $a{~n~} a{~n-1~} a{~n-2~} ... a{~3~} a{~2~} a{~1~}$

Asadar, prin adunarea cifrelor $a{~i~}$ si $a{~n-1+1~}$ se poate obtine un transport care va afecta cifrele anterioare. Deoarece sirul este parcurs de la extremitati spre interior $s$ va fi egal cu {$i$}, iar $d$ va fi egal cu {$n - i + 1$}, deci cifrele $v{~s~}$ si $v{~d~}$ sunt formate prin adunarea cifrelor $a{~i~}$ si {$a{~n-i+1~}$}.

Asadar, prin adunarea cifrelor $a{~i~}$ si $a{~n-i+1~}$ se poate obtine un transport care va afecta cifrele anterioare. Deoarece sirul este parcurs de la extremitati spre interior $s$ va fi egal cu {$i$}, iar $d$ va fi egal cu {$n - i + 1$}, deci cifrele $v{~s~}$ si $v{~d~}$ sunt formate prin adunarea cifrelor $a{~i~}$ si {$a{~n-i+1~}$}.

In parcurgerea sirului de la extremitati catre interior cazul ideal este atunci cand $v{~s~}$ este egal cu {$v{~d~}$}, caz in care cifra $v{~s~}$ nici nu primeste si nici nu trimite transport la cifrele aflate pe pozitii anterioare.
Un alt caz este cel in care $v{~s~}$ primeste transport prin adunarea cifrelor $a{~s+1~}$ si $a{~d-1~}$ (vezi schema de mai sus pentru a intelege acest lucru). In acest caz $v{~s~}$ este egal cu $v{~d~}+1$ si, pentru a tine cont de faptul ca pozitia $s+1$ a generat transport, adaugam la $v{~s+1~}$ valoarea {$10$}.

Un dreptunghi care apare in grila de puncte laticiale e marginit de doua drepte verticale la stanga si la dreapta, si de doua drepte orizontale in sus si in jos. Acum, daca vrem pentru patru drepte fixate sa stim cate dreptunghiuri marginesc ele, ne putem uita la urmatorul desen.

!http://infoarena.ro/preoni-2006/runda-1/solutii?action=download&file=drept.jpg!

!preoni-2006/runda-1/solutii?drept.jpg!

Daca dreptunghiul determinat de cele patru drepte are laturile $H$ si $W$ atunci un dreptunghi inscris va imparti laturile lui in bucatile {$A$}, $B$ si {$C$}, {$D$}. Acum folosind teorema lui Pitagora avem ca:

* $B^2^ + C^2^ = Verde^2^$
* $Galben^2^ + Verde^2^ = Roz^2^$
* $(A + B)^2^ = Rosu^2^$

* $(C * D)^2^ = Albastru^2^$

* $(C $-$ D)^2^ = Albastru^2^$

* $Rosu^2^ + Albastru^2^ = Roz^2^$

De aici avem ca {$(A + B)^2^ + (C * D)^2^ =A^2^ + B^2^ + C^2^ + D^2^$}, astfel obtinem {$AB = CD$}, dar {$B = H * A$}, iar {$D = W * C$} deci avem ca {$C^2^ * WC + A(H * A) = 0$}. Daca il fixam pe $A$ atunci trebuie sa rezolvam o ecuatie de gradul doi in necunoscuta {$C$}, solutia trebuie sa fie intreaga intre $0$ si {$W$}.

De aici avem ca {$(A + B)^2^ + (C - D)^2^ = A^2^ + B^2^ + C^2^ + D^2^$}, astfel obtinem {$AB = CD$}, dar {$B = H - A$}, iar {$D = W - C$} deci avem ca {$C^2^ - WC + A(H - A) = 0$}. Daca il fixam pe $A$ atunci trebuie sa rezolvam o ecuatie de gradul doi in necunoscuta {$C$}, solutia trebuie sa fie intreaga intre $0$ si {$W$}.

Astfel in $O(H)$ vom sti numarul de dreptunghiuri inscrise intr-un dreptunghi de dimensiuni {$H * W$}. Acest dreptunghi poate fi pus in $(N * H + 1) * (M * H + 1)$ locatii pe o grila de dimensiune {$N * M$}. Deci solutia are complexitate {$O(N*M^2^)$}, pentru fiecare dreptunghi de dimensiuni $1$ ≤ H ≤ N$ si $1 ≤ W ≤ M$ calculandu-se numarul de dreptunghiuri inscrise.

Astfel in $O(H)$ vom sti numarul de dreptunghiuri inscrise intr-un dreptunghi de dimensiuni {$H * W$}. Acest dreptunghi poate fi pus in $(N - H + 1) * (M - W + 1)$ locatii pe o grila de dimensiune {$N * M$}. Deci solutia are complexitate {$O(N*M^2^)$}, pentru fiecare dreptunghi de dimensiuni $1 ≤ H ≤ N$ si $1 ≤ W ≤ M$ calculandu-se numarul de dreptunghiuri inscrise.

O rezolvare de complexitate $O(N^2^*M^2^)$ in care se cautau solutiile ecuatiei printr-un for ar fi luat $60$ de puncte. Rezolvarea directa folosind ecuatia de gradul doi ia in jur de $80$ de puncte. Algoritmul poate fi optimizat la factorii constanti, de exemplu avem nevoie de functia radical care este cam inceata, precalculand-o obtinem o accelerare a vitezei, alta idee ar fi ca numarul de solutii cu $A ≤ H/2$ este egal cu numarul de solutii cu $A ≥ H * H/2$ si a treia idee de optimizare este ca numarul de dreptunghiuri inscrise intr-un dreptunghi de dimensiuni {$H$}, $W$ este acelasi cu numarul de dreptunghiuri inscrise intr-un dreptunghi de dimensiuni {$W$}, {$H$}.

O rezolvare de complexitate $O(N^2^*M^2^)$ in care se cautau solutiile ecuatiei printr-un for ar fi luat $60$ de puncte. Rezolvarea directa folosind ecuatia de gradul doi ia in jur de $80$ de puncte. Algoritmul poate fi optimizat la factorii constanti, de exemplu avem nevoie de functia radical care este cam inceata, precalculand-o obtinem o accelerare a vitezei, alta idee ar fi ca numarul de solutii cu $A ≤ H/2$ este egal cu numarul de solutii cu $A ≥ H - H/2$ si a treia idee de optimizare este ca numarul de dreptunghiuri inscrise intr-un dreptunghi de dimensiuni {$H$}, $W$ este acelasi cu numarul de dreptunghiuri inscrise intr-un dreptunghi de dimensiuni {$W$}, {$H$}.

h2. Zebughil

h3. (clasele 11-12, problema usoara)

Foarte multi concurenti au incercat sa rezolve aceasta problema folosind algoritmul Dijkstra cu heap-uri sau cu arbori de intervale. Aceasta solutie ar fi obtinut de la $70$ pana la $100$ de puncte (in cazul in care se optimiza algoritmul). O alta metoda de a obtine $100$ de puncte ar fi fost folosirea algoritmul Bellman Ford cu coada (vezi OJI 2004, problema "Lanterna":http://infoarena.ro/task/lanterna).

Foarte multi concurenti au incercat sa rezolve aceasta problema folosind algoritmul Dijkstra cu heap-uri sau cu arbori de intervale. Aceasta solutie ar fi obtinut de la $70$ pana la $100$ de puncte (in cazul in care se optimiza algoritmul). O alta metoda de a obtine $100$ de puncte ar fi fost folosirea algoritmul Bellman Ford cu coada (vezi OJI 2004, problema "Lanterna":http://infoarena.ro/problema/lanterna).

Solutia oficiala (care este de fapt si cea mai simpla si cea mai usor de implementat) are complexitate $O(N+M)$ ca timp si $O(N)$ ca memorie. Ea poate fi dedusa din modul de functionare a algoritmilor Dijkstra sau Bellman Ford. Asadar, conditile suficiente si necesare ca distantele minime date sa fie corecte sunt:

h3. (clasele 11-12, problema grea)

Problema a fost gandita sa rasplateasca pe "fanii info-arena" si anume pe aceea care au rezolvat corect problemele "Secventa 1":http://infoarena.ro/task/secventa, "Secventa 2":http://infoarena.ro/task/secv2, "Secventa 3":http://infoarena.ro/task/secv3. Pentru a trata circularitatea matricii o vom extinde intr-o matrice 2N*2M, lipind matrii initiale o copie la dreapta, sub ea, si la dreapta-jos.

Problema a fost gandita sa rasplateasca pe "fanii infoarena" si anume pe aceea care au rezolvat corect problemele "Secventa 1":http://infoarena.ro/problema/secventa, "Secventa 2":http://infoarena.ro/problema/secv2, "Secventa 3":http://infoarena.ro/problema/secv3. Pentru a trata circularitatea matricii o vom extinde intr-o matrice $2N*2M$, lipind matrii initiale o copie la dreapta, sub ea, si la dreapta-jos.

Rezolvarea acum se va baza pe cautarea binara a balansului maxim (idee folosita si la rezolvarea problemei "Secventa 3":http://infoarena.ro/task/secv3). Fie acesta {$X$}, trebuie sa verificam daca exista o submatrice cu balans cel putin {$X$}, adica:

Rezolvarea acum se va baza pe cautarea binara a balansului maxim (idee folosita si la rezolvarea problemei "Secventa 3":http://infoarena.ro/problema/secv3). Fie acesta {$X$}, trebuie sa verificam daca exista o submatrice cu balans cel putin {$X$}, adica:

* $Suma / Numar ≥ X$
* $Suma ≥ X*Numar$

Folosind cele scrise mai sus, putem observa ca, daca fiecare element nr din matricea intiala este inlocuit cu {$nr-X$}, atunci problema se reduce la a determina o submatrice din matricea modificata in care suma elementelor este {$≥ 0$}. Aceasta problema se poate rezolva determinand submatricea de suma maxima din matricea modificata, verificand apoi daca este {$≥ 0$}.

Asadar, problema s-a redus la a determina o submatrice de cel putin $R$ linii si $C$ coloane de suma maxima dintr-o matrice. Intai vom fixa $2$ linii la distanta cel putin $R$ si cel mult {$N$}, si vom calcula sumele pe coloane intre cele doua linii (acest lucru se poate face in $O(M)$ precalculand anumite sume la inceput). Pe vectorul de sume pe coloane obtinut va trebui sa rezolvam acum problema "secventei de suma maxima de lungime intre {$C$} si {$M$}" (necesara si la rezolvarea problemei "Secventa 3":http://infoarena.ro/task/secv3). Fie $A$ vectorul pe care vrem sa rezolvam acesta problema, si {$S{~i~} = A{~1~}+A{~2~}+...+A{~i~}$}. Pentru fiecare $i$ va trebui sa gasim un $j$ astfel incat:

Asadar, problema s-a redus la a determina o submatrice de cel putin $R$ linii si $C$ coloane de suma maxima dintr-o matrice. Intai vom fixa $2$ linii la distanta cel putin $R$ si cel mult {$N$}, si vom calcula sumele pe coloane intre cele doua linii (acest lucru se poate face in $O(M)$ precalculand anumite sume la inceput). Pe vectorul de sume pe coloane obtinut va trebui sa rezolvam acum problema "secventei de suma maxima de lungime intre {$C$} si {$M$}" (necesara si la rezolvarea problemei "Secventa 3":http://infoarena.ro/problema/secv3). Fie $A$ vectorul pe care vrem sa rezolvam acesta problema, si {$S{~i~} = A{~1~}+A{~2~}+...+A{~i~}$}. Pentru fiecare $i$ va trebui sa gasim un $j$ astfel incat:

* $S[i] - S[j]$ = maxim
* $i-M ≤ j ≤ i-C$