Solutiile oficiale pentru Concursul "de incalzire"

(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 ((xp+xp+1+...+xk-1)/(k-p), (yp+yp+1+...+yk-1)/(k-p)), iar cel albastru (xp+1+xp+2+...+xk)/(k-p), (yp+1+yp+2+...+yk)/(k-p)), care coincid deoarece (xp,yp) = (xk, yk).

Sobo

Problema se rezolva prin programare dinamica. Se retine in Ai = 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 A2N-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 Ai 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 Ai 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 Xi = A1 xor A2 xor ... xor Ai. Pentru fiecare Xi vom incearca sa gasim un Xj (j < i) astfel incat Xi xor Xj 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 Xj in O(b). Structura de date mentionata mai sus va memora sirurile de biti formate de vectorul X. Vom parcurge bitii lui Xi 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(2N * N * M).

PetSoft

In fiecare nod din arbore vom retine doua valori Ai, 0 = costul maxim pentru a cupla subarborele cu radacina in i, fara a cupla nodul i cu cineva, si Ai, 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 Ai, 0. Pentru a calcula Ai, 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 Ci, j = costul maxim pentru a forma echipe de cost maxim cu valorile de pe pozitiile i, i+1 ... j-1, j. Este evident ca Ci, j se obtine din Ci+1, j, Ci, j-1 si Ci+1, j-1. Complexitatea finala este O(N2).