h2. 'Dk':problema/dk
Pentru problema existau diverse rezolvari brute-force, care in functie de calitatea implementarii af fi obtinut pana la $50$ de puncte.
Algoritmul folosit in rezolvarea pentru $100$ de puncte este Miller-Rabin. Este un algoritm probabilistic care verifica primalitatea unui numar in complexitate $O(c*log Nr)$, unde c este numarul de baze folosite pentru verificare.
Dorim sa verificam daca numarul $n$ este prim. Primul pas care trebuie efectuat este acela de a-l scrie pe $n-1$ ca numar de forma <tex>2^s^ * d</tex>, unde s trebuie sa fie maxim. Pasul urmator este sa verificam 2 relatii:
1. <tex> a^{d}\ mod\ n\ \neq\ 1 </tex>
2. <tex> a^{2^r*d}\ mod\ n\ \neq\ -1</tex>, pentru orice $0 ≤ r ≤ s-1$
Daca ambele relatii sunt simultan indeplinite pentru un numar $a$, atunci stim ca numarul $Nr$ este compus. Daca cel putin una dintre conditii nu este indeplinita se continua verificarile pentru un alt numar $a$. Numerele $a$ cu care se vor face verificarile pot fi, de exemplu, primele 6 numere prime sau o multime de numere prime alese aleator (mai mult de $3$, dar nu mai mult de $7$, pentru ca solutia sa se incadreze in timp).
Complexitatea logaritmica a algoritmului provine de la faptul ca ridicarile la putere se vor efectua in $O(log n)$. Pentru mai multe detalii consultati CLR-ul sau 'Wikipedia':http://en.wikipedia.org/wiki/Miller-Rabin_primality_test.
h2. 'Kcity':problema/kcity
h3. "Bandwidth"-ul si "Pathwidth"-ul unui graf
Sa consideram ca nodurile unui graf sunt renumerotate cu numere de la $1$ la $N$ si sa notam cu $BMAX$ valoarea maxima a diferentei (in modul) dintre numerele asociate a doua noduri adiacente. "Bandwidth"-ul $B$ al unui graf este valoarea minima a lui $BMAX$ dintre toate renumerotarile posibile ale nodurilor. Determinarea acestei valori $B$ nu se poate realiza in timp polinomial. In cadrul problemei date, nodurile au fost deja numerotate corespunzator, astfel incat graful sa aiba un "bandwidth" mic, egal cel mult cu valoarea $K$ data.
"Pathwidth"-ul unui graf este un numar ce reflecta cat de mult structura grafului este asemanatoare cu cea a unui drum. Daca un graf $G$ are un "pathwidth" $P$, atunci exista un graf-drum $D$, cu nodurile $D{~1~}, D{~2~}, ..., D{~X~}$, avand urmatoarele proprietati:
* fiecare nod $D{~i~}$ corespunde unei submultimi de cel mult $P$ noduri ale grafului $G$
* oricare doua noduri adiacente ale grafului $G$, $u$ si $v$, se afla impreuna in cel putin una din submultimile $D{~1~},...,D{~X~}$
* orice nod $u$ al grafului $G$ apartine unor multimi $D{~i~}$ care formeaza un sub-drum al grafului $D$ (mai exact, niciun nod $u$ al lui $G$ nu poate sa apartina unui submultimi $D{~i~}$, sa nu apartina unei submultimi $D{~j~}$ {$(j > i)$} si apoi sa apartina din nou unei alte submultimi $D{~k~}$ $(k > j)$
Daca avem o renumerotare a unui graf $G$ corespunzatoare unui "bandwidth" mic, atunci putem obtine si o descompunere cu "pathwidth" mic a grafului G, care ne va ajuta sa rezolvam problema.
h3. Solutie de complexitate $O(N * numar_stari * K^3^)$
Elementele teoretice prezentate mai sus nu sunt neaparat necesare pentru a rezolva problema. Se "ghiceste" usor ca problema se rezolva folosind programare dinamica pe un numar exponential de stari, care depinde, insa, numai de $K$, care este o valoare mica.
Vom calcula urmatoarele valori:
* $minp[i][S]$ = numarul minim de drumuri cu care se pot acoperi nodurile $1,2,...,i$, iar starea la pasul $i$ sa fie $S$
* $minc[i][S]$ = numarul minim de cicluri cu care se pot acoperi nodurile $1,2,...,i$, iar starea la pasul $i$ sa fie $S$ (nu trebuie sa apartina neaparat unui ciclu inchis si nodurile din cadrul starii curente sau cele care apartin deja unor drumuri care au capetele in cadrul starii curente)
O stare $S$ la pasul $i$ este reprezentata de starea ultimelor $K$ noduri $(i-K+1, i-K+2, ..., i)$. O prima idee de definire a starii este urmatoarea: fiecare nod se poate afla in una din urmatoarele $3$ stari:
* are gradul $0$ (este un drum ce consta doar din nodul respectiv)
* are gradul $1$ (este un capat al unui drum)
* are gradul $2$ (se afla in interiorul unui drum sau al unui ciclu (in orice caz, daca un nod are gradul $2$, el nu mai prezinta interes in algoritmul nostru)
Definind o stare astfel, ar exista $3^K^$ stari in total. La fiecare pas $i$, am considera toate starile $S'$ de la pasul $i-1$ si, adaugand nodul $i$, impreuna cu unele muchii, la starea $S'$, am obtine niste stari $S$, pentru pasul $i$. Avem urmatoarele optiuni:
* pentru cazul acoperii cu drumuri
** nodul $i$ formeaza un drum nou (are gradul $0$) => numarul de drumuri creste cu $1$
** nodul $i$ extinde un drum deja existent (il legam de un nod $j$ de grad $0$ sau $1$, cu conditia sa existe muchia $i-j$) => numarul de drumuri ramane acelasi
** nodul $i$ leaga doua drumuri diferite (il legam de nodurile $j$ si $k$ de grad $0$ sau $1$, unind astfel doua drumuri) => numarul de drumuri scade cu $1$
* pentru cazul acoperirii cu cicluri
** nodul $i$ formeaza un drum nou (are gradul $0$) => numarul de cicluri ramane la fel
** nodul $i$ extinde un drum deja existent (il legam de un nod $j$ de grad $0$ sau $1$, cu conditia sa existe muchia $i-j$) => numarul de cicluri ramane la fel
** nodul $i$ leaga doua drumuri diferite (il legam de nodurile $j$ si $k$ de grad $0$ sau $1$, unind astfel doua drumuri) => numarul de cicluri ramane la fel
** nodul $i$ leaga cele $2$ capete ale unui drum => numarul de cicluri creste cu $1$
** daca nodul $i > K$, trebuie sa ne asiguram, inainte de a trece mai departe, ca nodul $i-K$ are gradul $2$ (se afla in interiorul unui drum sau al unui ciclu) => optiunile de mai sus nu sunt valide decat daca, in urma aplicarii lor, nodul $i-K$ are gradul $2$
Observam o dificultate in cazul in care nodul $i$ trebuie sa uneasca doua drumuri de grad $1$. In cazul acoperirii cu drumuri, trebuie sa ne asiguram ca el nu leaga capetele aceluiasi drum (inchizand, de fapt, un ciclu, in timp ce noi credeam ca a unit $2$ drumuri). In cazul acoperii cu cicluri trebuie sa putem realiza aceeasi distinctie. Asadar, modul in care am definit starea nu este corect, desi era, poate, cel mai intuitiv.
O stare va trebui definita in felul urmator: fiecare din cele $K$ noduri ale starii se poate afla in una din urmatoarele situatii:
* are gradul $0$ (este un drum ce consta doar din nodul respectiv) - se codifica prin $0$
* are gradul $1$ si este capatul unui drum care are un identificator bine specificat - se codifica prin identificatorul drumului
* are gradul $2$ (se afla in interiorul unui drum sau al unui ciclu) - se codifica prin $-1$
De exemplu, pentru $K=6$, starea $S=(-1, 1, 0, 2, -1, 1)$ specifica faptul ca primul si al cincilea nod au gradul $2$, al treilea nod are gradul $0$, al doilea si al saselea nod sunt capetele aceluiasi drum, care are identificatorul $1$, iar al patrulea nod este capatul unui drum ce are identificatorul $2$ (celalalt capat fiind ramas undeva in urma).
Conform noii definitii a starilor, acestea trebuie generate explicit. Observam ca doar doua noduri pot fi capetele aceluiasi drum, ca identificatorii drumurilor ii putem genera de la $1$ pana la cate drumuri pot exista intr-o stare (maxim $K$) si ca putem considera identificatorii drumurilor sortati in ordinea in care apar in cadrul starii nodurile ce sunt capetele acestora. De exemplu, starea $S=(-1, 2, 0, 1, -1, 2)$ nu ar avea sens, fiind echivalenta cu cea prezentata mai sus, schimband doar identificatorii drumurilor intre ei. Pentru $K=6$ exista $2364$ astfel de stari.
Raspunsul dorit il gasim intr-una din starile de la pasul $N$:
* pentru acoperirea cu drumuri se alege minimul dintre toate valorile $minp[N][S]$
* pentru acoperirea cu cicluri se alege valoarea $minc[N][S]$, unde $S$ este starea in care toate nodurile au gradul $2$ ; daca aceasta valoare este infinit, atunci rezultatul este $-1$
h2. 'Consir':problema/consir
Sa presupunem ca dorim sa aflam rezultatul pentru secventa maxima $1, 2 ... M$. Fie $F{~1~}, F{~2~}, ... F{~M~}$ frecventele numerelor de la $1$ la $M$ (numarul de aparitii). Sa construim acum un vector $P$ cu semnificatia $P{~i~} = F{~1~}* F{~2~} * ... * F{~i~}$. Datoria faptului ca rezultatul este mai mic decat $2^63^$ este clar ca nu avem mai mult de 63 de pozitii pentru care $F{~i~}>1$, deci la fiecare pas trebuie sa updatam subsecventele care se termina intr-o pozitie cu $F{~i~}>1$. Algoritmul in pseudocod pentru a calcula vectorul $Res$ cu semnificatia $Res{~i~}$ egal cu numarul de consiruri de lungime $i$ devine
== code(c) |
Res[M] = P[M];
pentru i = n-1, 1 executa
Res[i] = Res[i+1] + P[M]/P[M-i];
pentru j astfel incat F[j] >= 2 si j >= i+1
Res[i] = Res[i] - P[j]/P[j-i-1] + P[j-1]/P[j-i-1];
sfarsit pentru
sfarsit pentru
==
h2. 'Polig':problema/polig
Exista mai multe solutii care se incadreaza in timp pentru limitele date, o idee ar fi ca punctele sa fie sortate dupa unghiul cu axa $Ox$. Apoi, folosind programare dinamica vom construi o matrice cu semnificatia $a[i][j]$ = costul maxim astfel incat sa plecam din orginea planului si sa construim un drum care are ultimele puncte $i$ si $j$. In total, memoria este $O(n^2^)$ si complexitatea in timp $O(n^3^)$. Exista o solutie $O(n^2^ lg{~2~}n)$ propusa de Mugurel Ionut Andreica, gasirea ei o lasam ca un exercitiu pentru cititori :-). Daca aveti nelamuriri nu ezitati sa folositi forumul.
