Solutii Junior Challenge 2008

• Lista de probleme
• Grigo
• Reconst
• Gropi

Grigo

O analiza atenta a structurii permutarilor care respecta conditiile impuse ne arata ca daca ultima pozitie trebuie sa fie vizibila atunci in toate permutarile pe acea pozitie se va afla valoarea N, iar in caz contrar pe ultima pozitie se poate afla orice valoare intre 1 si N-1. De aici vine ideea construirii unei solutii bazate pe programare dinamica. Vom calcula un vector NrSol[i], reprezentand numarul de permutari de i numere ca respecta conditiile impuse daca se iau in considerare doar pozitiile de la 1 la i. Recurenta este destul de simplu de dedus. Astfel, daca pozitia i trebuie sa fie vizibila, atunci in mod evident NrSol[i] = NrSol[i-1], deoarece pe pozitia i este necesar sa se afle valoarea i. Daca pozitia i nu trebuie sa fie vizibila, atunci NrSol[i] = (i-1) * NrSol[i-1], deoarece pe ultima pozitie putem pune orice numar intre 1 si i-1, ramanandu-ne astfel i-1 valori distincte, pe care le putem reinterpreta ca fiind o permutare. Raspunsul cautat se va gasi in NrSol[N].

Reconst

Vom considera fiecare intrebare pusa ca fiind un interval de pozitii pentru care este necesar sa aiba o anumita suma data. O prima observatie care ne va ajuta sa rezolvam problema este ca daca nu avem doua intervale care sa inceapa pe aceeasi pozitie putem gasi foarte usor un algoritm greedy care sa furniezeze un raspuns corect. Parcurgem sirul de la ultima pozitie inspre prima, si vom considera ca toate elementele sale au valoarea 0, mai putin cele care sunt capatul de inceput al unui interval. Pentru aceste pozitii, vom considera valoarea lor ca fiind acel numar egal cu diferenta intre suma data a intervalului si suma valorilor deja alese pentru celelalte pozitii care fac parte din interval. In continuare vom analiza cazul in care exista cel putin o pereche de intervale care au acelasi capat de inceput. Fie doua intervale [A, B] si [A, C]. Daca B = C, atunci putem pur si simplu sa nu luam in calcul unul din cele doua intervale. In caz contrar putem considera ca B < C fara a restrange generalitatea. Fie S1 suma data pentru primul interval si S2 suma data pentru cel de-al doilea. Este destul de simplu de observat ca in loc de intervalul [A, C] de suma S2, putem sa consideram intervalul [B+1, C] de suma S2-S1. Repetand acest pas atat timp cat este nevoie vom ajunge la o configuratie in care nu exista doua intervale care sa aiba acelasi capat de inceput. Acest algoritm are complexitatea O(M²), deoarece fiecare segment poate fi inlocuit cu un alt segment mai mic de maxim M ori.

Gropi

Datorita restrictiilor mici pentru jumatate din teste, se poate implementa un algoritm trivial de complexitate O(M*C) care obtine 50 de puncte. Sa consideram un traseu de la (x₁ y₁) la (x₂ y₂), cu y1 ≤ y2 ( in caz contrar putem inversa punctul de plecare cu cel de sosire ). Cat timp y₁ < y₂ vom face una din urmatoarele actiuni:

• daca este posibil, ne deplasam spre dreapta (daca zona de pe coloana urmatoare si linia curenta nu este o zona cu gropi). Incrementam rezultatul cu 1;
• in caz contrar, schimbam linia si incrementam rezultatul cu 1.

In final afisam rezultatul obtinut, la care adaugam eventual 1 daca zona in care ne aflam este pe linia opusa liniei punctului destinatie (in acest caz mai trebuie sa facem un pas in sus sau in jos). Cum pentru fiecare traseu se efectueaza maxim C operatii, complexitatea va fi O(M*C).

Solutia de 100 de puncte are complexitatea O((N + M)log₂N). Se observa ca numarul de casute strabatute pe orizontala este constant (egal cu y₂-y₁+1), si trebuie sa aflam deci numarul de schimbari de directie pentru a afla raspunsul pentru un traseu. Vom imparti matricea data in zone, in functie de pozitionarea gropilor. O zona va fi formata dintr-o singura linie si coloane consecutive si in plus va avea proprietatea ca gropile pe care le contine sunt toate pe aceeasi linie. Se observa ca aceste zone apar alternativ pe linii: dupa o zona ce se afla pe linia 1, va veni o zona pe linia 2 si invers. In exemplul dat zonele apar astfel:

Pentru a evita cazurile particulare putem pozitiona o groapa pe coloana 0, pe linia opusa liniei primei gropi (cu coloana cea mai mica).

Dupa ce am realizat aceasta impartire vom cauta binar zonele in care se afla punctul de plecare si punctul de sosire. Sa presupunem ca zona punctului de plecare este i1 si cea a punctului de sosire este i2 si ca i1 < i2. Datorita structurii unui drum optim, putem identifica mai multe cazuri. De exemplu, daca x₁ este egal cu linia pe care se afla gropile in zona i1 si y₁ este mai mic decat coloana ultimei gropi din zona i1, iar punctul destinatie are aceeasi proprietate in functie de zona i2, atunci traseul va avea urmatoarea structura: prima data schimbam linia, apoi ne deplasam pe orizontala pana la zona i1+1, schimbam iarasi linia si ne deplasam pe orizontala pana la zona i1+2... si tot asa pana ajungem la zona i2 in dreptul coloanei y2, dupa care schimbam linia si ajungem in (x₂ y₂). Numarul de pasi in acest caz este (y₂-y₁+1) + 1 + (i2-i1) + 1. Dupa ce cautam binar este suficient sa determinam toate cazurile care exista si complexitatea devine O(1) deoarece se efectueaza un numar constant de adunari si scaderi.