Nu exista diferente intre titluri.
Diferente intre continut:
h1. Solutii Happy Coding 2007 !happy-coding-2007/solutii?hc2007-logo.gif!
h2. 'Abc2':problema/abc2
(toc)*{text-align:center} *Lista de probleme*
* 'Abc2':happy-coding-2007/solutii#abc2
* '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
O prima abordare care ar parea sa aiba sanse de a obtine punctaj maxim este de a construi un 'trie':http://en.wikipedia.org/wiki/Trie al cuvintelor. Cu ajutorul acestui trie putem verifica in complexitate $O(L)$ daca exista vreun cuvant care sa se termine la fiecare pozitie $i$ din sir. Totusi, aceasta solutie are complexitate $O(L*lungime text mare)$ si nu se incadreaza in timp.
* 'Dangerous Pattern / ZJU':http://acm.zju.edu.cn/show_problem.php?pid=2115
h2. 'Tritzi':problema/tritzi
h2(#tritzi). 'Tritzi':problema/tritzi
h3. Algoritm de complexitate $O(N)$
* 'Nice Patterns Strike Back / SGU':http://acm.sgu.ru/problem.php?contest=0&problem=197
* 'Fibo / .campion 2003':http://campion.edu.ro/problems/3/106/fibo.htm
h2. 'Regine2':problema/regine2
h2(#regine2). 'Regine2':problema/regine2
Problema se rezolva prin backtracking. Pentru fiecare pozitie (in ordinea liniilor si, pentru fiecare linie, in ordinea coloanelor), se incearca amplasarea sau neamplasarea unei regine in pozitia respectiva, iar apoi se marcheaza toate pozitiile atacate de regina respectiva, pentru a nu se mai incerca amplasarea unei regine viitoare pe o pozitie deja atacata. La intoarcerea din backtracking, pozitiile marcate se demarcheaza (vom folosi, de fapt, un contor pentru fiecare pozitie, in care vom retine de cate regine deja amplasate este atacata pozitia respectiva). Singura optimizare necesara este ca, atunci cand marcam pozitiile atacate de o regina nou-amplasata, vom marca doar pozitiile pe care vom incerca sa amplasam o regina in viitor (adica doar inspre directiile: est, sud-est, sud, sud-vest, si nu in toate cele $8$ directii).
* 'Problema celor $N$ regine [ clasica ] & co.':http://acm.fzu.edu.cn/reference/Search%20Techniques.htm
* 'Dame2 / Summer Challenge 2007':problema/dame2
h2. 'Rfinv':problema/rfinv
h2(#rfinv). 'Rfinv':problema/rfinv
h3. Solutie de complexitate $O(N^4^)$
* '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.
h3. Solutia 2
Vom incerca sa calculam valorile $pmin[i]$ treptat. Vom parcurge pozitiile de la $1$ la $N$ si vom incerca sa incepem un palindrom avand centrul in pozitia $i$ (pentru cazul unui palindrom de lungime impara), respectiv avand centrul la pozitiile $i$ si $i+1$ (pentru cazul unui palindrom de lungime para). Ideea importanta este ca, atunci cand ajungem la pozitia $i$, toate valorile $pmin[j]$, cu $j < i$ au fost calculate, iar valorile $pmin[k]$, $k > i$, au niste valori partiale (adica valorile calculate nu sunt inca finale, ele mai putand sa scada ulterior). Vom extinde treptat cat putem de mult un palindrom in jurul pozitiei $i$ (respectiv pozitiilor $i$ si {$i+1$}); la fiecare pas de extindere, vom incerca sa incrementam palindromul de la lungimea curenta $L$, la lungimea $L+2$ (pentru aceasta verificam caracterele din capatele palindromului); inainte de a realiza extinderea, vom incerca sa folosim palindromul curent in cadrul unei solutii - mai exact, vom avea posibilitatea ca valoarea $pmin[i-(L+1)/2]+1$ sa fie folosita pentru a micsora valoarea lui $pmin[i+(L+1)/2-1]$ (pentru cazul lungimii impare), respectiv valoarea $pmin[i-L/2]+1$ poate fi folosita pentru a micsora valoarea lui $pmin[i+L/2]$ (pentru cazul lungimii pare).
Vom incerca sa calculam valorile $pmin[i]$ treptat. Vom parcurge pozitiile de la $1$ la $N$ si vom incerca sa incepem un palindrom avand centrul in pozitia $i$ (pentru cazul unui palindrom de lungime impara), respectiv avand centrul la pozitiile $i$ si $i+1$ (pentru cazul unui palindrom de lungime para). Ideea importanta este ca, atunci cand ajungem la pozitia $i$, toate valorile $pmin[j]$, cu $j < i$ au fost calculate, iar valorile $pmin[k]$, $k > i$, au niste valori partiale (adica valorile calculate nu sunt inca finale, ele mai putand sa scada ulterior). Vom extinde treptat cat putem de mult un palindrom in jurul pozitiei $i$ (respectiv pozitiilor $i$ si {$i+1$}); la fiecare pas de extindere, vom incrementa palindromul de la lungimea curenta $L$, la lungimea $L+2$ (pentru aceasta verificam caracterele din capatele palindromului); inainte de a realiza extinderea, vom incerca sa folosim palindromul curent in cadrul unei solutii - mai exact, vom avea posibilitatea ca valoarea $pmin[i-(L+1)/2]+1$ sa fie folosita pentru a micsora valoarea lui $pmin[i+(L+1)/2-1]$ (pentru cazul lungimii impare), respectiv valoarea $pmin[i-L/2]+1$ poate fi folosita pentru a micsora valoarea lui $pmin[i+L/2]$ (pentru cazul lungimii pare).
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)$.
*Cosmin:* problema s-a dat si la algoritmus. Acolo limita de timp era foarte stransa si solutiile ce au luat punctaj maxim aveau complexitate $O(N^2^)$. Ajungem la complexitatea aceasta, folosind un hash table pentru a determina numarul maxim de puncte cu acelasi unghi fata de $i$ in loc sa sortam punctele.
Solutia de complexitate $O(N^3^)$, in care se fixeaza $2$ puncte si se determina in $O(N)$ numarul de puncte ce se afla pe dreapta determinata de cele $2$ puncte, nu se incadreaza in timp.
h3. Probleme asemanatoare
* '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 nu 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:
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:
* $C1 = F{~i1~} + C{~i1~} * X1 + (S{~i1~} + S{~i1+1~} + .. + S{~j-1~}) * X1 = A1 + B1 * X1$
* $C2 = F{~i2~} + C{~i2~} * X2 + (S{~i2~} + S{~i2+1~} + .. + S{~j-1~}) * X2 = A2 + B2 * X2$
Vom calcula costurile $cmin[i]$, reprezentand costul total minim pentru a satisface cererile din lunile $1, 2, .., i$. Algoritmul este descris in continuare in pseudocod:
* $cmin[ 0 ] = 0$
* $pentru i de la 1 la N$
** $cmin[i]=infinit$
** $pentru j de la 1 la i$
*** $cost_total = cmin[j-1] + F[j] + C[j] * D[j]$
*** $cost_stocare=S[j]$
*** $pentru k de la j+1 la i$
**** $cost_total = cost_total + (C[j]+cost_stocare) * D[k]$
**** $cost_stocare = cost_stocare + S[k]$
*** $daca cost_total < cmin[i] atunci$
**** $cmin[i]=cost_total$
==code(c) |
cmin[ 0 ] = 0
pentru i de la 1 la N
cmin[i]=infinit
pentru j de la 1 la i
cost_total = cmin[j-1] + F[j] + C[j] * D[j]
cost_stocare=S[j]
pentru k de la j+1 la i
cost_total = cost_total + (C[j]+cost_stocare) * D[k]
cost_stocare = cost_stocare + S[k]
daca cost_total < cmin[i] atunci
cmin[i]=cost_total
==
Se variaza valoarea lui $i$ de la $1$ la $N$ si pentru fiecare valoare incercam sa calculam $cmin[i]$. Pentru aceasta, incercam toate valorile $j ≤ i$ care pot reprezenta luna in care sunt produse kilogramele de cascaval necesare in luna $i$. Apoi calculam costul total pentru cazul in care luna $j$ produce cantitatea de cascaval necesara pentru a satisface cererile din lunile $j, j+1, .., i$. In cele din urma vom avea in $cmin[i]$ minimul dintre costurile corespunzatoare fiecarei variante de alegere a lunii $j$. Costul total minim pentru toate cele $N$ luni il avem in $cmin[N]$. Bineinteles, aceasta solutie nu se incadreaza in limita de timp.
he. Programare dinamica cu complexitatea $O(N^2^)$
h3. Programare dinamica cu complexitatea $O(N^2^)$
Algoritmul descris anterior are complexitatea $O(N^3^). El se poate optimiza, insa, usor la complexitatea $O(N^2^)$.
Algoritmul descris anterior are complexitatea $O(N^3^)$. El se poate optimiza, insa, usor la complexitatea $O(N^2^)$.
==code(c) |
cmin[ 0 ] = 0
pentru i de la 1 la N
cmin[i] = infinit
dtotal = 0
cost_stocare = 0
pentru j de la i la 1
cost_stocare = cost_stocare + S[j] * dtotal
dtotal = dtotal + D[j]
cost_productie = F[j] + C[j] * dtotal
cost_total = cmin[j-1] + cost_productie + cost_stocare
daca cost_total < cmin[i] atunci
cmin[i]=cost_total
==
* $cmin[ 0 ] = 0$
* $pentru i de la 1 la N$
** $cmin[i] = infinit$
** $dtotal = 0$
** $cost_stocare = 0$
** $pentru j de la i la 1$
*** $cost_stocare = cost_stocare + S[j] * dtotal$
*** dtotal = dtotal + D[j]
*** cost_productie = F[j] + C[j] * dtotal
*** cost_total = cmin[j-1] + cost_productie + cost_stocare
*** daca cost_total < cmin[i] atunci
**** cmin[i]=cost_total
Optimizarea adusa este minora, dar importanta. In algoritmul anterior, cel de-al treilea ciclu era folosit pentru a aduna la costul total costul stocarii cantitatilor de cascaval. In varianta optimizata, am schimbat sensul de parcurgere al variabilei $j$ si, in felul acesta, putem calcula pe parcurs o parte din costul de stocare. Practic, la inceputul fiecarei iteratii din cel de-al doilea ciclu, $cost_stocare$ retine costul stocarii cantitatiior de cascaval din lunile $j+1, .., i$, el trebuind actualizat doar cu costul de stocare din luna $j$.
h3. Programare dinamica cu complexitatea $O(N*log^2^N)$
Folosind observatia ca fiecare functie este minima pe cel mult un interval, putem folosi un arbore de intervale pentru a stoca in el semidrepte. Aceasta este o utilizare oarecum neobisnuita a unui arbore de intervale, dar vom vedea ca este foarte utila in cazul acestei probleme. Pseudocodul solutiei este urmatorul:
* $; calculeaza vectorii SP si DP$
* $SP[0]=0$
* $DP[0]=0$
* $pentru i de la 1 la N$
** $SP[i]=SP[i-1]+S[i]$
** $DP[i]=DP[i-1]+D[i]$
* $; calculeaza vectorul cmin$
* $cmin[0]=0$
* $pentru i de la 1 la N$
** $finit[i]=cmin[i-1]+F[i]$
** $P[i]=C[i]-SP[i-1]$
** $[li,ri]=find_interval(i) ; gaseste intervalul [li,ri] pe care functia fi este minima$
** $daca intervalul [li, ri] nu este vid$
*** $update(li,ri,i,radacina_arborelui_de_intervale)$
** $cmin[i]=get_min(i) ; determina valoarea minima in punctul i dintre toate functiile existente$
* $suma=0$
* $pentru i de la 1 la N$
** $suma=suma+SP[i-1]*D[i]$
* $afisaza cmin[N]+suma$
==code(c) |
// calculeaza vectorii SP si DP
SP[ 0 ] = 0
DP[ 0 ] = 0
pentru i de la 1 la N
SP[i] = SP[i-1] + S[i]
DP[i] = DP[i-1] + D[i]
// calculeaza vectorul cmin
cmin[ 0 ] = 0
pentru i de la 1 la N
finit[i] = cmin[i-1] + F[i]
P[i] = C[i] - SP[i-1]
[li,ri] = find_interval(i) // gaseste intervalul [li,ri] pe care functia fi este minima
daca intervalul [li, ri] nu este vid
update(li, ri, i, radacina_arborelui_de_intervale)
cmin[i] = get_min(i) // determina valoarea minima in punctul i dintre toate functiile existente
suma = 0
pentru i de la 1 la N
suma = suma + SP[i-1] * D[i]
afisaza cmin[N] + suma
==
Cele $3$ functii a caror implementare mai trebuie descrisa in detaliu sunt: $find_interval$, $update$ si $get_min$.
Pseudocodul pentru calculul capatului stanga al intervalului in care functia fi este minima este urmatorul:
*left=i
*right=N
*li=N+1
*cat timp left <= right
** mid = (left+right)/2
** fi_mid_1 = finit[i]+(DP[mid]-DP[i-1])*P[i] // valoarea in punctul DP[mid+1]
** fi_mid_2 = finit[i]+(DP[mid + 1]-DP[i-1])*P[i] // valoarea in punctul DP[mid]
** fmin1=get_min(mid+1) // valoarea minima in punctul DP[mid+1]
** fmin2=get_min(mid) // valoarea minima in punctul DP[mid]
** df1 = fi_mid_1 - fmin1;
** df2 = fi_mid_2 - fmin2;
** daca (df1 < 0)
*** li = mid;
*** right = mid - 1;
** altfel
** daca (df1 - df2 > 0)
*** left = mid + 1;
** altfel
*** right = mid - 1;
* ; la sfarsit, in li se afla capatul stanga al intervalului in care fi este minima (sau N+1 daca nu exista un astfel de interval)
==code(c) | find_interval(i)
left=i
right=N
li=N+1
cat timp left <= right
mid = (left+right)/2
fi_mid_1 = finit[i]+(DP[mid]-DP[i-1]) * P[i] // valoarea in punctul DP[mid+1]
fi_mid_2 = finit[i]+(DP[mid + 1]-DP[i-1]) * P[i] // valoarea in punctul DP[mid]
fmin1=get_min(mid+1) // valoarea minima in punctul DP[mid+1]
fmin2=get_min(mid) // valoarea minima in punctul DP[mid]
df1 = fi_mid_1 - fmin1
df2 = fi_mid_2 - fmin2
daca (df1 < 0)
li = mid
right = mid - 1
altfel
daca (df1 - df2 > 0)
left = mid + 1
altfel
right = mid - 1
// la sfarsit, in li se afla capatul stanga al intervalului in care fi este minima (sau N+1 daca nu exista un astfel de interval)
==
Functiile $update$ si $get_min$ se aplica arborelui de intervale si au complexitate $O(logN)$. Complexitatea functiei $find_interval$ este $O(log^2^N)$.
Pseudocodul functiei $update$ este prezentat in continuare:
* $*update(li,ri,i,nod)*$
* $daca intervalul corespunzator nodului nod este chiar [li,ri], atunci$
** $index[nod]=i$
* $altfel$
** $fs = fiul stanga al nodului nod$
** $fd = fiul dreapta al nodului nod$
** $daca l[fd] > ri atunci$
*** $update(li,ri,i,fs)$
** $altfel$
** $daca r[fs] < li atunci$
*** $update(li,ri,i,fd)$
** $altfel$
*** $update(li,r[fs],i,fs)$
*** $update(l[fd],ri,i,fd)$
== code(c) | update(li,ri,i,nod)
daca intervalul corespunzator nodului nod este chiar [li,ri], atunci
index[nod]=i
altfel
fs = fiul stanga al nodului nod
fd = fiul dreapta al nodului nod
daca l[fd] > ri atunci
update(li,ri,i,fs)
altfel
daca r[fs] < li atunci
update(li,ri,i,fd)
altfel
update(li,r[fs],i,fs)
update(l[fd],ri,i,fd)
==
h4. Functia $get_min$
Fiecare nod din arbore are o referinta catre tatal sau $(tata[nod])$. Radacina arborelui are o referinta catre o valoare nedefinita $(NEDEFINIT)$. Pseudocodul functiei $get_min$ este urmatorul:
* $get_min(i)$
* $nod = nodul din arbore corespunzator intervalului [i,i]$
* $val_min=infinit$
* $cat timp nod <> NEDEFINIT$
** $k=index[nod]$
** $daca k este definit atunci$
*** $fki = finit[k] + (DP[i] - DP[k-1]) * P[k]$
*** $daca fki < val_min atunci$
**** $val_min=fki$
** $nod=tata[nod]$
* $intoarce val_min$
== code(c) | get_min(i)
nod = nodul din arbore corespunzator intervalului [i,i]
val_min=infinit
cat timp nod != NEDEFINIT
k=index[nod]
daca k este definit atunci
fki = finit[k] + (DP[i] - DP[k-1]) * P[k]
daca fki < val_min atunci
val_min=fki
nod=tata[nod]
intoarce val_min
==
h3. Link-uri utile
* Un 'articol':http://dspace.mit.edu/bitstream/1721.1/5146/1/OR-238-90.pdf care prezinta o solutie a acestei probleme avand complexitate optima $O(N*logN)$
* 'Sensitivity Analysis of the Economic Lot-Sizing Problem / MIT':http://dspace.mit.edu/bitstream/1721.1/5146/1/OR-238-90.pdf -> articolul prezinta o solutie a acestei probleme avand complexitatea optima $O(N*logN)$
h3. Probleme asemanatoare
* 'Euro / BOI 2003':problema/euro
* 'Yogurt Factory / USACO 2005':http://acm.pku.edu.cn/JudgeOnline/problem?id=2393
* 'Branza':problema/branza
* 'Rompetrol':problema/rompetrol
* '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.
h3. Link-uri utile
* 'Circle-Cirlce Intersection / Mathworld':http://mathworld.wolfram.com/Circle-CircleIntersection.html
* 'Circle-Circle Intersection / Mathworld':http://mathworld.wolfram.com/Circle-CircleIntersection.html
h3. Probleme asemanatoare
* '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$
* $daca toti soldatii pot ajunge in siguranta la destinatie, atunci deplaseaza-i acolo si incheie misiunea cu succes$
* $altfel: "Mission aborted!"$
==code(c) |
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
daca toti soldatii pot ajunge in siguranta la destinatie, atunci deplaseaza-i acolo si incheie misiunea cu succes
altfel: "Mission aborted!"
==
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.
Vom calcula valorile $Tmin[i][j]$, reprezentand numarul minim de pasi necesari pentru a distribui mesajul tuturor nodurilor din subarborele nodului $i$, considerand ca au fost efectuati primii $j$ pasi din cadrul strategiei optime a nodului $i$ si ca au fost taiate din subarborele lui $i$ toti subarborii primelor $j$ noduri care au primit mesajul direct de la nodul $i$. Evident, cand $i=1$, in $Tmin[ 1 ][ 0 ]$ vom avea numarul minim de pasi necesari pentru distributia mesajului la toate nodurile din arbore.
Vom calcula, in ordine (de la $j=0$), toate valorile $Tmin[i][j]$. Sa observam intai (pentru cazul $j=0$), ca $Tmin[i][0]$ trebuie sa fie mai mare sau cel putin egal cu $Tmin[f][ 0 ]$, unde $f$ este fiu al lui $i$. Vom cauta binar aceasta valoare, intre maximul dintre valorile $Tmin[f][0]$ si $N-1$. Sa presupunem ca am fixat, in cadrul cautarii binare, $T$ unitati de timp. Vom initializa fiecare fiu $f$ al lui $i$ ca aflandu-se in starea $s(f)=0$ (adica nu s-a efectuat nici o mutare din cadrul strategiei sale optime). Vom considera fiul $f$ al lui $i$ care are valoarea $Tmin[f][s(f)]$ maxima. Daca $T > Tmin[f][s(f)]$, atunci trimitem mesajul nodului $f$, scadem din T o unitate de timp si mergem mai departe (ignorand nodul $f$ de acum inainte). Daca, la un moment dat, avem $T = Tmin[f][s(f)]$, atunci se demonstreaza (nu foarte usor, dar nici prea greu) ca nodul $i$ trebuie sa trimita mesaj nodului $j$ care este al $s(f)+1$-lea nod la care ar trimite mesaj nodul $f$ in cadrul strategiei sale optime. In felul acesta, taiem subarborele nodului $j$, scadem $T$ cu $1$ unitate si trecem nodul $f$ din starea $s(f)$ in starea $s(f)+1$ (pentru ca deja s-a efectuat o mutare din cadrul strategiei sale optime). Daca, la un moment dat, $T < Tmin[f][s(f)]$, atunci trebuie incercata o valoare mai mare in cadrul cautarii binare.
Vom calcula, in ordine (de la $j=0$), toate valorile $Tmin[i][j]$. Sa observam intai (pentru cazul $j=0$), ca $Tmin[i][ 0 ]$ trebuie sa fie mai mare sau cel putin egal cu $Tmin[f][ 0 ]$, unde $f$ este fiu al lui $i$. Vom cauta binar aceasta valoare, intre maximul dintre valorile $Tmin[f][ 0 ]$ si $N-1$. Sa presupunem ca am fixat, in cadrul cautarii binare, $T$ unitati de timp. Vom initializa fiecare fiu $f$ al lui $i$ ca aflandu-se in starea $s(f)=0$ (adica nu s-a efectuat nici o mutare din cadrul strategiei sale optime). Vom considera fiul $f$ al lui $i$ care are valoarea $Tmin[f][s(f)]$ maxima. Daca $T > Tmin[f][s(f)]$, atunci trimitem mesajul nodului $f$, scadem din T o unitate de timp si mergem mai departe (ignorand nodul $f$ de acum inainte). Daca, la un moment dat, avem $T = Tmin[f][s(f)]$, atunci se demonstreaza (nu foarte usor, dar nici prea greu) ca nodul $i$ trebuie sa trimita mesaj nodului $j$ care este al $s(f)+1$-lea nod la care ar trimite mesaj nodul $f$ in cadrul strategiei sale optime. In felul acesta, taiem subarborele nodului $j$, scadem $T$ cu $1$ unitate si trecem nodul $f$ din starea $s(f)$ in starea $s(f)+1$ (pentru ca deja s-a efectuat o mutare din cadrul strategiei sale optime). Daca, la un moment dat, $T < Tmin[f][s(f)]$, atunci trebuie incercata o valoare mai mare in cadrul cautarii binare.
Inainte de a calcula $Tmin[i][j+1]$ dupa ce am calculat $Tmin[i][j]$, memoram in $Mut[i][j]$ nodul la care a trimis mesaj nodul $i$ prima data (adica al $j+1$-lea nod din cadrul strategiei optime a nodului $i$) si in $F[i][j]$ fiul din subarborele caruia face parte nodul $Mut[i][j]$. De asemenea, starile fiiilor nodului $i$ se seteaza la valorile pe care le aveau inainte de a calcula $Tmin[i][j]$, incrementand doar starea fiului $F[i][j]$ cu $1$ (sau eliminand de tot fiul $F[i][j]$, daca $F[i][j] = Mut[i][j]$). Vom termina calculul acestor valori atunci cand $Tmin[i][j]=0$.
Pentru reconstituirea solutiei, vom initializa toate nodurile ca aflandu-se in starea $0$ si vom tine un vector cu nodurile la care a ajuns deja mesajul. Prima mutare va fi de la nodul $1$ la nodul $j = Mut[ 1 ][ 0 ]$. Pentru toate nodurile de pe calea de la $1$ (inclusiv) la $j$ (exclusiv), vom incrementa starea in care se afla acestea, apoi vom marca ca nodul $j$ a primit mesajul. La urmatorul moment de timp, vom lua fiecare nod care detine mesajul, vom verifica daca mai are de efectuat pasi din strategia sa optima si daca da, vom efectua pasul corespunzator in mod similar mutarii descrise mai sus.
Complexitatea solutiei descrise este O(N^3^ * logN).
Complexitatea solutiei descrise este $O(N^3^ * logN)$.
O dificultate suplimentara apare in momentul in care avem mai multi fii $f$ ai unui nod $i$, pentru care $Tmin[f][s(f)]$ are aceeasi valoare maxima. In aceasta situatie, va trebui sa il alegem pe cel pentru care sirul $Tmin[f][s(f)], Tmin[f][s(f)+1], ..$ este maxim din punct de vedere lexicografic. Justificarea este ca vrem sa scapam de acel fiu care ne-ar restrictiona cel mai mult mutarile ulterioare daca nu l-am taia acum. Mai exact, daca la un moment dat ajungem cu $T$-ul egal cu $Tmin[f][s(f)]$ (deoarece am eliminat altii fii si nu pe $f$), vrem ca acest fiu $f$ sa aiba sirul respectiv cat mai mic din punct de vedere lexicografic, pentru a ne restrictiona cat mai putin timpul.
h3. Link-uri utile
* 'Information Dissemination in Restricted Routing Networks':http://citeseer.ist.psu.edu/186949.html - in acest articol este prezentata o solutie de complexitate O(N^3^) la aceasta problema
* '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:
h3. Probleme asemanatoare
* 'Consilul tribului / BOI 2003':problema/trib
* '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:
Pe langa alegerea uneia dintre cele $2$ metode, sunt necesare cateva optimizari suplimentare, precum:
* ridicarea la puterea $P$ trebuie realizata folosind exponentiere logaritmica; in plus, chiar si in cadrul exponentierii logaritmice, putem sa nu efectuam toti pasii daca, la un moment dat, numarul de cifre ale numarului obtinut depaseste numarul de cifre ale lui $N$
* efectuarea tuturor calculelor intr-o baza mai mare decat $10$ (solutia oficiala foloseste baza ${10^4^$}), deoarece, astfel, numarul de cifre ale numerelor ce intervin in calcule scade simtitor.
* efectuarea tuturor calculelor intr-o baza mai mare decat $10$ (solutia oficiala foloseste baza $10^4^$), deoarece, astfel, numarul de cifre ale numerelor ce intervin in calcule scade simtitor.
* in cazul cautarii binare, intervalul initial de cautare nu trebuie sa fie $[1,N]$, ci un interval mai restrans (de exemplu, $[10^(X/P)-1^, 10^(X/P)+1^]$), unde $X$ este numarul de cifre ale numarului N dat.
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". Aceasta euristica se refera la urmatoarea situatie: Sa presupunem ca am extras din coada nodul $X$ (primul nod din coada) si urmeaza sa incercam sa facem update-uri la distantele tuturor vecinilor nodului $X$, folosind distanta calculata pana acum pentru $X$. De asemenea, sa presupunem ca nodul care i-a facut update la distanta minima nodului $X$ este $T$ ({$T$} mai este numit si parintele lui $X$, deoarece este nodul chiar dinaintea lui $X$ de pe drumul minim pana la $X$). Inainte sa incercam sa facem update pentru toti vecinii lui $X$, verificam daca nodul $T$ se afla in coada. Daca se afla in coada, atunci nu mai facem update folosind nodul $X$ si trecem la urmatorul nod din coada. Motivul este urmatorul: Daca nodul $T$ se afla in coada, el a fost introdus acolo dupa ce i-a facut update distantei pana la nodul $X$; noua valoarea a distantei minime pana la $T$ este mai mica decat in momentul cand s-a calculat distanta minima pana la $X$, astfel ca, atunci cand vom extrage din coada nodul $T$, se va micsora in mod sigur si distanta pana la $X$. Prin urmare, nu are rost sa facem acum update-uri folosind nodul $X$, deoarece acesta are calculata o distanta despre care stim sigur ca va fi micsorata in curand.
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
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$.
h2(#biti3). 'Biti3':problema/biti3
Folosind aceste valori, vom determina bitii celui de-al $M$-lea sir, unul cate unul, pornind de la al $N$-lea bit. La fiecare pas, va trebui sa determinam cate siruri incep cu bitul $0$ si cate siruri incep cu bitul $1$. La inceput, vor exista $num[N-1,3]$ siruri care incep cu bitul $0$ si $num[N-1,2]$ siruri care incep cu bitul $1$. Este evident ca, la un anumit pas, toate sirurile care incep cu $0$ se vor afla inaintea tuturor sirurilor care incep cu $1$. De aceea, daca $M$ < numarul sirurilor care incep cu $0$, bitul respectiv va fi $0$; in caz contrar, bitul va fi $1$. Daca bitul este $1$, inainte de a trece la pasul urmator, va trebui sa actualizam valoarea lui $M$, in asa fel incat sa sarim peste toate sirurile care incep cu $0$ ({$M = M - numarul de siruri care incep cu 0$), precum si sa tinem cont de faptul ca am mai consumat inca un bit de $1$. Algoritmul in pseudocod este urmatorul:
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-1, 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$.
* $nrbiti = 3$
* $for i = N -> 1$
** $daca num[i-1, nrbiti] >= M atunci$
*** $bitul i este 0$
** $altfel$
*** $bitul i este 1$
*** $M = M - num[i-1, nrbiti]$
*** $nrbiti = nrbiti - 1$
Folosind aceste valori, vom determina bitii celui de-al $M$-lea sir, unul cate unul, pornind de la al $N$-lea bit. La fiecare pas, va trebui sa determinam cate siruri incep cu bitul $0$ si cate siruri incep cu bitul $1$. La inceput, vor exista $num[N-1,3]$ siruri care incep cu bitul $0$ si $num[N-1,2]$ siruri care incep cu bitul $1$. Este evident ca, la un anumit pas, toate sirurile care incep cu $0$ se vor afla inaintea tuturor sirurilor care incep cu $1$. De aceea, daca $M$ < numarul sirurilor care incep cu $0$, bitul respectiv va fi $0$; in caz contrar, bitul va fi $1$. Daca bitul este $1$, inainte de a trece la pasul urmator, va trebui sa actualizam valoarea lui $M$, in asa fel incat sa sarim peste toate sirurile care incep cu $0$ ({$M = M - numarul de siruri care incep cu 0$}), precum si sa tinem cont de faptul ca am mai consumat inca un bit de $1$. Algoritmul in pseudocod este urmatorul:
== code(c) | nrbiti = 3
for i = N -> 1
daca num[i-1, nrbiti] >= M atunci
bitul i este 0
altfel
bitul i este 1
M = M - num[i-1, nrbiti]
nrbiti = nrbiti - 1
==
h3. Probleme asemanatoare
* 'Word Encoding / ACM ICPC NWERC 2004':http://acm.pku.edu.cn/JudgeOnline/problem?id=2058
* 'Coding of Permutations / POJ':http://acm.pku.edu.cn/JudgeOnline/problem?id=1349
* 'Bits of Trinity / ACM ICPC NWERC 1999':http://www.acm.inf.ethz.ch/ProblemSetArchive/B_EU_NWRC/1999/Problems.pdf'
* 'Cuvinte / Stelele Informaticii 2003':problema/cuvinte
* 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.
h4. Acoperirea cu numar minim de drumuri
Vom parcurge matricea pe linii, si pentru fiecare linie, pe coloane. Vom mentine o stare $S$ asemanatoare celei din solutia prezentata mai sus, la care se mai adauga un indice $C$ $(1 ≤ C ≤ N)$, avand semnificatia ca valorile de la $C+1$ la $N$ se refera la pozitiile de pe linia de deasupra, iar valorile de pe pozitiile de la $1$ la $C$ (din cadrul starii) se refera la linia curenta. Mentinand starea in acest fel, cand ajungem la elementul de pe linia $L$ si coloana $C$, vom calcula toate starile pentru care indicele este egal cu $C$. Pentru aceasta, vom parcurge toate starile $S'$ corespunzatoare coloanei anterioare ($C-1$ sau $N$, daca $C$ este prima coloana) si vom genera toate starile $S$ cu indicele egal cu $C$, avand de ales dintre urmatoarele optiuni:
Vom parcurge matricea pe linii, si pentru fiecare linie, pe coloane. Vom mentine o stare $S$ asemanatoare celei din solutia prezentata mai sus, la care se mai adauga un indice $C$ $(1 ≤ C ≤ N)$, avand semnificatia ca valorile de la $C+1$ la $N$ se refera la pozitiile de pe linia de deasupra, iar valorile de pe pozitiile de la $1$ la $C$ (din cadrul starii) se refera la linia curenta. Mentinand starea in acest fel, cand ajungem la elementul de pe linia $L$ si coloana $C$, vom calcula toate starile pentru care indicele este egal cu $C$. Pentru aceasta, vom parcurge toate starile $S'$ corespunzatoare coloanei anterioare ({$C-1$} sau $N$, daca $C$ este prima coloana) si vom genera toate starile $S$ cu indicele egal cu $C$, avand de ales dintre urmatoarele optiuni:
* incepe drum nou -> numarul de drumuri creste cu 1
* uneste nodul curent de nodul din stanga -> numarul de drumuri ramane constant
* '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))$
h3. Solutie $O(N*logN)$
Solutia prezentata poate fi optimizata la complexitate $O(N*logN)$, folosind o tehnica standard. Orice query de acest tip corespunzator unui arbore de intervale 2D poate fi redus de la o complexitate $O(log^2^N)$ la o complexitate $O(log N)$. Practic, se va efectua o cautare binara a coordonatei $Y$ inferioare si superioare numai in cadrul radacinii arborelui de intervale. Apoi, din constructia arborelui, vom memora pentru fiecare punct $P$ al fiecarui nod, $4$ pointeri:
* un pointer catre punctul cu cea mai mica coordonata $Y$ mai mare sau egala cu cea a punctului $P$ si care se afla in intervalul de coordonate $X$ al fiului stanga
* un pointer catre punctul cu cea mai mica coordonata $Y$ mai mare sau egala cu cea a punctului $P$ si care se afla in intervalul de coordonate $X$ al fiului dreapta
* un pointer catre punctul cu cea mai mare coordonata $Y$ mai mica sau egala cu cea a punctului $P$ si care se afla in intervalul de coordonate $X$ al fiului stanga
O parte din acesti pointeri pot fi calculati in momentul in care, in faza de constructie a arborelui de intervale 2D, se interclaseaza coordonatele $Y$ corespunzatoare fiului stanga si fiului dreapta. Cealalta parte a pointer-ilor se calculeaza realizand inca $2$ parcurgeri ale coordonatelor $Y$ sortate, una de la stanga la dreapta si alta de la dreapta la stanga (in conditiile in care am memorat pentru fiecare coordonata $Y$ de la care din cei doi fii provine).
Unul dintre concurenti a obtinut $100$ de puncte folosind o structura de date 2D numita 'kd-tree':http://en.wikipedia.org/wiki/Kd-tree, care poate oferi aceleasi operatii ca si un arbore de intervale 2D. Diferenta consta in cantitatea de memorie folosita ($O(N)$, in loc de $O(N*logN)$), dar si in complexitatea cautarii in interiorul unui dreptunghi ($O(sqrt(N))$, in loc de $O(log^2^N)$ sau $O(logN)$ cu optimizarea mentionata).
Unul dintre concurenti a obtinut $100$ de puncte folosind o structura de date 2D numita 'kd-tree':http://en.wikipedia.org/wiki/Kd-tree, care poate oferi aceleasi operatii ca si un arbore de intervale 2D. Diferenta consta in cantitatea de memorie folosita ({$O(N)$}, in loc de $O(N*logN)$), dar si in complexitatea cautarii in interiorul unui dreptunghi ({$O(sqrt(N))$}, in loc de $O(log^2^N)$ sau $O(logN)$ cu optimizarea mentionata).
h3. Link-uri utile
* 'Cautari Ortogonale':downloads?cautari_ortogonale.doc , articol scris de Cosmin Negruseri
* 'Arbori de intervale':downloads?arbori_de_intervale.zip , articol scris de d-na. prof. Dana Lica
* 'Range Minimum Query and Lowest Common Ancestor':http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor , articol scris de catre Daniel Pasaila
* 'Orthogonal Range Queries':http://people.csail.mit.edu/indyk/6.838-old/handouts/lec5.pdf
* 'Cautari Ortogonale / infoarena':cautari-ortogonale , articol scris de Cosmin Negruseri
* 'Arbori de intervale / infoarena':arbori-de-intervale , articol scris de d-na. prof. Dana Lica
* 'Range Minimum Query and Lowest Common Ancestor / TopCoder':http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor , articol scris de catre Daniel Pasaila
* 'Orthogonal Range Queries / MIT':http://people.csail.mit.edu/indyk/6.838-old/handouts/lec5.pdf
h3. Probleme asemanatoare
* '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.
Daca aplicam algoritmul direct, obtinem o solutie de tipul 'Divide et Impera':http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm , ce are complexitatea $O(N*logN)$. O imbuntataire a acestei solutii (care nu este necesara pentru a obtine punctajul maxim la problema) consta in observatia ca, de fapt, va trebui sa rezolvam cel mult $2*logN$ probleme distincte. Sa consideram urmatorul caz (cea mai proasta situatie):
* $N=2*k+1$: La primul nivel de recursivitate trebuie sa rezolvam problema pentru valorile k si k+1. Avem urmatoarele $2$ subcazuri:
** $k=2*p$ si $k+1=2*p+1$: Pentru $k$, va trebui sa rezolvam la nivelul urmator de recursivitate problema pentru valoarea $p$, iar pentru $k+1$ va trebui sa rezolvam problema pentru valorile $p si p+1$ ; asadar, la urmatorul nivel de recursivitate va trebui sa rezolvam problema doar pentru valorile distincte $p$ si $p+1$.
** $k=2*p-1$ si $k+1=2*p$: Pentru $k$, va trebui sa rezolvam la nivelul urmator de recursivitate problema pentru valorile $p-1$ si $p$, iar pentru $k+1$ va trebui sa rezolvam problema pentru valoarea $p$ ; asadar, la urmatorul nivel de recursivitate va trebui sa rezolvam problema doar pentru valorile distincte $p-1$ si $p$.
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:
* 'Obj / Happy Coding 2006':problema/obj
* 'Pawns / Bursele Agora 2004':problema/pawns
* 'Game / Bursele Agora 2004':problema/game
* 'Pietre':problema/pietre
* 'Pietre / infoarena':problema/pietre
* 'Otilia / .campion 2005':problema/otilia
* 'Playing with Matches / SGU':http://acm.sgu.ru/problem.php?contest=0&problem=153
* 'A Stone Game / TIMUS':http://acm.timus.ru/problem.aspx?space=1&num=1180
* 'The Game of Squares / TIMUS':http://acm.timus.ru/problem.aspx?space=1&num=1529
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.
