Diferente pentru preoni-2007/runda-finala/solutii intre reviziile #22 si #28

Nu exista diferente intre titluri.

Diferente intre continut:

==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 $i < j$: $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.
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
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
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^.
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)

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.