Revizia anterioară Revizia următoare
Soluţii ONIS 2016, Runda 1
- Lista de probleme
- A. MaxSubSum
- B. Avioane2
- C. Minlcm
- D. Unlock
- E. Min Max Store
- F. Pokemon3
- G. Puzzle2
- H. Subpermutari
- I. Nucleul Valoros Season 2
Cine a rezolvat o problema a carei solutie nu este inca adaugata, este rugat sa o scrie in sectiuniile de mai jos :)
A. MaxSubSum
Datorita limitei lui N (N <= 2.000), solutia triviala in care matricea este calculata iar apoi este aplicat algoritmul pentru submatrice de suma maxima O(N^3) nu va intra in timp.
Se observa ca orice submatrice este de fapt data de o subsecventa din primul sir S1 si o subsecventa din al doilea S2. Suma elementelor a submatricei este de fapt len(S1) * sum(S2) + len(S2) * sum(S1).
Se va calcula pentru fiecare sir max[i] = suma maxima a unei subsecvente de lungime i in O(N^2).
Avand max1 si max2 (pentru cele doua siruri), in O(N^2) putem incerca toate lungimile L1, L2 (1 <= L1 <= N, 1 <= L2 <= M) de secvente posibile pentru cele doua siruri iar cu formula de mai sus putem calcula suma maxima ce se poate obtine pentru lungimile respective. Vom salva si afisa valoarea maxima.
B. Avioane2
C. Minlcm
D. Unlock
E. MinMaxStore
F. Pokemon3
O observatie importanta este ca pentru a castiga "din prima" Ash va alege (din lista sa de pokemoni) la fiecare lupta un pokemon care este super eficient fata de cel al adversarului. Asta inseamna ca nu conteaza ordinea bataliilor ci doar tipurile de pokemoni adversi ce trebuie infranti. Datorita limitei mici a lui N (N <= 20) se pot incerca toate posbilitatile de a alege pokemonii (backtracking). O configuratie (un anume grup de pokemoni alesi) se considera valida daca nu exista niciun pokemon advers ce nu poate fi infrant folosindu-ne de pokemonii din configuratia curenta. Se va retine numarul cel mai mic de pokemoni din configuratiile valide. Complexitatea solutiei, data de backtracking, este de O(2^N).
