Problema cere determinarea radicalului de ordin $P$ dintr-un numar mare. Exista mai multe metode de realiza acest lucru, dintre care voi mentiona doua:
* Determinarea radicalului de ordin $P$ cifra cu cifra: Se determina intai numarul de cifre ale numarului (se incadreaza radicalul intre un {$10^x^$ si $10^x+1^$}), apoi se determina, pe rand, fiecare cifra a rezultatului; pentru fiecare pozitie, se incearca, pe rand, toate cifrele de la $0$ la $9$ si ne oprim la ultima cifra pentru care numarul ridicat la puterea $P$ (considerand ca cifrele de dupa cifra curenta sunt egale cu $0$), nu depaseste $N$-ul dat. Eventual, cifra curenta se poate cauta binar (poate fi util daca rezultatul este tinut intr-o baza mai mare decat $10$).
* Determinarea radicalului de ordin $P$ cifra cu cifra: Se determina intai numarul de cifre ale numarului (se incadreaza radicalul intre un $10^x^$ si $10^x+1^$), apoi se determina, pe rand, fiecare cifra a rezultatului; pentru fiecare pozitie, se incearca, pe rand, toate cifrele de la $0$ la $9$ si ne oprim la ultima cifra pentru care numarul ridicat la puterea $P$ (considerand ca cifrele de dupa cifra curenta sunt egale cu $0$), nu depaseste $N$-ul dat. Eventual, cifra curenta se poate cauta binar (poate fi util daca rezultatul este tinut intr-o baza mai mare decat $10$).
* Cautarea binara a rezultatului, intre o limita inferioara si o limita superioara. Numarul fixat in cadrul cautarii binare se ridica la puterea $P$ si daca depaseste $N$-ul dat, se pastreaza jumatatea inferioara a intervalului de cautare; in caz contrar, se pastreaza jumatatea superioara a intervalului.
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.
* 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.
* 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. Clear
h2. H
h2. 'H':problema/h
h2. Permavg
h3. Solutie $O(N*log^2^(N))$
h2. Kboard
Pentru fiecare segment vertical $(X{~1~},Yj{~1~},Ys{~1~})$, vom dori sa determinam un segment vertical din stanga sa $(X{~2~},Yj{~2~},Ys{~2~})$, impreuna cu care formeaza o litera $H$ de lungime maxima, in fiecare din urmatoarele $4$ cazuri (ce depind de pozitia celui de-al doilea segment fata de primul):
* $Yj{~1~} ≤ Ys{~2~} ≤ Ys{~1~}$ si $Yj{~2~} ≤ Yj{~1~}$ : in acest caz, litera $H$ va avea YjosH = Yj{~1~} si YsusH = Ys{~2~}
* $Yj{~2~} ≤ Yj{~1~} ≤ Ys{~1~} ≤ Ys{~2~}$ : in acest caz, litera $H$ va avea YjosH = Yj{~1~} si YsusH = Ys{~1~}
* $Yj{~1~} ≤ Yj{~2~} ≤ Ys{~2~} ≤ Ys{~1~}$ : in acest caz, litera H va avea YjosH = Yj{~2~} si YsusH = Ys{~2~}
* $Yj{~1~} ≤ Yj{~2~} ≤ Ys{~1~}$ si $Ys{~1~} ≤ Ys{~2~}$ : in acest caz, litera H va avea YjosH = Yj{~2~} si YsusH = Ys{~1~}
Constatam ca, o data ce am fixat unul din cele $4$ cazuri, este foarte clara contributia fiecaruia din cele $2$ segmente la lungimea literei $H$:
* cazul $1$: contributia segmentului $1$ este $L{~1~} = X{~1~} - 2 * Yj{~1~}$, iar cea a segmentului $2$ este $W = -X{~2~} + 2 * Ys{~2~}$
* cazul $2$: contributia segmentului $1$ este $L{~1~} = X{~1~} + 2 * (Ys{~1~} - Yj{~1~})$, iar cea a segmentului $2$ este $W = -X{~2~}$
* cazul $3$: contributia segmentului $1$ este $L{~1~} = X{~1~}$, iar cea a segmentului $2$ este $W = -X{~2~} + 2*(Ys{~2~}-Yj{~2~})$
* cazul $4$: contributia segmentului $1$ este $L{~1~} = X{~1~} + 2 * Ys{~1~}$, iar cea a segmentului $2$ este $W = -X{~2~} - 2 * Yj{~2~}$
In aceste conditii, pentru fiecare caz, putem privi fiecare segment ca un punct intr-un alt sistem de coordonate 2D, in care coordonata $X$ corespunde lui $Yj$, iar coordonata $Y$ corespunde lui $Ys$. In plus, fiecare punct are asociata o pondere $W$. Pentru fiecare caz construim cu toate cele $N$ puncte un arbore de intervale 2D, care utilizeaza $O(N*logN)$ memorie. Acest arbore de intervale este, de fapt, un arbore de intervale obisnuit pentru coordonatele $X$, insa fiecare nod al arborelui mentine un vector cu coordonatele $Y$ ale punctelor ce corespund intervalului nodului respectiv. In plus, pentru fiecare coordonata $Y$ se mentine si ponderea asociata punctului.
Pentru fiecare caz $C$ si fiecare segment vertical, vom dori sa gasim segmenetul vertical din stanga sa cu care poate forma o litera $H$ de lungime maxima. Acest segment corespunde unui punct ce se afla intr-un dreptunghi ce corespunde constrangerilor pentru coordonatele $Yj$ si $Ys$ corespunzatoare cazului $C$ si care are ponderea $W$ maxima. Pentru fiecare caz, interogarile pot fi astfel puse incat dreptunghiul $[a,b]x[c,d]$ in care cautam punctul sa aiba ori coordonata c egala cu $-infinit$, ori coordonata $d$ egala cu $+infinit$. In aceste conditii, pentru fiecare nod din arborele de intervale in care se ajunge prin "spargerea" segmentului $[a,b]$, va trebui sa determinam ponderea maxima a unui punct care are coordonata $Y$ printre primele $z$ sau printre ultimele $z$ (unde $z$ este determinat folosind cautare binara in fiecare nod al arborelui de intervale al coordonatelor $X$ in care ajungem). Din acest motiv, putem sa mentinem pentru fiecare nod un vector $wmax[z]$ cu ponderea maxima a unui punct dintre primele $z$ puncte ce corespund intervalului nodului, precum si un vector similar ce corespunde ultimelor $z$ puncte ale intervalului; daca unul dintre capetele $c$ sau $d$ nu era egal cu $+/- infinit$, atunci trebuia sa folosim RMQ (Range Minimum Query) pentru fiecare nod din arbore.
Observam ca, in modul in care am pus interogarile, nu am specificat nicaieri ca punctul cu pondere maxima sa corespunda unui segment aflat in stanga segmentului pentru care facem interogarea. Totusi, daca punctul cu pondere maxima obtinut nu corespunde unui segment aflat in stanga segmentului curent, atunci vom obtine in mod sigur o litera H de lungime mai mare in momentul in care vom efectua interogarea pentru segmentul corespunzator punctului obtinut (acest lucru se datoreaza modului in care sunt definite ponderile).
Mai trebuie sa avem grija ca, atunci cand realizam interogarea, punctul de pondere maxima sa nu corespunda chiar segmentului pentru care facem interogarea (ceea ce se poate intampla, intrucat nu am impus nici o conditie pentru a evita aceasta situatie). Pentru a evita acest lucru, o posibilitate este sa folosim niste limite ale dreptunghiului de interogare care sa excluda punctele ce corespund unor segmente ce au exact acelasi $Yjos$ si acelasi $Ysus$ ca si segmentul curent. In felul acesta, insa, ajungem sa nu luam in considerare $H$-uri formate din $2$ segmente care au acelasy $Yjos$ si acelasi $Ysus$ (dar coordonate $X$ diferite). Acest caz trebuie tratat separat, printr-o simpla sortare si parcurgere a segmentelor (segmentele avand acelasi $Yjos$ si $Ysus$ aflandu-se unul dupa altul in ordinea sortata).
Complexitatea acestei solutii este $O(N*log^2^N)$ si foloseste memorie $O(N*logN)$.
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
* 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 dreapta
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).
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
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
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
Avem urmatoarele cazuri:
* $K=1$: Daca $N$ este impar, atunci primul jucator castiga; in caz contrar, al doilea jucator castiga.
* $K > 1$: Pentru $K > 1$, va trebui sa folosim teoria numerelor Grundy (vezi 'link1':http://www.ginfo.ro/revista/14_5/mate.pdf , 'link2':http://en.wikipedia.org/wiki/Sprague-Grundy_theory , 'link3':http://yucs.org/~gnivasch/cgames/spraguegrundy/index.html ). Vom calcula pentru fiecare $i$ de la $1$ la $3000$ o valoarea $grundy[i]$, reprezentand numarul Grundy corespunzator unei table formate din $i$ patratele. Pentru $0 ≤ i ≤ K-1$, $grundy[i]=0$. Pentru $i ≥ K$, vom genera toate starile in care putem ajunge dupa prima mutare efectuata: $S{~j~}$ $(0 ≤ j ≤ i-K)$ - plasam piesa pe patratelele $j+1,..,j+K$, impartind tabla in $2$ bucati, una de dimensiune $j$, alta de dimensiune $i-j-K$; calculam apoi numarul Grundy asociat acestei stari "compuse", ca fiind $grundy_compus[S{~j~}] = grundy[j] *xor* grundy[i-j-K]$. Vom calcula apoi primul numar natural (mai mare sau egal cu $0$) care nu apare in multimea numerelor $grundy_compus[S{~j~}]$. Aceasta valoare corespunde numarului $grundy[i]$ (pe care doream sa-l calculam). Pentru o dimensiune $i$ a tablei, jucatorul $1$ are strategie sigura de castig daca $grundy[i] > 0$; in caz contrar, va avea strategie sigura de castig jucatorul $2$. Este evident ca, pentru o valoare $M$, putem calcula numerele Grundy pentru dimensiuni ale tablei de la $1$ la $M$ in complexitate $O(M^2^)$. Dupa ce calculam aceste valori, va trebui sa observam niste reguli pentru a putea rezolva problema pentru limitele date:
** $K > 2$ si $max{3000, 69*K-19} = 3000$: Pentru acest caz nu trebuie sa facem nimic special. Pur si simplu calculam numerele Grundy conform algoritmului descris mai sus si, pentru fiecare test, raspundem in complexitate $O(1)$.
** $K > 2$ si $max{3000, 69*K-19} = 69*K-19$: Dimensiunile tablei de la $1$ la $K-1$ sunt pierzatoare pentru primul jucator, iar dimensiunea $K$ este castigatoare. Vom observa ca, dupa dimensiunea $K-1$, exista $12$ stari pierzatoare pentru primul jucator, de forma $a*K+b$, care sunt aceleasi indiferent de $K$ (in sensul ca sunt aceleasi constante $a$ si $b$). Cel mai simplu mod de a observa acest lucru este de a afisa diferenta dintre dimensiunea $X$ a tablei corespunzatoare unei stari pierzatoare si dimensiunea $Y$ a tablei anterioare ce corespunde unei stari pierzatoare. Cele $12$ diferente sunt, in ordine: $2*K$, $2*K$, $4*K-2$, $4*K-2$, $4*K$, $4*K-2$, $8*K-2$, $4*K-2$, $8*K$, $8*K-2$, $16*K-6$, $4*K$ . Aceasta regula este valida pentru $K ≥ 4$ (dar noi o vom folosi doar pentru $K ≥ 44$, deoarece pentru $K < 44$, ne vom afla in cazul anterior).
** $K=2$: In acest caz ne vom uita, din nou, la diferentele dintre doua stari pierzatoare (pentru primul jucator) consecutive. Vom observa ca sirul acestor diferente (considerand prima stare pierzatoare "interesanta" ca fiind $K-1$) consta dintr-un prefix de lungime $8$ $(4,4,6,6,4,4,6,4)$, dupa care sirul devine periodic, cu perioada $5$ $(4,12,4,4,10)$.
h3. Probleme asemanatoare
* 'Obj / Happy Coding 2006':problema/obj
* 'Pawns / Bursele Agora 2004':problema/pawns
* 'Game / Bursele Agora 2004':problema/game
* 'Pietre':problema/pietre
* 'Otilia / .campion 2005':problema/otilia
