Diferente pentru junior-challenge/solutii intre reviziile #10 si #24

Nu exista diferente intre titluri.

Diferente intre continut:

h3. ( problema usoara )
rezolvarea $O(n^2)$:
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
 - o astfel de solutia ar fi adus $50-70%$ din punctaj in functie de implementare
rezolvarea $O(n log n)$:
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
 - 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)
h2. 'Panou':problema/panou
h3. ( 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^3^)$, pentru a reduce complexitatea la $O(N^2^)$ 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.
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^3^)$, pentru a reduce complexitatea la $O(N^2^)$ 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.
h2. 'Ordini':problema/ordini
h3. ( 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{~0~} * 10^0^$}. Daca stim coeficientii {$c{~0~}$}, {$c{~1~}$}, ... {$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^i^$} obtine exact aceasta relatie. Coeficientii c{~0~}, c{~1~}... c{~N-1~} vor fi deci toti egali pentru ca fiecare cifra $x$ poate fi pusa pe orice pozitie.
Daca frecventele cifrelor sunt {$f{~0~}$}, {$f{~1~}$}... {$f{~9~}$}, atunci cifra $x$ poate aparea pe o pozitie in exact !junior-challenge/solutii?formula.jpg! 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:
!junior-challenge/solutii?formula2.jpg!, 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.

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.