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 )

Sa presupunem ca dorim sa aflam suma numerelor care se pot forma cu cifrele date in care ignoram conditia care impune ca prima cifra sa fie nenula. Fie N numarul total de cifre ( din restrictiile problemei N < 1001 ). Folosind descompunerea in baza 10, rezultatul se va scrie sub forma c_N-1 * 10^N-1 + c_N-2 * 10^N-2 + ... c₀ * 10⁰. Daca stim coeficientii c₀, c₁, ... c_N-1, atunci stim si rezultatul ( toate calculele vor fi facute modulo M ). Se observa ca daca intr-un numar format cifra x apare pe pozitia i, atunci trebuie sa adunam la coeficientul c_i numarul x * Res, unde Res este numarul de numere care se pot forma si in care cifra x apare pe pozitia i - daca descompunem fiecare numar in baza 10 ca mai sus si dam factor comun 10ⁱ obtine exact aceasta relatie. Coeficientii c₀, c₁... c_N-1 vor fi deci toti egali pentru ca fiecare cifra x poate fi pusa pe orice pozitie.
Daca frecventele cifrelor sunt f₀, f₁... f₉, atunci cifra x poate aparea pe o pozitie in exact (!junior-challenge/solutii?formula.jpg!) numere.