Diferente pentru preoni-2006/runda-1/solutii intre reviziile #19 si #26

Nu exista diferente intre titluri.

Diferente intre continut:

* $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$}.
* $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$}.
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$}.
h3. (clasele 11-12, problema grea)
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.
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/problema/secv3). Fie acesta {$X$}, trebuie sa verificam daca exista o submatrice cu balans cel putin {$X$}, adica:

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.