Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2006-11-16 10:34:12.
Revizia anterioară   Revizia următoare  

Solutiile oficiale pentru Concursul "de incalzire"

(Creat de silviugSilviu-Ionut Ganceanu silviug la data de 2004-11-15 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.

Incep prin a recunoaste faptul ca setul de probleme a fost unul foarte dur, comparabil cu unul de la nationale, chiar baraje. Pe viitor vom incerca sa facem concursurile mai gradate. Reversul medaliei este ca aveti acum probleme dure cu care sa va pregatiti si la care voi prezenta idei de solutie avand astfel ce invata! Nu voi incerca sa dau solutii foarte explicite, ci doar voi schita ideile de baza deoarece este important sa incercati sa intelegi si sa implementati singuri solutiile! ;)

Clasele 9-10

Coins

Primul fapt care trebuie observat este numarul destul de mic al starilor de joc si anume 222 = 4.194.304. Recomand cartea doamnei Cerchez 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 * 222) = O(1) :).

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) (x1, y1). Al doilea va fi (x2, y1), al treilea (x2, y2), al patrulea (x3, y2) .. penultimul (xk, yk-1), ultimul (xk, yk) (care va coincide cu un alt punct (xp, yp), p < k). Se observa ca poligonul rosu va avea ca centru de greutate punctul ((xpxp+1...+xk-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).

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 2N-1. Raspunsul va fi A[2N-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(2N * L * N). Se poate optimiza la O(2N * L) folosind operatii pe biti.

Clasele 11-12

Xor Max

Fie X[i] = A1 xor A2 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).

Boom

Vom construi un graf din cele 2N 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 2N-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).

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.