Pentru a afla de cate ori trece un robotel prin pozitia (X Y) avem nevoie de urmatoarele informatii:

1. Cate mutari efectuam daca pornim din pozitia (X Y) si ajungem tot in (X Y) - lungimea ciclului care cuprinde pozitia (X Y). Daca pozitia (X Y) nu se afla pe un ciclu atunci lucrurile se simplifica (acesta este un caz special care se trateaza separat).
2. Cate mutari efectueaza fiecare robot pana ajunge in (X Y). Desigur, pot exista si roboti care nu ajung niciodata in (X Y).

# Cate mutari efectuam daca pornim din pozitia ({$X Y$}) si ajungem tot in ({$X Y$}) - lungimea ciclului care cuprinde pozitia ({$X Y$}). Daca pozitia ({$X Y$}) nu se afla pe un ciclu atunci lucrurile se simplifica (acesta este un caz special care se trateaza separat).
# Cate mutari efectueaza fiecare robot pana ajunge in ({$X Y$}). Desigur, pot exista si roboti care nu ajung niciodata in ({$X Y$}).

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].

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$}].

h2. PScNv

(problema simpla clasele XI-XII)

 
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.