Rezolvarile problemelor date in concurs

Teams

( problema usoara )

rezolvarea O(n²):
- 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 functie 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 pokemon se adauga la solutie numarul de pokemoni din intervalul cu care poate forma o echipa (atentie, 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 numere, formula care rezulta din calculul numarului de anagrame pentru un cuvant dat, care este dat de factorialul lungimii cuvantului supra produsul factorialelor frecventelor fiecarei litere in parte. Pentru a calcula efectiv acest numar, vom face toate simplificarile posibile ( impartind prin cel mai mare divizor comun dintre doua numere, primul de la numarator si al doilea de la numitor ) si vom obtine in final un sir de numere care trebuie inmultite ( modulo M ).
Daca prima cifra poate fi 0, rezultatul este deci:
, unde numarul de 1 este dat de suma frecventelor cifrelor.
Desi formula pare la prima vedere complicata, ea rezulta destul de usor din formula numarului de anagrame ale unui cuvant dat si din scrierea numerelor in baza 10.

Daca prima cifra nu poate fi 0 procedam in felul urmator: fixam prima cifra C ( de la 1 la 9 ), scadem cu 1 frecventa cifrei selectate si calculam conform rezultatului de mai sus la care mai adaugam C * Res * 10^N. In final vom aduna ( tot modulo M ) cele 9 numere obtinute si afisam rezultatul.

Aceasta este una din solutii care obtinea punctajul maxim in concurs. Exista si solutii mai rapide care folosesc combinari, insa s-a considerat ca aceste cunostinte depasesc nivelul claselor 7-9.