Rezolvarile problemelor date in concurs

Teams

( problema usoara )

rezolvarea O(n^2):
- se ia fiecare pereche de pokemoni (i,j) cu i<j si se verifica daca este valida
- o astfel de solutia ar fi adus 50-70% din punctaj in funtie de implementare

rezolvarea O(n log n):

- se sorteaza sirul
- pentru fiecare pokemon se cauta binar intervalul de pokemoni cu care poate forma o echipa

rezolvarea O(n):

- se calculeaza v[i] = numarul de pokemoni cu forte mai mici sau egale cu i
- pentru fiecare pokemoni se adauga la solutie numarul de pokemoni din intervalul cu care poate forma o echipa ( atentzia un pokemon nu poate forma o echipa cu el insusi

Panou

( problema medie )

In primul rand observam ca nu are sens sa actionam un comutator de 2 sau mai multe ori. Plecam de pe linia N, coloana N a panoului A. Daca A[N][N] != B[N][N] este clar ca trebuie sa actionam
comutatorul situat pe aceasta pozitie. Apoi ne uitam la pozitiile (N, N-1) (N, N-2) .. (N, 1) in ordinea aceasta si procedam similar (unele comutari vor fi fortate). Apoi ne uitam la pozitiile (N-1, N) (N-2, N) .. (1, N) si iarasi unele dintre aceste pozitii vor trebui comutate neaparat. Continuam acest algoritm pentru fiecare pozitie (i, i) din panoul A, variabila i fiind parcursa descrescator. O implementare directa a algoritmului are complexitate O(N³), pentru a reduce complexitatea la O(N²) observam ca la un moment dat, noi trebuie sa stim in ce stare se afla becul situat pe o pozitie (i, j). Starea in care se afla acest bec este (A[i][j]+L[i]+C[j])%2, unde A[i][j] reprezinta starea initiala a becului, L[i] numarul de comutari efectuate pe linia i pana in prezent, iar C[j] numarul de comutari efectuate pe coloana j pana in prezent. Cum am efectuat doar acele comutari care trebuiau neaparat efectuate acesta este si numarul minim de comutari necesare.

Ordini

( problema grea )

...