Diferente pentru winter-challenge-1/solutii intre reviziile #38 si #64

Nu exista diferente intre titluri.

Diferente intre continut:

h1. Solutii
In numele echipei Winter Challenge 2007 felicit toti participantii si le urez succes in viitoare confruntari. Totodata, tin sa multumesc lui Mugurel Ionut Andreica si lui Sorin Stancu-Mara pentru ca au acceptat sa propuna subiecte alaturi de mine. Nu in ultimul rand multumesc intregii "echipe infoarena":http://infoarena.ro/echipa-infoarena pentru suportul tehnic acordat si ii rog sa ma ierte daca i-am stresat (prea tare).
In numele echipei Winter Challenge 2007 felicit toti participantii si le urez succes in viitoare confruntari. Totodata, tin sa multumesc lui Mugurel Ionut Andreica si lui Sorin Stancu-Mara pentru ca au acceptat sa propuna subiecte alaturi de mine. Nu in ultimul rand multumesc intregii "echipe infoarena":echipa-infoarena pentru suportul tehnic acordat si ii rog sa ma ierte daca i-am stresat (prea tare).
Mult noroc in continuare,
Bogdan A. Stoica
h3. problema usoara, clasele 9-10
Se observa ca figura se obtine dintr-un patrat de latura $radical(N)$, la care se mai adauga niste patratele, solutia fiind $4*radical(N)$ (pentru $N$ patrat perfect) sau $4*(radical(N)+1)$ ({$-2$}, dupa caz :p).
Vom nota cu P{~k~}, perimetrul minim al figurii ce contine $k$ patratele de latura unitate. In mod evident, acesta depinde numai de patratelele ce formeaza marginea figurii.
Vom trata intai cazul in care $N$ este patrat perfect pornind de la $N = 1$, cu $P{~1~} = 4$. Pentru $N = 4$, construind toate figurile posibile se observa ca cea de perimetru minim are forma unui patrat cu latura $2$, deci $P{~4~} = 4*2 = 8$. Continuand procedeul, se demonstreaza cu ajutorul principiului inducitei matematice ca $P{~t~} = 4*[radical(t)]$ (cu $[x]$ s-a notat partea intreaga a lui $x$), oricare ar fi $t$ patrat perfect.
Pentru al doilea caz, cel in care $N$ nu este patrat perfect, figura noastra porneste tot de la un patrat de latura $[radical(N)]$. Este evident faptul ca pentru ca $P{~N~}$ sa fie minim, trebuie sa avem cat mai putine patratele (pe margine) carora li se aduna mai mult de o latura la perimetru (cu alte cuvinte trebuie sa avem cat mai putine patratele care sa formeze colturi). Va trebui, deci, sa adaugam pe marginile patratului format $N-[radical(N)]*[radical(N)]$ patratele. Astfel solutia devine $4*[radical(N)]$ pentru $N$ patrat perfect, $4*[radical(N)]+2$ pentru cazul in care acoperim maxim o latura cu patratele sau $4*[radical(N)]+4$ pentru cazul in care acoperim maxim 2 laturi cu patratele.
O solutie care calcula aceste valori in O({$N$}) nu ar fi obtinut punctaj maxim.
h2. Mall
h3. problema medie, clasele 9-10
Calculam $A[i, j]$ = castigul maxim pe care-l obtine Varu daca repartizeaza $j$ ingrijitori primelor $i$ firme, unde
$A[i, j]$ = $maxim(A[l, j-k])$ ({$0 < l < i$}, {$0 &le; k &le; j$}).
$A[i, j]$ = $maxim(A[l, j-k]+Castig[l, k])$ ({$0 < l < i$}, {$0 &le; k &le; j$}), unde $Castig[i, j]$ = castigul pe care-l obtine Varu de la firma $i$ daca acesteia ii repratizaza exact $j$ ingrijitori.
O solutie care calcula in O({$N^4^$}) aceasta recurenta ar fi obtinut $16$ puncte.
O solutie care calcula in O({$N^3^$}), folosind matricea $V[i, j]$ = $maxim(A[k, j])$ ({$0 <  k < i$}), obtinea $32$ de puncte.
O solutie care calcula in O({$N^3^$}), folosind matricea $V[i, j]$ = $maxim(A[k, j]+Castig[k, j])$ ({$0 <  k < i$}), obtinea $32$ de puncte.
O solutie care calcula in O({$N^2^$}), folosind un deque ce calcula in O({$1$}) maximul (pentru linia $i$ si coloana $j$) dintre $V[i, 1]$, $V[i, 2]$, ..., $V[i, j-1]$, obtinea $100$ de puncte.
h2. Smen
h3. problema grea, clasele 9-10 - problema medie, clasele 11-12
Incepem prin a normaliza toate numerele din sir si pe $A$ si $B$, adunand tuturor valoarea $200$. Astfel vom lucra numai cu numere pozitive. Apoi problema se rezolva prin programare dinamica. Sortam in ordine crescatoare elementele si apoi calculam $A[i, j, k]$ = numarul minim de operatii ce se efectueaza asupra primelor $i$ numere a.i. sa obtinem exact $j$ elemente distincte iar ultimul element sa nu depaseasca valoarea $k$.
$A[i, j, k]$ se poate obtine ca fiind maximul dinntre:
$A[i, j, k]$ se poate obtine ca fiind maximul dintre:
# $A[i-1, j, k-1]$ + $|Val_initiala[i]-k|$ (daca vrem ca valoarea initiala a celui de-al $i$-lea element sa fie $k$, dar sa nu-mi creeze un alt element distinct).
# $A[i-1, j-1, k-1]+|Val_initiala[i]-k|$ (daca vrem ca valoarea initiala a celui de-al $i$-lea element sa fie $k$ si sa-mi creez inca un element dinstinct)
# $A[i-1, j, k-1]$ (nu cresc nici valoarea elementului $i$, nici numarul de elemente distincte)
Pentru reconstituire vom lucra cu o matrice $B[i, j, k]$ care ia valori din multimea {$0$, $1$, $2$}, semnificand conditia din care a provenit starea ({$i$}, {$j$}, {$k$}). Se observa ca aceasta solutie ar fi obtinut foloseste foarte multa memorie (O({$N*K*$}({$B$}-{$A$})) si ar fi obtinut doar $40%$ din punctaj.
Pentru reconstituire vom lucra cu o matrice $B[i, j, k]$ care ia valori din multimea {$0$, $1$, $2$}, semnificand conditia din care a provenit starea ({$i$}, {$j$}, {$k$}). Se observa ca aceasta solutie foloseste foarte multa memorie (O({$N*K*$}({$B$}-{$A$})) si ar fi obtinut doar $40%$ din punctaj.
Solutia $100$ de puncte incepe prin a observa ca, la un pas, nu sunt folosite decat "linia" curenta si "linia" anterioara din matricea $A$. Pentru reconstituire se poate folosi urmatorul smen: retinem din $14$ in $14$ "linii" informatiile din matricea $A$ (cea de la prima solutie), adica $R[1, j, k]$ =  {$A[1, j, k]$} ({$1 &le; j &le; K$} si {$A+200 &le; k &le; B+200$}), $R[2, j, k]$ = $A[15, j, k]$ ({$1 &le; j &le; K$} si {$A+200 &le; k &le; B+200$}), $R[3, j, k]$ = $A[29, j, k]$ ({$1 &le; j &le; K$} si {$A+200 &le; k &le; B+200$}), etc. Dupa ce am completat matricea $R$, reluam dinamica de la coada la cap si ne vom folosi doar de matricea $R$. Astfel la pasul $i$ vom reconstitui doar liniile care se afla intre liniile $R[i, j, k]$ si $R[i-1, j, k]$ ({$1 &le; j &le; K$} si {$A+200 &le; k &le; B+200$}), adica intre ({$i-1$})*{$14+1$} si $i*14+1$ in matricea de la prima solutie. Astfel o sa avem o memorie de O({$14*K*$}({$B$}-{$A$})).
h3. problema usoara, clasele 11-12
In ciuda proprietatii un pic nenaturala care priveste valoarea fricii dintr-o intersectie, problema se reduce la aflarea fluxul maxim avand orasul $1$ ca sursa si orasul $N$ ca destinatie. Pentru a realiza acest lucru vom logaritma (in baza $2$, $e$ sau $10$) costurile muchiilor ce se dau in fisierul de intrare. Dintre toate aceste noi costuri o vom lua pe cea maxima ({$vmax$}). Algoritmul va fi urmatorul:
In ciuda proprietatii un pic nenaturale care priveste valoarea fricii dintr-o intersectie, problema se reduce la aflarea fluxului maxim avand orasul $1$ ca sursa si orasul $N$ ca destinatie. Pentru realizarea acestui lucru vom logaritma (in baza $2$, $e$ sau $10$) costurile muchiilor ce se dau in fisierul de intrare. Dintre toate aceste noi costuri o vom lua pe cea maxima ({$vmax$}). Algoritmul va fi urmatorul:
# vom trimite frica (din orasul $1$) cu o valoare $V$ (initial, $V$ = $vmax$) pana cand frica nu va mai putea ajunge la destinatie.
# injumatatim pe $V$ si reluam algoritmul de la pasul $1$.
Aceasta metoda poarta denumirea de "Flux maxim prin scalare". O alta abordare care ar fi mers la fel de bine este cea folosind algoritmul de flux maxim Ford Fulkerson.
 
h2. Doipe
h3. problema grea, clasele 11-12
	Vom calcula $P[i, j]$ = numarul de permutari ale multimii {{$1$},{$2$},..,{$i$}} care respecta primele $i-1$ relatii ale sirului de relatii si in care ultimul numar al permutarii este numarul $j$. In mod evident, rezultatul dorit va fi dat de suma $P[N, 1]$ + $P[N, 2]$ + ... + $P[N, N]$.
	Prima solutie corecta este de complexitate O(N*2^N^). Se calculeaza o matrice $P[i, R]$ = numarul de permutari cu $i$ elemente, care respecta sirul de relatii $R$ ({$R$} este un numar binar de $i - 1$ biti, care codifica un sir de relatii). Putem calcula aceste valori pe baza valorilor calculate pentru $P[i - 1, R']$, variind pozitia in care este asezat in cadrul permutarii cel de-al $i$-lea element. Aceasta solutie nu se incadreaza, insa, nici in limita de timp, nici in cea de memorie.
	Ideea solutiei de punctaj maxim este urmatoarea: Vom calcula $P[i, j]$ = numarul de permutari ale multimii {{$1$},{$2$},..,{$i$}} care respecta primele $i-1$ relatii ale sirului de relatii si in care ultimul numar al permutarii este numarul $j$. In mod evident, rezultatul dorit va fi dat de suma $P[N, 1]$ + $P[N, 2]$ + ... + $P[N, N]$.
	Pentru calculul lui $P[i, j]$ vom observa ca, eliminand numarul $j$ din permutare, obtinem $i-1$ numere distincte care pot fi renumerotate pentru a forma o permutare a multimii {{$1$},{$2$},..,{$i-1$}}. Mai exact, orice numar $x$ mai mare decat $j$ este renumerotat cu valoarea $x-1$. In conditiile acestei renumerotari, avem urmatoarele $2$ cazuri:
* daca relatia $i-1$ este "$<$", atunci $P[i, j]$ = $P[i-1, 1]$ + $P[i-1, 2]$ + ... + $P[i-1, j-1]$

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.