Diferente pentru warm-up-2004/solutii intre reviziile #6 si #20

Nu exista diferente intre titluri.

Diferente intre continut:

h1. Solutiile oficiale pentru Concursul "de incalzire"
(Creat de ==user(user="silviug" type="tiny")== la data de _2004-11-15_ categoria _Competitii_, autor(i) _Mircea Pasoi_)
(Categoria _Competitii_, autor(i) _Mircea Pasoi_)
In acest articol voi prezenta cateva idei de rezolvare pentru problemele din concursul "de incalzire" de la clasele 9-10 si 11-12.
h2. Clasele 9-10
h3. Coins
h3. **Coins**
Primul fapt care trebuie observat este numarul destul de mic al starilor de joc si anume {$2^22^ = 4.194.304$}. Recomand "cartea doamnei Cerchez":http://www.liis.ro/%7eema/ despre arbori pentru a citi capitolul despre Arbori de Joc. Ideea principala este ca se exploreaza intregul arbore de joc format de starile tablei de $22$ de patralele si se retine intr-un vector boolean pentru fiecare configuratie daca jucatorul care incepe cu acea configuratie castiga sau nu. Astfel, se va raspunde la fiecare din cele $N$ teste in $O(1)$ dupa preprocesarea in $O(22 * 2^22^) = O(1)$ :).
h3. Zaharel
h3. **Zaharel**
Solutia se bazeaza pe proprietatea foarte importanta (subliniata si in enunt) ca pe fiecare linie exista un punct rosu si pe fiecare coloana un punct albastru. Presupunem ca tinem o lista cu puncte. Initial bagam un punct rosu oarecare. Pe coloana punctului rosu respectiv exista un punct albastru (din proprietatea de mai sus). Inseram acel punct albastru in lista. Pe linia punctul albastru va exista un punct rosu , pe care il vom insera in lista. Repetand acest procedeu vom ajunge la un moment dat la un punct care a mai fost in lista ,deci la un ciclu (acest lucru este evident deoarece numarul punctelor este finit). Punctele rosii de pe ciclu vor reprezenta primul poligon, iar punctele albastre al doilea poligon. Este evident ca vor avea acelasi numar de varfuri, vom arata in continuare ca au si acelasi centru de greutate. Fie primul punct (acela rosu) ({$x{~1~}, y{~1~}$}). Al doilea va fi ({$x{~2~}, y{~1~}$}), al treilea ({$x{~2~}, y{~2~}$}), al patrulea ({$x{~3~}, y{~2~}$}) .. penultimul ({$x{~k~}, y{~k-1~}$}), ultimul ({$x{~k~}, y{~k~}$}) (care va coincide cu un alt punct ({$x{~p~}, y{~p~}$}), {$p < k$}). Se observa ca poligonul rosu va avea ca centru de greutate punctul ({$(x{~p~} +x{~p+1~}+...+x{~k-1~})/(k-p)$}, (y_p+y_p+1+...+y_k-1)/k-p), iar cel albastru ((x_p+1+x_p+2+...+x_k)/k-p, (y_p+1+y_p+2+...+y_k)/k-p), care coincid deoarece (x_p,y_p) = (x_k, y_k).
Solutia se bazeaza pe proprietatea foarte importanta (subliniata si in enunt) ca pe fiecare linie exista un punct rosu si pe fiecare coloana un punct albastru. Presupunem ca tinem o lista cu puncte. Initial bagam un punct rosu oarecare. Pe coloana punctului rosu respectiv exista un punct albastru (din proprietatea de mai sus). Inseram acel punct albastru in lista. Pe linia punctul albastru va exista un punct rosu , pe care il vom insera in lista. Repetand acest procedeu vom ajunge la un moment dat la un punct care a mai fost in lista ,deci la un ciclu (acest lucru este evident deoarece numarul punctelor este finit). Punctele rosii de pe ciclu vor reprezenta primul poligon, iar punctele albastre al doilea poligon. Este evident ca vor avea acelasi numar de varfuri, vom arata in continuare ca au si acelasi centru de greutate. Fie primul punct (acela rosu) ({$x{~1~}, y{~1~}$}). Al doilea va fi ({$x{~2~}, y{~1~}$}), al treilea ({$x{~2~}, y{~2~}$}), al patrulea ({$x{~3~}, y{~2~}$}) .. penultimul ({$x{~k~}, y{~k-1~}$}), ultimul ({$x{~k~}, y{~k~}$}) (care va coincide cu un alt punct ({$x{~p~}, y{~p~}$}), {$p < k$}). Se observa ca poligonul rosu va avea ca centru de greutate punctul ({$(x{~p~}&#0043;x{~p+1~}&#0043;...&#0043;x{~k-1~})/(k-p)$}, {$(y{~p~}&#0043;y{~p+1~}&#0043;...&#0043;y{~k-1~})/(k-p)$}), iar cel albastru {$(x{~p+1~}&#0043;x{~p+2~}&#0043;...&#0043;x{~k~})/(k-p)$}, {$(y{~p+1~}&#0043;y{~p+2~}&#0043;...&#0043;y{~k~})/(k-p)$}), care coincid deoarece ({$x{~p~},y{~p~}$}) = ({$x{~k~}, y{~k~}$}).
h3. Sobo
h3. **Sobo**
Problema se rezolva prin programare dinamica. Se retine in A[i] = costul minim in cazul cel mai defavorabil pentru a recunoaste sobolanul inteligent din multimea de sobolani cu numerele de ordine pozitiile bitilor de 1 in reprezentarea binara a lui i. Astfel, A va avea valori pentru i intre 0 si 2^N-1. Raspunsul va fi A[2^N-1]. Este evident ca graful format de aceste stari este aciclic deoarece fiecare raspuns imparte o multime in doua multimi mai mici. Astfel pentru a calcula un A[i] vom lua fiecare raspuns care imparte in doua multimi nevide multimea curenta, vom vedea in care multime costul este mai mare (cazul cel mai defavorabil) , adaugam pretul raspunsului si actualizam in A[i] daca valoarea aceasta este mai mica decat cea curenta (sa nu uitam ca vrem cost minim in cazul cel mai defavorabil). Cea mai simpla metoda de a implementa acest mecanism este cu memoizare. Complexitatea finala O(2^N * L * N). Se poate optimiza la O(2^N * L) folosind operatii pe biti.
Problema se rezolva prin programare dinamica. Se retine in $A{~i~}$ = costul minim in cazul cel mai defavorabil pentru a recunoaste sobolanul inteligent din multimea de sobolani cu numerele de ordine pozitiile bitilor de $1$ in reprezentarea binara a lui {$i$}. Astfel, $A$ va avea valori pentru $i$ intre $0$ si {$2^N^-1$}. Raspunsul va fi {$A{~2^N^-1~}$}. Este evident ca graful format de aceste stari este aciclic deoarece fiecare raspuns imparte o multime in doua multimi mai mici. Astfel pentru a calcula un $A{~i~}$ vom lua fiecare raspuns care imparte in doua multimi nevide multimea curenta, vom vedea in care multime costul este mai mare (cazul cel mai defavorabil) , adaugam pretul raspunsului si actualizam in $A{~i~}$ daca valoarea aceasta este mai mica decat cea curenta (sa nu uitam ca vrem cost minim in cazul cel mai defavorabil). Cea mai simpla metoda de a implementa acest mecanism este cu memoizare. Complexitatea finala {$O(2^N^ * L * N)$}. Se poate optimiza la {$O(2^N^ * L)$} folosind operatii pe biti.
h2. Clasele 11-12
h3. Xor Max
h3. **Xor Max**
Fie X[i] = A[1] xor A[2] xor ... A[i]. Pentru fiecare X[i] vom incearca sa gasim un X[j] (j < i) astfel incat X[i] xor X[j] sa fie maxim. Pentru a realiza aceasta operatie eficient vom mentine un "trie" (vezi in CLR varianta in romana la pagina 223 - capitolul "Arbori binari de cautare" problema 13-2 - se asemana cu "suffix trees/tries" doar ca vom lucra cu siruri binare). Fie b numarul maxim de biti pe care ii are un element din vector. Vom realiza operatia de gasire a lui X[j] in O(b). Structura de date mentionata mai sus va memora sirurile de biti formate de vectorul X. Vom parcurge bitii lui X[i] de la cel mai semnificativ la cel mai nesemnificativ. Astfel daca bitul curent este 1, vom incerca sa gasim un sir de biti care are acest bit 0 (pentru a maxima xor-ul), iar daca bitul curent este 0 vom proceda invers. Complexitatea finala a algoritmului este O(N*b).
Fie {$X{~i~} = A{~1~} xor A{~2~} xor ... xor A{~i~}$}. Pentru fiecare $X{~i~}$ vom incearca sa gasim un $X{~j~}$ ({$j < i$}) astfel incat $X{~i~} xor X{~j~}$ sa fie maxim. Pentru a realiza aceasta operatie eficient vom mentine un *trie* (vezi in CLR varianta in romana la pagina 223 - capitolul "Arbori binari de cautare" problema 13-2 - se asemana cu "suffix trees/tries" doar ca vom lucra cu siruri binare, nu cu litere). Fie $b$ numarul maxim de biti pe care ii are un element din vector. Vom realiza operatia de gasire a lui $X{~j~}$ in {$O(b)$}. Structura de date mentionata mai sus va memora sirurile de biti formate de vectorul {$X$}. Vom parcurge bitii lui $X{~i~}$ de la cel mai semnificativ la cel mai nesemnificativ. Astfel daca bitul curent este {$1$}, vom incerca sa gasim un sir de biti care are acest bit $0$ (pentru a maxima xor-ul), iar daca bitul curent este $0$ vom proceda invers. Complexitatea finala a algoritmului este {$O(N*b)$}.
h3. Boom
h3. **Boom**
Vom construi un graf din cele 2^N stari posibile. Prin stare intelegem un numar binar in care bitii de 1 reprezinta locurile in care s-ar putea afla sobolanul. Pentru fiecare astfel de nod, exista M muchii la alte noduri, care se obtin aplicand bomba asupra pozitiilor si avansarea pozitiilor ramase. Deoarece muchiile au costuri numere naturale, iar graful nu este neaparat aciclic vom aplica algoritmul Dijkstra, pentru a determina drumul de cost minim de la nodul 2^N-1 la nodul 0. Pentru a se incadra in timp era necesara implementarea cozii de prioritate cu heap-uri. Complexitate finala O(2^N * N * M).
Vom construi un graf din cele $2^N^$ stari posibile. Prin stare intelegem un numar binar in care bitii de $1$ reprezinta locurile in care s-ar putea afla sobolanul. Pentru fiecare astfel de nod, exista $M$ muchii la alte noduri, care se obtin aplicand bomba asupra pozitiilor si avansarea pozitiilor ramase. Deoarece muchiile au costuri numere naturale, iar graful nu este neaparat aciclic vom aplica algoritmul Dijkstra, pentru a determina drumul de cost minim de la nodul $2^N^-1$ la nodul {$0$}. Pentru a se incadra in timp era necesara implementarea cozii de prioritate cu heap-uri. Complexitate finala {$O(2^N^ * N * M)$}.
h3. PetSoft
h3. **PetSoft**
In fiecare nod din arbore vom retine doua valori A[i][0] = costul minim pentru a cupla subarborele cu radacina in i, fara a cupla nodul i cu cineva, si A[i][1] acelasi lucru, dar cupland nodul i cu cineva. Pentru a calcula aceste valori in fiecare nod, luam numerele de ordine a fiilor , le sortam si aplicam o alta dinamica pentru a obtine echipe cu cost maxim. Astfel determinam A[i][0]. Pentru a calcula A[i][1], inseram si nodul i in lista fiilor, sortam din nou si aplicam aceeasi dinamica (atentie la detalii de implementare!). Dinamica se face astfel: retinem in C[i][j] = costul maxim pentru a forma echipe de cost maxim cu valorile de pe pozitiile i, i+1...j-1, j. Este evident ca C[i][j] se obtine din C[i+1][j], C[i][j-1] si C[i+1][j-1]. Complexitatea finala este O(N^2).
 
References
 
Visible links
1.
In fiecare nod din arbore vom retine doua valori $A{~i, 0~}$ = costul maxim pentru a cupla subarborele cu radacina in {$i$}, fara a cupla nodul $i$ cu cineva, si $A{~i, 1~}$ acelasi lucru, dar cupland nodul $i$ cu cineva. Pentru a calcula aceste valori in fiecare nod, luam numerele de ordine a fiilor, le sortam si aplicam o alta dinamica pentru a obtine echipe cu cost maxim. Astfel determinam {$A{~i, 0~}$}. Pentru a calcula {$A{~i, 1~}$}, inseram si nodul $i$ in lista fiilor, sortam din nou si aplicam aceeasi dinamica (atentie la detalii de implementare!). Dinamica se face astfel: retinem in $C{~i, j~}$ = costul maxim pentru a forma echipe de cost maxim cu valorile de pe pozitiile {$i, i+1 ... j-1, j$}. Este evident ca $C{~i, j~}$ se obtine din {$C{~i+1, j~}$}, $C{~i, j-1~}$ si {$C{~i+1, j-1~}$}. Complexitatea finala este {$O(N^2^)$}.

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.