Puncte4
Autor: Vlad Stoian, software development engineer, Amazon România
Descrierea soluţiei (Vlad Stoian)
Soluţie – 100 p – Complexitate O(N2*K)
Elementele din imaginea alăturată reprezintă 2 pătrate NxN vecine. A este numărul de puncte de pe prima coloană, B numărul de puncte de pe următoarele N-1 coloane şi C de pe ultima coloana. Din enunţ ştim că A + B = P, respectiv B + C = P. De aici deducem că A = C. Asta înseamnă că dacă alegem ca pe prima coloană să punem un număr de puncte, la fel vom alege şi pentru toate coloanele pentru care i % n == 1. Generalizând, fiecare coloană va avea acelaşi număr de puncte ca i - n si i + n.
Fie nrci numărul de puncte de pe coloana i. Împărţim coloanele pe N clase de echivalenţă pe baza operaţiei i % n. Fie clsi numărul de coloane din clasa de echivalenţă i.
Observăm că, in funcţie de M, o coloană va putea fi găsită de M / N sau M / N + 1 ori aşadar clsi va putea lua doar două valori. Sunt Comb(n, k)clsi posibilităţi de a aranja P puncte in fiecare dintre cele clsi coloane, deci toate combinările la puterile M / N si M / N + 1 pot fi precalculate. Deoarece M / N poate fi un număr destul de mare, vom folosi un algoritm de ridicare rapidă la putere.
Pornind de la aceste descoperiri, ajungem la 2 idei de rezolvare.
1. Partiţionarea sumei P (backtracking)
Încercăm să partiţionăm P în p1, p2, .. pn unde Suma(pi) = P.
2. Programare dinamică
Fie dp[i][j] numărul de posibilităţi de a umple toate coloanele din clasele 1 până la i, astfel încât Suma(nrck) = j;
De aici rezultă că:
dp[i][j+k] = suma pentru K = 0 <- P-j din dp[i-1][k] * Comb(n, k)clsi
Se observa si ca, pentru x > i * i / 2, dp[i][x] == dp[i][i * i - x].
Implementarea recursivă primeşte 80 de puncte, iar cea iterativă 100 de puncte.
