h1. Solutii Happy Coding 3

Concursurile Happy Coding par sa fie singurele care nu au avut parte de descrieri ale solutiilor problemelor propuse.. Desi cu intarziere, intentionez sa remediez aceasta situatie. Aceasta pagina este "under construction" momentan.
 
 
 

O parte din problemele date in cadrul acestui concurs (cele propuse de Mugurel Ionut Andreica) au fost folosite pentru a selecta echipele care au reprezentat Universitatea Politehnica Bucuresti la etapa regionala sud-est europeana a concursului ACM ICPC, in anul 2006.

h2. 'AVD':problema/avd

(toc)*{text-align:center} *Lista de probleme*
* 'AVD':happy-coding-2006/solutii#nr1
* 'CT':happy-coding-2006/solutii#nr2
* 'Swap':happy-coding-2006/solutii#nr3
* 'Obj':happy-coding-2006/solutii#nr4
* '1expr':happy-coding-2006/solutii#nr5
* 'Cc':happy-coding-2006/solutii#nr6
* 'Joc3':happy-coding-2006/solutii#nr7
* 'Geometry':happy-coding-2006/solutii#nr8
* 'Itree':happy-coding-2006/solutii#nr9
* 'Hprob':happy-coding-2006/solutii#nr10
* 'Arbore de cicluri':happy-coding-2006/solutii#nr11
* 'Gandaci Java':happy-coding-2006/solutii#nr12
* 'Roy-Floyd':happy-coding-2006/solutii#nr13
* 'Biomech':happy-coding-2006/solutii#nr14
* 'Expresii min-max':happy-coding-2006/solutii#nr15
* 'Noroc':happy-coding-2006/solutii#nr16
 
h2(#nr1). 'AVD':problema/avd

Cea mai simpla solutie consta in generarea tuturor submultimilor de muchii pe care le eliminam. Ce ramane este o reuniune de componente conexe, care defineste fiecare cate o partitie. Dintre toate cele $2^N-1^$ partitii generate, le pastram pe cele unice si impartim acest numar la numarul total de partitii (care poate fi generat si el prin backtracking sau folosind programare dinamica).
O solutie mai laborioasa consta in generarea fiecarei partitii (putin peste $100$, pt $N=13$) si, pentru fiecare astfel de partitie (care are, sa presupunem $K$ elemente), calcularea urmatoarelor valori: $ok[i][j][S] = 1$ sau $0$ , reprezentand daca e posibil sau nu sa se "acopere" elementele partitiei corespunzatoare starii $S$ ( $S$ e un numar pe $K$ biti), folosind nodurile din subarborele lui $i$ si ramanand $j$ noduri, inclusiv nodul $i$, intr-o componenta conexa pe care nu o "potrivim" peste vreun element al partitiei (si care poate fi eventual extinsa ulterior de catre un stramos al lui $i$); o valoare $j=0$ indica ca au fost folosite toate nodurile din subarborele lui $i$, inclusiv $i$, pentru a genera componente conexe care se "potrivesc" peste elemente ale partitiei. Aceste valori se calculeaza folosind programare dinamica de tip rucsac pe arbore, in functie de valorile calculate pentru fii (valori de tipul $ok[fiu][j'][S']$, cu $j' < j$ si $S'$ inclus in $S$). Daca $ok[ 1 ][ 0 ][2^K^-1]$ are valoarea $1$, atunci se poate genera o impartire in componente conexe a arborelui, ce corespunde partitiei respective.

h2. 'CT':problema/ct

h2(#nr2). 'CT':problema/ct

Se fixeaza radacina arborelui intr-un nod (sa zicem nodul $1$). Pentru fiecare din cele $K$ perechi de orase se calculeaza $LCA$-ul (lowest common ancestor = cel mai apropiat stramos comun). Se poate folosi orice metoda eficienta de determinarea a $LCA$-ului: de exemplu, pentru fiecare nod $i$ se pot memora $O(logN)$ valori, $stramos[i][j]$, reprezentand stramosul aflat cu $2^j^$ nivele mai sus in arbore (cu $j$ incepand de la $0$), iar cu aceste valori, $LCA$-ul a oricare $2$ noduri se poate determina in timp $O(logN)$. Se sorteaza apoi $LCA$-urile tuturor perechilor, in functie de nivelul din arbore ({$LCA$}-urile de pe un nivel mai jos aflandu-se inaintea celor de pe un nivel mai ridicat). In continuare, vom parcurge $LCA$-urile in ordinea sortata. Pentru a rezolva problema, avem acum $2$ posibilitati:
* Vom renumerota nodurile conform unei parcurgeri in adancime (DF), astfel incat toate nodurile din subarborele oricarui nod $i$ sa formeze un interval de numere consecutive. Apoi vom tine un arbore de intervale pentru aceste numere. In arborele de intervale vom memora daca un nod (identificat prin numarul asociat lui din cadrul parcurgerii DF) a fost eliminat din arbore sau nu. Pentru fiecare $LCA$, in ordinea precizata mai sus, vom verifica daca cel putin unul din cele $2$ noduri al caror $LCA$ este a fost deja eliminat din arbore. Daca nu a fost eliminat nici unul, vom selecta $LCA$-ul acestora ca oras ce va fi bombardat si vom marca ca intreg intervalul de numere corespunzator subarborelui $LCA$-ului a fost eliminat din arbore. Complexitatea acestei variante este $O(K*logN)$, plus complexitatea determinarii celor $K LCA$-uri (care ar putea fi $O(N*logN + K*logN))$.
* A doua varianta nu mai necesita o renumerotare si utilizarea unui arbore de intervale, insa mentine ideea de a memora pentru fiecare nod daca acesta a fost eliminat sau nu din arbore. Parcurgem $LCA$-urile si verificam pentru fiecare daca cel putin unul din cele $2$ noduri din perechea de noduri pentru care a fost calculat $LCA$-ul a fost deja eliminat din arbore. Daca nici unul din cele $2$ noduri nu a fost eliminat din arbore, vom selecta $LCA$-ul ca fiind oras ce va fi bombardat si apoi vom efectua o parcurgere DF pentru a marca toate nodurile din subarborele acestuia ca fiind eliminate. Optimizarea importanta este ca daca, in cadrul acestei parcurgeri, intalnim un nod deja marcat anterior ca fiind eliminat, nu vom parcurge subarborele acestuia. In felul acesta, fiecare nod este marcat ca find eliminat cel mult o singura data, iar complexitatea acestei etape este $O(K + N)$.

h2. 'Swap':problema/swap

h2(#nr3). 'Swap':problema/swap
 
Vom construi o permutare $P$ a multimii ${1,...,N}$, asociata primului sir ({$N$} este lungimea fiecaruia din cele $2$ siruri). Pentru fiecare caracter $x$ din primul sir, vom calcula al catelea caracter de tipul respectiv este in cadrul primului sir (acest lucru se poate realiza usor in $O(N)$). Apoi vom construi permutarea $P$ in felul urmator: pentru fiecare caracter $x$, pentru care stim ca este al $y$-lea caracter de tipul sau si care se afla pe pozitia $i$, vom seta valoarea lui $P[i]$ ca fiind egala cu pozitia pe care se afla cel de-al $y$-lea caracter egal cu $x$ din cel de-al doilea sir. Numarul de operatii $swap$ necesare este egal cu numarul de inversiuni ale permutarii $P$. Acest numar poate fi determinat eficient in mai multe feluri: folosind mergesort (sortare prin interclasare), arbori de intervale, arbori indexati binar, impartirea in grupe de cate<tex>\sqrt N</tex> etc.

Vom construi un o permutare $P$ a multimii ${1,...,N}$, asociata primului sir ({$N$} este lungimea fiecaruia din cele $2$ siruri). Pentru fiecare caracter $x$ din primul sir, vom calcula al catelea caracter de tipul respectiv este in cadrul primului sir (acest lucru se poate realiza usor in $O(N)$). Apoi vom construi permutarea $P$ in felul urmator: pentru fiecare caracter $x$, pentru care stim ca este al $y$-lea caracter de tipul sau si care se afla pe pozitia $i$, vom seta valoarea lui $P[i]$ ca fiind egala cu pozitia pe care se afla cel de-al $y$-lea caracter egal cu $x$ din cel de-al doilea sir. Numarul de operatii $swap$ necesare este egal cu numarul de inversiuni ale permutarii $P$. Acest numar poate fi determinat eficient in mai multe feluri: folosind mergesort (sortare prin interclasare), arbori de intervale, arbori indexati binar, impartirea in grupe de cate<tex>\sqrt N</tex> etc.

h2(#nr4). 'Obj':problema/obj

h2. 'Obj':problema/obj

Vom porni de la o solutie avand complexitatea $O(N*K)$. Vom calcula $win[ 0 ][ i ]$ = $1$, daca gramada contine $i$ obiecte, castigatorul trebuie sa stranga un numar par de obiecte, iar jucatorul aflat la mutare are strategie sigura de castig, sau $0$, daca jucatorul aflat la mutare nu are strategie sigura de castig. $win[ 1 ][ i ]$ va reprezenta acelasi lucru, cu diferenta ca cel care castiga jocul este cel care aduna un numar impar de obiecte. Avem $win[ 0 ][ 0 ] = 1$ si $win[ 1 ][ 0 ] = 0$. Pentru fiecare valoare a lui $i$ de la $1$ la $N$, variem numarul de obiecte pe care le ia jucatorul aflat la mutare si, in functie de paritatea acestui numar, paritatea lui $i$ si paritatea numarului de obiecte ce trebuie luate pentru a castiga jocul, se determina starile in care se poate ajunge; ca orice alt joc rezolvat prin programare dinamica, jucatorul aflat la mutare va avea strategie sigura de castig daca cel putin una din starile in care poate ajunge este o stare de pierdere pentru jucatorul ce se va afla la mutare in continuare (adica adversarul).

h2. '1expr':problema/1expr

Solutia $O(N*K)$ se poate optimiza la $O(N)$, observand ca, de fapt, pentru starile in care poate ajunge jocul dupa efectuarea unei mutari nu ne intereseaza numarul exact de obiecte ramase, ci paritatea acestui numar. Pe masura ce mergem cu $i$ de la $1$ la $N$ si calculam valorile mentionate anterior, retinem si ultima valoare a lui $i$ ce corespunde unei stari de tipul $(x,y,z)$, unde $x$ reprezinta pariatea numarului de obiecte pe care trebuie sa le ia unul din cei doi jucatori pentru a castiga jocul, $y$ reprezinta paritatea numarului de obiecte aflate in gramada, iar $z$ retine daca jucatorul aflat la mutare are sau nu are strategie sigura de castig in conditiile date de $x$ si $y$. Memorand astfel de triplete, problema de decizie pentru un numar de obiecte $i$ se reduce la a verifica daca ultimul numar de obiecte din gramada (ultima pozitie $j < i$) ce corespunde unei stari de un anumit tip care ar determina existenta unei strategii sigure de castig pentru pozitia $i$, se afla in intervalul $[i-K,i-1]$ (adica acel numar de obiecte in gramada poate fi obtinut dintr-o singura mutare).
 
Uitandu-ne pe valorile obtinute pentru fiecare $i$ de la $1$ la $N$, observam o regula care reduce complexitatea rezolvarii problemei la $O(1)$. Pentru $K$ par, daca $N mod (K + 2) = 1$, castigatorul jocului va fi Ionel (al doilea jucator); in caz contrar, castigatorul va fi Gigel (primul jucator). Pentru $K$ impar, daca $N mod (2 * K + 2) = 1$, atunci castigatorul este Ionel (al doilea jucator); in caz contrar, castigatorul va fi Gigel (primul jucator).
 
h2(#nr5). '1expr':problema/1expr

Problema se rezolva folosind programare dinamica. Pentru fiecare $K$ de la 1 la $3^8^$ se calculeaza lungimea minima a unei $1-expresii$ care are ca rezultat pe $K$, iar ultima operatie efectuata in cadrul acestei $1-expresii$ este $+$, $*$, $^$ sau $!$ (deci se calculeaza $4$ valori). Este important sa se calculeze toate aceste $4$ valori si nu doar o singura lungime minima a unei $1-expresii$ care il are ca rezultat pe $K$, deoarece este posibil ca acea $1-expresie$ sa se obtina folosind operatori de prioritate mica si, pentru a fi folosita in cadrul unor expresii mai mari, sa trebuiasca pusa intre paranteze.

* pentru $+$ : se incearca combinarea a doua expresii al caror rezultat este $X$, respectiv $K-X$
* pentru $*$ : combinarea a doua expresii al caror rezultat este $X$, respectiv $K/X$
* pentru $^$ : similar

* pentru $!$ : numai in cazul in care $K$ este factorialul unui numar (pentru limitele date, $K$ poate fi maxim $7!$ )

* pentru $!$ : numai in cazul in care $K$ este factorialul unui numar (pentru limitele date, factorialul maxim este $7!$ )

Se calculeaza la inceput cele $4$ valori pentru fiecare numar de la $1$ la limita maxima, apoi pentru fiecare numar dat in fisierul de intrare, doar se afisaza rezultatul (daca s-ar recalcula valorile pentru fiecare numar, s-ar depasi limita de timp).

h2. 'Cc':problema/cc

h2(#nr6). 'Cc':problema/cc

Problema cere determinarea unui cuplaj de cost minim, intr-un graf bipartit complet. Aceasta se poate realiza folosind un algoritm de flux maxim de cost minim sau, mai rapid, folosind algoritmul Ungar.

h2. 'Joc3':problema/joc3

h2(#nr7). 'Joc3':problema/joc3

Problema este cunoscuta sub numele de "staircase Nim".

h2. 'Geometry':problema/geometry

h2(#nr8). 'Geometry':problema/geometry

Pentru fiecare pereche de segmente, se determina daca acestea se intersecteaza. Daca cele $2$ segmente nu sunt paralele, atunci se calculeaza punctul de intersectie al dreptelor suport al celor $2$ segmente si apoi se verifica daca punctul de intersectie se afla in interiorul ambelor segmente. Daca cele $2$ segmente sunt paralele, atunci se verifica daca se afla pe aceeasi dreapta (putem verifica usor acest lucru, calculand intersectia dreptelor suport cu axa $OX$ sau $OY$). Daca sunt pe aceeasi dreapta, se verifica daca exista un capat al unui segment care sa aiba atat coordonata $X$, cat si coordonata $Y$, situate intre coordonatele capetelor celuilalt segment (inclusiv capetele).

h2. 'Itree':problema/itree

h2(#nr9). 'Itree':problema/itree

Un arbore este "arbore de intervale" (conform definitiei din enunt), numai daca orice nod are cel mult $2$ vecini al caror grad este mai mare decat $1$.

h2. 'Hprob':problema/hprob

h2(#nr10). 'Hprob':problema/hprob

Se vor numerota cele $4!=24$ de permutari posibile ale celor $4$ obiecte cu numere de la $1$ la $24$. Se va calcula apoi o matrice $A$, unde fiecare element $A[i][j]$ reprezinta probabilitatea ca daca un client gaseste obiectele in starea $j$, acesta sa le puna la loc in ordinea corespunzatoare starii $i$. Vom considera ca, initial, obiectele se aflau in ordinea corespunzatoare starii $1$ si vom calcula probabilitatea ca la sfarsit acestea sa se afle tot in starea $1$. Vom privi matricea $A$ calculata ca o matrice de iteratie. Vom avea un vector $V{~i~}[j]$ reprezentand probabilitatea ca obiectele sa se afle in starea $j$ dupa $k$ iteratii. Putem calcula pe $V{~i~}$ ca fiind $A*V{~i-1~}$. In felul acesta, $V{~N~}=A^N^*V{~0~}$. $V{~0~}$ are valoarea $1$ pe pozitia $1$ si $0$ pe celelalte pozitii, iar $A^N^$ poate fi calculata eficient folosind exponentiere logaritmica.

h2. 'Nodiv':problema/nodiv
 
h2. 'Arbore de cicluri':problema/arbciclu

h2(#nr11). 'Arbore de cicluri':problema/arbciclu

Vom realiza urmatoarea operatie in mod repetat, pana cand operatia nu mai poate fi aplicata: daca exista un nod $i$ avand gradul $2$, iar vecinii acestuia sunt $j$ si $k$, eliminam nodul $i$ din graf si introducem muchia $j-k$, daca aceasta muchie nu exista deja. Daca graful dat este un arbore de cicluri, atunci la final trebuie sa ramanem cu doar $2$ noduri (si, initial, numarul de noduri trebuie sa fi fost cel putin $3$). Pentru a aplica operatia descrisa in mod eficient, vom folosi o coada in care vom introduce nodurile cu gradul $2$. De fiecare data cand extragem din coada un nod $i$, exista posibilitatea sa modificam gradele vecinilor acestuia, $j$ si $k$; daca $j$ sau $k$ ajung sa aiba gradul $2$ in urma eliminarii lui $i$, ii introducem si pe ei in coada. Mai trebuie sa folosim o structura de date eficienta pentru a determina rapid daca $2$ noduri sunt adiacente, precum si pentru a elimina noduri din "lista" de adiacenta a altor noduri (in implementarea solutiei oficiale s-au folosit arbori echilibrati, prin intermediul structurii "set" din STL).

h2. 'Gandaci Java':problema/java

h2(#nr12). 'Gandaci Java':problema/java

Problema cere determinarea unui cuplaj maxim intr-un graf bipartit. Algoritmii "standard" pentru determinarea unui cuplaj maxim sunt prea lenti pentru limitele date, de aceea este necesara folosirea unei optimizari, cunoscuta ca algoritmul 'Hopcoft-Karp':http://en.wikipedia.org/wiki/Hopcroft-Karp_algorithm ('aici':http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/123641 gasiti o implementare in Python a acestui algoritm).

h2. 'Roy-Floyd':problema/rf

h2(#nr13). 'Roy-Floyd':problema/rf

Se aplica algoritmul Roy-Floyd standard, la care se adauga un criteriu suplimentar: in cazul in care se gaseste un drum de distanta egala cu distanta minima curenta, dar avand un numar mai mare de strazi, se va alege drumul respectiv.

h2. 'Biomech':problema/biomech

h2(#nr14). 'Biomech':problema/biomech
 
Vom calcula matricea $A[lstart][dirstart][lfinish][dirfinish][P]$, reprezentand timpul minim pentru a ajunge de pe linia $lstart$, o coloana oarecare $X$ si privind in directia $dirstart$, pana pe linia $lfinish$, coloana $X + 2^P^$ (deci o coloana situata cu $2^P^$ pozitii mai in dreapta) si privind in directia $dirfinish$. Pentru $P = 0$, vom folosi un algoritm de drum minim. Va trebui sa avem grija ca solutia de timp minim pentru a trece de pe o coloana pe coloana imediat din dreapta ei poate presupune niste mutari "in spate", pe un numar limitat de coloane din stanga. Alegand o limita maxima de $9$ coloane in stanga si in dreapta, putem folosi algoritmul Dijkstra pe un graf ale carui stari constau din elementele unei submatrici de $5$ linii, $19$ coloane si au $8$ orientari. Pentru $P > 0$, $A[lstart][dirstart][lfinish][dirfinish][P] = A[lstart][dirstart][lintermed][dirintermed][P-1] + A[lintermed][dirintermed][lfinish][dirfinish][P-1]$. Variem linia si orientarea intermediara si pastram minimul. In mod similar, vom calcula o matrice $B[lstart][dirstart][lfinish][dirfinish][P]$, unde indicele $P$ va reprezenta sosirea pe o coloana situata cu $2^P^$ coloane la stanga coloanei de start.
 
Cu aceste matrici calculate, vom determina numarul maxim de coloane pe care le poate parcurge robotul spre stanga si spre dreapta, in timpul dat, alegand maximul dintre cele $2$ variante. Voi prezenta in continuare doar cazul deplasarii spre dreapta, cel al deplasarii spre stanga fiind similar. Vom porni de la coloana $0$ si vom mari treptat numarul de coloane pe care le poate parcurge robotul (fie acest numar $C$). Pentru fiecare valoare a lui $C$ si fiecare stare posibila $(linie,orientare)$ vom mentine timpul minim in care se poate ajunge in stares respectiva. Initial, robotul poate ajunge in $0$ unitati de timp doar in starea initiala, in celelalte stari el neputand ajunge. Vom porni cu $P$ de la valoarea maxima pentru care am calculat valori (de exemplu, aceasta valoare poate fi $61$) si il vom decrementa treptat. Presupunand ca am ajuns pana la coloana $C$, vom incerca acum sa parcurgem inca $2^P^$ coloane. Folosind matricea $A$ si cunoscand timpul minim pentru a ajunge la coloana $C$ in fiecare stare posibila, vom calcula timpul minim corespunzator fiecarei stari pentru a ajunge la coloana $C+2^P^$. Daca cel putin o stare are acest moment de timp mai mic sau egal cu durata de timp maxim data, atunci marim valoarea lui $C$ cu $2^P^$ si vom considera momentele de timp actualizate pentru noua valoare a lui $C$. Daca pentru nici o stare nu se poate ajunge la coloana $C+2^P^$ in timp util, atunci lasam valoare lui $C$ nemodificata, nefacand nimic altceva (la urmatorul pas avand, insa, o valoare a lui $P$ cu $1$ mai mica). Valoarea finala a lui $C$ este numarul maxim de coloane ce poate fi parcurs spre dreapta in timpul dat.

h2. 'Expresii min-max':problema/emm

h2(#nr15). 'Expresii min-max':problema/emm

Expresia data poate fi evaluata folosind o metoda de complexitate liniara ({$O(N)$}). Pentru simplificarea explicatiilor, vom considera ca intreaga expresie este incadrata intr-o pereche de paranteze. Se parcurge expresia de la stanga la dreapta si se va mentine o stiva cu operatorii neevaluati inca, cu rezultate partiale si cu paranteze deschise. Cand se inalneste un operator, acesta se adauga in stiva. Cand se intalneste un operand si in varful stivei este un operator, se efectueaza operatia respectiva (caci in stiva se va gasi si cel de-al doilea operand): adica se elimina din stiva operatorul si cel de-al doilea operand si se pune in varful stivei rezultatul operatiei. Cand se intalneste un operand si in stiva se afla o paranteza deschisa, operandul se pune in varful stivei. La intalnirea unei paranteze inchise vom evalua toate operatiile pana la prima paranteza deschisa din stiva. Apoi vom inlocui paranteza deschisa cu rezultatul evaluarii si, daca pe nivelul urmator din stiva se gaseste un operator, atunci efectuam operatia. La final, in varful stivei vom avea rezultatul expresiei.

h2. 'Zeap':problema/zeap

h2(#nr16). 'Noroc':problema/noroc

h2. 'Noroc':problema/noroc

Un punct de pornire consta in calcularea unor vectori $p{~i~}[S]$, reprezentand probabilitatea ca dupa $i$ aruncari sa se obtina suma $S$. $S$ ia valori intre $0$ si $M$, iar $i$ trebuie sa ajunga la o valoare suficient de mare $IMAX$, pentru ca probabilitatea cautata sa nu isi mai modifice primele $7$ zecimale dupa $IMAX$ aruncari (adica sa convearga cu precizia dorita). $p{~i~}[S]$ se calculeaza pe baza lui $p{~i-1~}[S-1]$ si $p{~i-1~}[S+1]$, mai putin in cazurile limita $S=M$ si $S=0$, unde formula este usor diferita. Bieninteles, calculul acestor vectori nu se va incadra in limita de timp, dar, uitandu-ne la probabilitatile obtinute pentru diverse valori ale lui $X$ si $M$, vom observa (sau "ghici") ca rezultatul cerut de problema este $1-X/M$ (ne intereseaza doar cazul $X ≤ M$).