* 'Tritzi':happy-coding-2007/solutii#tritzi
* 'Regine 2':happy-coding-2007/solutii#regine2
* 'Rfinv':happy-coding-2007/solutii#rfinv

* 'Pali':happy-coding-2007/solutii#pali
* 'Furnica':happy-coding-2007/solutii#furnica
* 'Flori 2':happy-coding-2007/solutii#flori2
* 'Bitmap':happy-coding-2007/solutii#bitmap
* 'Cascaval':happy-coding-2007/solutii#cascaval
* 'Cercuri 3':happy-coding-2007/solutii#cercuri3
* 'Antitero':happy-coding-2007/solutii#antitero
* 'Sistem 2':happy-coding-2007/solutii#sistem2
* 'Optic':happy-coding-2007/solutii#optic
* 'Zvon':happy-coding-2007/solutii#zvon
* 'Cerc 2':happy-coding-2007/solutii#cerc2
* 'Puteri 2':happy-coding-2007/solutii#puteri2
* 'Aimin':happy-coding-2007/solutii#aimin
* 'Multimi':happy-coding-2007/solutii#multimi
* 'Nrbanda':happy-coding-2007/solutii#nrbanda
* 'Tramvai':happy-coding-2007/solutii#tramvai
* 'Biti 3':happy-coding-2007/solutii#biti3
* 'Clear':happy-coding-2007/solutii#clear
* 'H':happy-coding-2007/solutii#h
* 'Permavg':happy-coding-2007/solutii#permavg
* 'Kboard':happy-coding-2007/solutii#kboard

h2(#abc2). 'Abc2':problema/abc2

* 'Rf / Happy Coding 2006':problema/rf

h2. 'Pali':problema/pali

h2(#pali). 'Pali':problema/pali

Se va calcula $pmin[i]$ = numarul minim de palindroame in care poate fi impartit sirul format din primele $i$ caractere ale sirului dat.

Complexitatea ambelor solutii este $O(N^2^)$, insa a doua solutie merge mai repede, in practica, deoarece ia in considerare numai palindroamele valide (care pot fi cel mult {$O(N^2^)$}).

h2. 'Furnica':problema/furnica

h2(#furnica). 'Furnica':problema/furnica

* daca pozitia de start este $'C'$, atunci raspunsul este $(t+1)^2^$
* daca pozitia de start este $'S'$, atunci:

Aceste formule (sau altele echivalente) pot fi obtinute folosind urmatorul rationament: furnica se poate afla in orice pozitie aflata la o distanta care are aceeasi paritate ca si $t$, fata de pozitia initiala. Pentru pozitia de start $'C'$, aceste pozitii formeaza niste "romburi", iar pentru pozitia de start $'S'$, aceste pozitii formeaza niste diagonale "secundare".

h2. 'Flori2':problema/flori2

h2(#flori2). 'Flori2':problema/flori2

Pentru fiecare punct $i$, se sorteaza toate celelalte $N-1$ puncte in jurul punctului $i$ (in functie de unghi). Parcurgand apoi punctele in ordinea sortata, vom determina numarul maxim de puncte avand acelasi unghi fata de $i$ (folosind o precizie corespunzatoare, de $10^-8^$, de exemplu). Fie acest numar $MAX{~i~}$. Raspunsul cautat este $maxim{MAX{~i~} + 1}$ si se obtine in complexitate $O(N^2^*logN)$.

* 'Rabbit Hunt / TIMUS':http://acm.timus.ru/problem.aspx?space=1&num=1052
* 'Maximum Number of Colinear Points / KATTIS':https://kattis.csc.kth.se/problem?id=maxcolinear

h2. 'Bitmap':problema/bitmap

h2(#bitmap). 'Bitmap':problema/bitmap

O prima solutie ar consta in a incerca toate cele $4$ posibilitati de a codifica un bitmap care nu are toate celulele de aceeasi culoare. Aceasta abordare de tip backtracking nu s-ar incadra in timp. Optimizarea necesara consta in 'memoizarea':http://en.wikipedia.org/wiki/Memoization starilor prin care trecem in cadrul backtracking-ului (algoritmul nu se mai numeste backtracking acum, ci devine un fel de programare dinamica). O stare este data de $2$ numere pe cel mult $11$ biti, $S{~1~}$ si $S{~2~}$. Bitii de $1$ din $S{~1~}$ definesc liniile selectate din cadrul bitmap-ului initial, iar bitii de $1$ din $S{~2~}$ definesc coloanele selectate din cadrul bitmap-ului initial. Bitmap-ul definit de starea $(S{~1~},S{~2~})$ este reprezentat de celulele aflate la intersectia dintre liniile selectate de $S{~1~}$ si coloanele selectate de $S{~2~}$. Prin urmare, vom calcula $lmin[S{~1~},S{~2~}]$ = lungimea minima a bitmap-ului ce corespunde starilor $S{~1~}$ si $S{~2~}$. $lmin[2^M^ 1,2^N^-1]$ va contine rezultatul cautat. Pentru ca solutia sa se incadreze in timp, matricea cu valorile asociate fiecarei stari nu trebuie reinitializata la fiecare test. Se va folosi o matrice suplimentara $last_test$, in care vom memora numarul ultimului test in care am ajuns sa calculam valoarea pentru starea $(S{~1~},S{~2~})$. Daca ajungem la starea $(S{~1~},S{~2~})$ in testul curent, vom verifica valoarea lui $last_test[S{~1~},S{~2~}]$. Daca aceasta este egala cu numarul testului curent, inseamna ca am calculat deja valoarea respectiva; in caz contrar, o vom calcula acum si vom seta $last_test[S{~1~},S{~2~}]$ la numarul testului curent.

h2. 'Cascaval':problema/cascaval

h2(#cascaval). 'Cascaval':problema/cascaval

Rezolvarea problemei incepe cu o observatie ne neaparat evidenta. Sa presupunem ca in luna $j$, compania are $X$ kilograme de cascaval (produse in luna respectiva sau in lunile anterioare si stocate pana in luna $j$). Sa presupunem, de asemenea, ca aceste $X$ kilograme provin din productia de cascaval din $2$ luni diferite, $i1$ si $i2$. Vom calcula costurile obtinerii celor $X1$ si celor $X2$ kilograme de cascaval:

* 'Branza / preONI 2007':problema/branza
* 'Rompetrol / Autumn Warmup 2007':problema/rompetrol

h2. 'Cercuri3':problema/cercuri3

h2(#cercuri3). 'Cercuri3':problema/cercuri3

O metoda simpla este sa translatam primul cerc in originea sistemului de axe de coordonate si sa il rotim pe cel de-al doilea pana cand centrul acestuia se afla pe axa $OX$ (la coordonata $X$ egala cu distanta dintre cele $2$ centre). Trebuie analizate cateva cazuri, pe baza valorilor razelor celor $2$ cercuri si a distantei dintre centrele lor (cazurile simple sunt cand unul din cercuri se afla complet in interiorul, respectiv complet in exteriorul celuilalt cerc). In cazul in care se decide ca cele $2$ cercuri se intersecteaza in $2$ puncte, vom observa ca, in urma translatiei si rotatiei efectuate, cele $2$ puncte de intersectie se vor afla la aceeasi coordonata $x$, dar la coordonate $y$ opuse (egale in modul, dar opuse ca semn). Vom determina cele $2$ coordonate folosind 'Teorema lui Pitagora generalizata':http://en.wikipedia.org/wiki/Pythagorean_theorem in triunghiul format din centrele celor $2$ cercuri si fiecare din cele $2$ puncte de intersectie (deoarece cunoastem lungimile tuturor laturilor). Aria comuna a celor 2 cercuri este acum formata din 2 bucati de cerc, de o parte si de alta a segmentului ce uneste cele 2 puncte de intersectie. Aria fiecareia din cele 2 bucati de cerc se poate scrie ca diferenta dintre aria unui sector de cerc (corespunzator segmentului ce uneste punctele de intersectie) si aria unui triunghi (format din centrul unui cerc si cele 2 puncte de intersectie). O formulare suficient de generala a expresiilor ce calculeaza aria comuna permite tratarea unitara a cazurilor in care cel de-al doilea cerc are centrul in exteriorul, respectiv in interiorul primului cerc.

* 'Cercuri / Happy Coding 2005 [2]':problema/cercuri
* 'Cerc2 / Happy Coding 2007':problema/cerc2

h2. 'Antitero':problema/antitero

h2(#antitero). 'Antitero':problema/antitero

* $cat timp (exista un soldat care se poate deplasa in siguranta intr-o pozitie de unde poate omori un terorist)$
** $deplaseaza soldatul in pozitia respectiva si elimina teroristul$

Aceasta este schita unui algoritm usor de implementat care rezolva problema. Practic, se incearca eliminarea repetata a cat mai multor teroristi, dupa care se incearca deplasarea la destinatie. Rezolvarea problemei implica, asadar, doar parcurgeri repetate ale grafului (de exemplu, 'DF':http://en.wikipedia.org/wiki/Depth-first_search sau 'BF':http://en.wikipedia.org/wiki/Breadth-first_search), in care unele noduri sunt "blocate" (cele in care se afla teroristi in viata si cele amenintate de teroristi in viata).

h2. 'Sistem2':problema/sistem2

h2(#sistem2). 'Sistem2':problema/sistem2

Problema se rezolva generand permutari ale celor $N$ variabile si verificand daca ele verifica constrangerile. Ideea importanta este ca verificarea satisfacerii constrangerilor sa nu se realizeze abia dupa ce s-a generat cate o permutarea intreaga, deoarece o astfel de abordare nu s-ar incadra in limita de timp. Pe masura ce selectam o valoare pentru un element $i$ al permutarii, vom verifica toate constrangerile care contin acel element si elemente dinaintea lui $i$ (ale caror valori au fost, de asemenea, deja selectate). Daca cel putin o constrangere nu este satisfacuta, nu vom mai continua generarea permutarii in continuare, ci vom trece la valoarea urmatoare a elementului $i$ (scapand, astfel, de un numar posibil foarte mare de permutari pe care le-am fi generat degeaba). Aceasta optimizarea nu ne-ar fi prea folositoare daca, de exemplu, toate constrangerile contin ultimul element (si verificarea lor se poate face abia la sfarsit), insa, putem schimba ordinea in care selectam valorile elementelor. De exemplu, daca luam elementele in ordinea in care apar acestea in constrangeri (intai cele din prima constrangere, apoi cele din a doua care nu apar si in prima, apoi cele din a treia care nu apar in primele doua s.a.m.d.), putem garanta ca dupa selectarea valorilor a cel mult $4$ elemente vom putea verifica prima constrangere si ca dupa cel mult $8$ elemente putem verifica a doua constrangere. Daca schimbam si ordinea constrangerilor, in asa fel incat constrangerile cu numar mai mic de variabile sa fie primele, obtinem niste optimizari si mai bune. Alta optimizare utila ar fi aceea ca, daca o constrangere contine $P$ variabile, dupa setarea valorilor a $P-1$ dintre ele se poate calcula valoarea celeialalte variabile. De asemenea, pentru fiecare element a carui valoare nu a fost setata inca s-ar putea memora multimea valorilor posibile pe care le mai poate lua in continuare (pe baza variabilelor avand valori setate si a multimilor de valori posibile ale variabilelor cu valori nesetate inca, dar impreuna cu care se afla in cel putin o constrangere),
In concluzie, problema nu se rezolva in timp polinomial (lucru care se putea ghici dupa numarul mic de variabile), fiind necesare unele optimizari. Ea poate fi privita ca un caz particular al 'problemei satisfacerii constrangerilor':http://en.wikipedia.org/wiki/Constraint_satisfaction, care este o problema generala, pentru care au fost studiati multi algoritmi si au fost gasite multe optimizari.

h2. 'Optic':problema/optic

h2(#optic). 'Optic':problema/optic

Sa consideram, pe rand, fiecare nod $i$ al arborelui dat (in ordine, de la frunze spre radacina) si subarborele acestuia. Vom rezolva problema considerand ca arborele consta numai din subarborele cu radacina in nodul $i$. In felul acesta, cand vom considera nodul $i=1$, vom avea solutia pentru intreg arborele.

* 'Information Dissemination in Restricted Routing Networks / CiteSeer':http://citeseer.ist.psu.edu/186949.html -> in acest articol este prezentata o solutie de complexitate O(N^3^) la aceasta problema

h2. 'Zvon':problema/zvon

h2(#zvon). 'Zvon':problema/zvon

Solutia "oficiala" are complexitatea $O(N*logN)$ si presupune calculul urmatoarelor valori:

* 'Consiliul tribului / BOI 2003':problema/trib
* 'Optic / Happy Coding 2007':problema/optic

h2. 'Cerc2':problema/cerc2

h2(#cerc2). 'Cerc2':problema/cerc2

Observam ca distanta dintre oricare $2$ puncte in care fotonul atinge cercul este aceeasi ca cea dintre punctul initial si punctul $(R*cos(alfa), R*sin(alfa))$. Fie aceasta distanta $D$. Dupa $S$ secunde, fotonul se afla la o distanta $S mod D$ de ultimul punct in care a atins cercul. Operatia $modulo$ se poate defini si pentru numere reale, scriind $S$ ca fiind $k*D + r$, unde k este un numar intreg (si $r$ este restul impartirii). Putem folosi acum Teorema lui Pitagora generalizata, pentru a determina distanta de la foton la centrul cercului, in triunghiul format din punctul curent, ultimul punct de atingere a cercului si centrul cercului. O metoda mai simpla de a calcula aceasta distanta este de a calcula distanta de la centrul cercului la segmentul dintre $2$ puncte consecutive in care fotonul atinge cercul (aceasta distanta este {$R*sin(beta)$}). Cum perpendiculara din centrul cercului pe acest segment il intersecteaza exact in mijloc, putem folosi distanta fotonului fata de mijlocul segmentului si apoi Teorema lui Pitagora intr-un triunghi dreptunghic, pentru a calcula distanta de la foton la centrul cercului (in triunghiul format de centrul cercului, mijlocul segmentului si pozitia fotonului, distanta respectiva este lungimea ipotenuzei).

* 'Cercuri / Happy Coding 2005 [2]':problema/cercuri
* 'Cercuri3 / Happy Coding 2007':problema/cercuri3

h2. 'Puteri2':problema/puteri2

h2(#puteri2). 'Puteri2':problema/puteri2

Problema cere determinarea radicalului de ordin $P$ dintr-un numar mare. Exista mai multe metode de realiza acest lucru, dintre care voi mentiona doua:

O alta optimizare care ar fi putut avea un impact simtitor asupra timpului de executie este inmultirea a doua numere mari in complexitate $O(C*logC)$, unde $C$ este numarul de cifre ale acestora,  insa implementarea unei astfel de operatii ar fi fost mai complicata (si nu era necesara pentru a obtine punctaj maxim la problema) (vezi 'aici':http://numbers.computation.free.fr/Constants/Algorithms/fft.html)

h2. 'Aimin':problema/aimin

h2(#aimin). 'Aimin':problema/aimin

Solutia de complexitate $O(N^3^)$ este evidenta. Se calculeaza $HMIN[i, j]$, reprezentand inaltimea minima a unui arbore ce contine frunzele din intervalul $i, .., j$. $HMIN[i, i] = L{~i~}$, iar $HMIN[i, j] = 1 + min { max {HMIN[i,k], HMIN[k+1,j]} }$ (pentru $i < j$ si $i ≤ k < j$ ). Raspunsul il avem in $HMIN[1, N]$. In mod evident, pentru limitele date, algoritmul nu are nici o sansa sa se incadreze in limita de timp (sau de memorie).

Pentru a obtine punctaj maxim, datorita limitei de timp nu foarte stricte, se putea implementa si un algoritm cu complexitatea $O(N*logN)$, folosind structuri de date precum 'arbori indexati binar':http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees sau 'arbori de intervale':arbori-de-intervale ; de exemplu, o solutie asemanatoare constructiei unui arbore 'Huffman':http://en.wikipedia.org/wiki/Huffman_coding, bazata pe unirea repetata a cate doi subarbori alaturati pentru care maximul inaltimilor este minim.

h2. 'Multimi':problema/multimi

h2(#multimi). 'Multimi':problema/multimi

Se considera matricea $M$ cu $n$ linii si $m$ coloane, unde $M[i][j]=1$, daca $i$ este in $A{~j~}$ si $0$, altfel. Deoarece $A{~1~},...,A{~m~}$ separa multimea $[n]$, rezulta ca oricare $2$ linii ale matricei sunt diferite (daca liniile $k$ si $l$ ar fi egale, atunci $k$ si $l$ nu pot fi separate). De aici rezulta ca $n ≤ 2^m^$ (numarul de linii posibile, astfel incat oricare $2$ sa fie diferite). Asadar, $m ≥ log{~2~}n$. Vom arata ca $m=(log{~2~}n) + 1$. Presupunem prin absurd ca $m=log{~2~}n$. Din principiul lui Dirichlet se obtine cu usurinta faptul ca fie apare in matrice linia $00..0$ (contradictie cu conditia de acoperire), fie matricea contine 2 linii identice, ceea ce este absurd.
Pentru $m=(log{~2~}n)+1$ se poate da exemplul urmator: $A{~j~}$ este multimea numerelor mai mici sau egale cu $n$ care au $1$ pe bitul $(j-1)$ din reprezentarea lor binara pe $m$ biti (am numarat bitii de la stanga catre dreapta, incepand cu bitul {$0$})

h2. 'Nrbanda':problema/nrbanda

h2(#nrbanda). 'Nrbanda':problema/nrbanda

Se roteste intreg sirul la stanga, pana cand pe prima pozitie se afla numarul $1$. Apoi problema se rezolva incremental, pas cu pas. La pasul $i$ ({$2 ≤ i ≤ N$}), avem numerele de la $1$ la $i-1$ pe primele $i-1$ pozitii si vom dori sa aducem numarul $i$ pe pozitia $i$ (daca nu se afla deja acolo). Pentru aceasta, rotim sirul spre dreapta pana cand numarul $i$ ajunge pe ultima pozitie. Apoi separam sirul intre pozitiile $N-1$ si $N$ pana cand pe pozitiile $N-i+1, N-i+2, .., N-1$ se afla numerele $1, 2, .., i-1$ (la fiecare separare, numarul $i$ ramane pe ultima pozitie, iar numerele de pe pozitiile $1,..,N-1$ se rotesc spre stanga). Apoi se roteste intregul sir spre stanga, pana cand numerele $1, .., i$ ajung pe pozitiile $1, .., i$.

* 'Order2 / Lista lui Francu':problema/order2

h2. 'Tramvai':problema/tramvai

h2(#tramvai). 'Tramvai':problema/tramvai

Se construieste un graf al punctelor de intersectie dintre oricare $2$ drepte. Acest graf are $O(N^2^)$ noduri, insa fiecare nod are cel mult $4$ vecini (cate $2$ pe fiecare din cele $2$ drepte care il determina). Problema se reduce acum la determinarea drumului minim intre $2$ puncte in acest graf. Algoritmul folosit de solutia oficiala este 'Dijkstra':http://en.wikipedia.org/wiki/Dijkstra's_algorithm cu heap, care are complexitatea $O(N^2^*logN)$, insa se poate folosi cu succes si algoritmul 'Bellman-Ford':http://en.wikipedia.org/wiki/Bellman-Ford_algorithm, implementat folosind o coada (aceasta varianta, cunoscuta ca algoritmul Bellman-Ford-Moore, are o complexitate teoretica mare, dar, in practica, merge foare bine; este, posibil, insa, ca, in cazul acestei probleme, sa fie necesare unele optimizari pentru a se incadra in limita de timp - de exemplu, folosirea euristicii "parent checking").

h2. 'Biti3':problema/biti3

h2(#biti3). 'Biti3':problema/biti3

Vom considera bitii fiecarui sir numerotati de la $N$ la $1$ (de la stanga la dreapta) si vom calcula $num[i, j]$ = numarul de siruri de $i$ biti, continand exact $j$ biti de $1$. $num[i, 0] = 1$. Pentru $j > i$, avem $num[i, j] = 0$ ; altfel, $num[i, j] = num[i-1, j] + num[i, j-1]$ (cele $2$ variante corespund deciziei de a plasa un bit de $0$ pe pozitia $i$, caz in care pe pozitiile $1,..,i-1$ se afla $j$ biti de $1$, respectiv un bit de $1$ pe pozitia $i$, caz in care pe pozitiile $1,..,i-1$ se mai afla doar $j-1$ biti de $1$). Alt mod de a calcula aceste valori este urmatorul: $num[i,j] = Combinari de i luate cate j$.

* 'Bits of Trinity / ACM ICPC NWERC 1999':http://www.acm.inf.ethz.ch/ProblemSetArchive/B_EU_NWRC/1999/Problems.pdf'
* Parantezari / Baraj ONI 2000

h2. 'Clear':problema/clear

h2(#clear). 'Clear':problema/clear

Probleme cere acoperirea cu numar minim de drumuri/cicluri a unui subgraf al grafului-grid $MxN$. Problema este foarte asemanatoare cu problema 'Kcity':problema/kcity , propusa in cadrul 'rundei 3 a concursului Autumn-Warmup 2007':http://infoarena.ro/autumn-warmup-2007/runda-3 si, daca numerotam nodurile grafului incepand de la $1$, parcurgand matricea pe linii, iar pentru fiecare linie, pe coloane, obtinem un graf care are aceeasi proprietate cu cel din Kcity (modulul diferentei dintre numerele asociate a doua noduri conectate printr-o muchie este limitat de o constanta: $7$, respectiv $10$). Totusi, aplicand direct ideea de rezolvare de la Kcity, se obtine un numar prea mare de stari, care nu permite incadrarea solutiei in limita de timp stabilita.

* 'Kcity / Autumn Warmup 2007':problema/kcity
* 'Pipes / ACM ICPC NWERC 2004':http://acm.pku.edu.cn/JudgeOnline/problem?id=2064

h2. 'H':problema/h

h2(#h). 'H':problema/h

h3. Solutie $O(N*log^2^(N))$

* 'Zoo / .campion 2003':problema/zoo
* 'Kth Number / ACM ICPC NEERC Northern Subregion 2004':http://acm.tju.edu.cn/toj/showp2722.html

h2. 'Permavg':problema/permavg

h2(#permavg). 'Permavg':problema/permavg

Observam ca, pentru ca media aritmetica a doua numere sa fie un numar intreg, ambele numere trebuie sa aiba aceeasi paritate. Acesta observatie ne-ar putea conduce la ideea de a separa, in cadrul permutarii, numerele pare de numerele impare. Sa presupunem ca vrem sa amplasam la inceputul permutarii toate numerele pare, apoi toate numerele impare. Sa consideram cazul numerelor pare, cazul numerelor impare tratandu-se similar. Avem $N/2$ numere pare: $2, 4, 6, ...$ pe care trebuie sa le ordonam in asa fel incat media aritmetica a oricare doua numere sa nu se afle intre ele. Vom renumerota numerele pare ca fiind $1, 2, .., N/2$ si vom observa ca acum problema s-a redus la a gasi o permutare de $N/2$ elemente pentru care media a oricare $2$ numere sa nu se afle intre ele (exact problema initiala, dar pentru $N$ injumatatit). Vom aplica in mod recursiv acest algoritm, pana ajungem la permutari cu $1$ sau $2$ elemente.

In concluzie, la fiecare nivel al recursivitatii, avem de rezolvat, de fapt, doar $2$ probleme distincte. Prin urmare, daca memoizam rezultatele pentru fiecare valoare pentru care generam cate o permutare in cadrul algoritmului descris anterior, vom ajunge la o complexitate $O(N)$, in loc de $O(N*logN)$. Aceasta complexitate se obtine din urmatoarea relatie: $N + 2 * (N/2 + N/4 + N/8 + ...) = 3*N$.

h2. 'Kboard':problema/kboard

h2(#kboard). 'Kboard':problema/kboard

Avem urmatoarele cazuri: