Aflarea lungimii ciclului (punctul 1.) se face usor, pornind din pozitia ({$X Y$}), efectuand mutari pana se ajunge din nou in pozitia ({$X Y$}). Daca numarul de mutari depaseste $modX*modY$ si nu am atins inca pozitia ({$X, Y$}), atunci aceasta nu se afla pe un ciclu. Complexitatea acestui pas va fi {$O(modX * modY)$}.
Pentru a afla, pentru fiecare robot, numarul de mutari pentru a ajunge in ({$X Y$}), putem asocia un graf caroiajului, fiecarei celule din cele $N*N$ corespunzandu-i un nod in graful orientat construit. Pentru fiecare celula ({$i j$}) vom adauga o muchie orientata in acest graf intre nodul corespunzator celulei ({$i j$}) si nodul corespunzator celulei ( {$[i*i + offsetX] modulo modX , [j*j + offsetY] modulo modY$}). Fiecare nod din acest graf va avea gradul de iesire {$1$}, in consecinta, vor fi atatea muchii cate noduri sunt (adica {$N*N$}).
Pornind din pozitia ({$X Y$}), efectuam o parcurgere BFS a grafului INVERSAT si vom afla, pentru fiecare nod, care este numarul de mutari pe care trebuie sa le efectuam, pornind din celula corespunzatoare nodului, pentru a ajunge in pozitia ({$X Y$}). Nodurile care nu pot fi vizitate in aceasta parcurgere corespund unor celule din care nu se poate atinge pozitia ({$X Y$}).

Complexitatea acestui algoritm este $O(N*N)$ si obtine $70%$ din punctaj. Pentru a obtine punctaj maxim, observam ca, dupa prima mutare toti roboteii se afla in caroiajul de dimensiuni ({$modX modY$}), si aplicam acelasi algoritm ignorand pozitiile care sunt in afara acestuia. Observatia precedenta ne permite sa afirmam ca daca un robot pleaca din pozitia ({$i, j$}) e ca si cum ar pleca, imaginar, din pozitia ({$i modX, j modY$}). Putem determina cati roboti pleaca (considerandu-i si pe cei care pleaca imaginar) dintr-o celula ({$i j$}) a caroiajului redus, determinand cate solutii au ecuatiile $x % modX = i$ si $y % modY = j$ ({$x$} si $y$ necunoscute) in intervalul [{$0..N-1$}].

Complexitatea acestui algoritm este $O(N*N)$ si obtine $70%$ din punctaj. Pentru a obtine punctaj maxim, observam ca, dupa prima mutare toti roboteii se afla in caroiajul de dimensiuni ({$modX modY$}), si aplicam acelasi algoritm ignorand pozitiile care sunt in afara acestuia. Observatia precedenta ne permite sa afirmam ca daca un robot pleaca din pozitia ({$i, j$}) e ca si cum ar pleca, imaginar, din pozitia ({$i modX, j modY$}). Putem determina cati roboti pleaca (considerandu-i si pe cei care pleaca imaginar) dintr-o celula ({$i j$}) a caroiajului redus, determinand cate solutii au ecuatiile $x {@%@} modX = i$ si $y {@%@} modY = j$ ({$x$} si $y$ necunoscute) in intervalul [{$0..N-1$}].

h2. PScNv
h3. (problema simpla clasele XI-XII)

Aceasta problema a fost aleasa asa cum spune si textul pentru faptul ca sunt mai multe abordari ce rezolva problema. O prima abordare ar fi pentru un k fixat sa vedem daca putem ajunge de la nodul start pana la nodul destinatie folosind doar muchii cu cost mai mic sau egal cu k. Verificarea acestui fapt o facem folosind o cautare in latime. Cat timp nu putem ajunge de la nodul start la nodul destinatie incrementam pe k si apoi aplicam o cautare in latime. Astfel aflam valoarea k minima ceruta in problema. Complexitatea acestui algoritm este O(kmax (n + m)). Daca notam kmin valoarea ceruta in problema, atunci daca fixam un k si nodul destinatie este accesibil din nodul start folosind doar muchii de pondere mai mica sau egale cu k atunci este evident ca kmin <= k, iar daca nodul destinatie nu este accesibil atunci kmin > k. Pe baza acestei observatii putem dezvolta un algoritm ce cauta binar valoarea kmin ce are complexitatea O(log kmax (n + m)). O alta abordare se bazeaza pe o modificare usoara a
algoritmului Dijkstra de drum minim, in care in loc sa pastram drumuri minime, pastram drumuri pt care muchia maxima are valoare cat mai mica. O implementare cu heapuri a acestui algoritm are complexitate O(m log n). De asemenea algoritmul Bellman Ford poate fi modificat usor pentru a ne rezolva problema, chiar daca acest algoritm are complexitatea O(nm) in practica implementarea lui ce foloseste o lista se comporta cu mult mai bine. Ultimele trei rezolvari ar fi luat in jur de 70 de puncte.
Solutia oficiala se bazeaza tot pe o varianta a algoritmului Dijkstra, dar care in loc sa foloseasca un heap pentru a determina nodul i inca neexpandat cu drumul de la sursa la el de cost minim, foloseste niste liste. Aceasta abordare este identica cu cea din problema Car, si comisia se astepta ca multi concurenti sa rezolve perfect problema, asteptare infirmata de rezultatele din concurs. Cum ponderile muchiilor sunt numere de la 1 pana la 1000 inseamna ca in d[i] oricare ar fi nodul i va fi intotdeauna mai mica sau egala cu 1000. Vom folosi astfel 1000 de liste dublu inlantuite. In lista i vom tine minte nodurile x pentru care d[x] = i. Cand d[x] se micsoreaza inseram pe x intr-o lista mai mica, dar pentru a il sterge din lista veche vom folosi "lazy deletion". Adica atunci cand ajungem la lista i si vrem sa expandam nodul x verificam mai intai daca d[x] = i, daca nu inseamna ca d[x] < i si nodul x a fost expandat mai devreme, deci putem sa il ignoram. Acest algoritm are complexitate O(kmax + n +
m).
Comisia a mai discutat posibilitatea de a propune problema folosind un graf neorientat. Atunci o solutie similara algoritmului Kruskal ar fi avut complexitate aproape de cea optima. Am fi putut folosi un radix sort pentru a sorta muchiile, iar apoi sa adaugam muchii in ordine crescatoare la graf pana cand nodul start si nodul destinatie ar fi fost in aceiasi componenta conexa. Pentru a gestiona componentele conexe am fi folosit structuri de multimi disjuncte. Aceasta solutie ar fi avut complexitatea O(kmax + m log*n).

Aceasta problema a fost aleasa asa cum spune si textul pentru faptul ca sunt mai multe abordari ce rezolva problema. O prima abordare ar fi pentru un $k$ fixat sa vedem daca putem ajunge de la nodul start pana la nodul destinatie folosind doar muchii cu cost mai mic sau egal cu {$k$}. Verificarea acestui fapt o facem folosind o cautare in latime. Cat timp nu putem ajunge de la nodul start la nodul destinatie incrementam pe {$k$} si apoi aplicam o cautare in latime. Astfel aflam valoarea {$k$} minima ceruta in problema. Complexitatea acestui algoritm este {$O(kmax (n + m))$}. Daca notam $kmin$ valoarea ceruta in problema, atunci daca fixam un $k$ si nodul destinatie este accesibil din nodul start folosind doar muchii de pondere mai mica sau egale cu $k$ atunci este evident ca {$kmin ≤ k$}, iar daca nodul destinatie nu este accesibil atunci {$kmin > k$}. Pe baza acestei observatii putem dezvolta un algoritm ce cauta binar valoarea $kmin$ ce are complexitatea {$O(log kmax (n + m))$}. O alta abordare se bazeaza pe o modificare usoara a algoritmului Dijkstra de drum minim, in care in loc sa pastram drumuri minime, pastram drumuri pt care muchia maxima are valoare cat mai mica. O implementare cu heapuri a acestui algoritm are complexitate {$O(m log n)$}. De asemenea algoritmul Bellman Ford poate fi modificat usor pentru a ne rezolva problema, chiar daca acest algoritm are complexitatea $O(n*m)$ in practica implementarea lui ce foloseste o lista se comporta cu mult mai bine. Ultimele trei rezolvari ar fi luat in jur de $70$ de puncte.
 
Solutia oficiala se bazeaza tot pe o varianta a algoritmului Dijkstra, dar care in loc sa foloseasca un heap pentru a determina nodul $i$ inca neexpandat cu drumul de la sursa la el de cost minim, foloseste niste liste. Aceasta abordare este identica cu cea din problema "Car":http://infoarena.ro/task/car, si comisia se astepta ca multi concurenti sa rezolve perfect problema, asteptare infirmata de rezultatele din concurs. Cum ponderile muchiilor sunt numere de la $1$ pana la $1000$ inseamna ca in $d[i]$ oricare ar fi nodul $i$ va fi intotdeauna mai mica sau egala cu {$1000$}. Vom folosi astfel $1000$ de liste dublu inlantuite. In lista $i$ vom tine minte nodurile $x$ pentru care {$d[x] = i$}. Cand $d[x]$ se micsoreaza inseram pe $x$ intr-o lista mai mica, dar pentru a il sterge din lista veche vom folosi "lazy deletion". Adica atunci cand ajungem la lista $i$ si vrem sa expandam nodul $x$ verificam mai intai daca {$d[x] = i$}, daca nu inseamna ca $d[x] < i$ si nodul $x$ a fost expandat mai devreme, deci putem sa il ignoram. Acest algoritm are complexitate {$O(kmax + n + m)$}.
 
Comisia a mai discutat posibilitatea de a propune problema folosind un graf neorientat. Atunci o solutie similara algoritmului Kruskal ar fi avut complexitate aproape de cea optima. Am fi putut folosi un radix sort pentru a sorta muchiile, iar apoi sa adaugam muchii in ordine crescatoare la graf pana cand nodul start si nodul destinatie ar fi fost in aceiasi componenta conexa. Pentru a gestiona componentele conexe am fi folosit structuri de multimi disjuncte. Aceasta solutie ar fi avut complexitatea {$O(kmax + m log*n)$}.

h2. Arbore

(problema medie clasele XI-XII)

 
h3. (problema medie clasele XI-XII)

O prima idee de rezolvare a problemei are o complexitate de O(1) la operatiile de tip update si O(n) la operatiile de tip query. Cand intalnim o operatie de tip 1 este necesar sa folosim un vector S[1..N] in care marcam aceste modificari. Astfel, adunand valoarea s la elementul S[p] vom observa ca suma pe care a primit-o un nod X este de fapt suma valorilor S[nod] unde nod reprezinta indicele nodurilor din drumul lui X pana la radacina arborelui. Deci, pentru o operatie de tipul 1 vom face o singura adunare, iar pentru o operatie de tipul 2 vom efectua o parcurgere in adancime pentru a cauta suma ceruta. Aceasta solutie obtine in jur de 30 de puncte.