Viteze

Hamster

Pentru rezolvarea acestei probleme se va folosi programarea dinamica.
Mai exact, $dp[i][j] =$ D-ul minim pentru a acoperi primele $i$ gropi cu $j$ placi. Recurenta este: $dp[i][j] = min(max(dp[k-1][j-1], X_i - X_k))$ , unde $k = 1, 2, \: ..., i$ ; - folosim a $j$ -a placa pentru a acoperi fix gropile $k \: ... \: i$ , iar pentru celelalte $k - 1$ gropi vom folosi cele $j - 1$ placi ramase si vom lua $k$ -ul optim. Acest algoritm are complexitate timp $O(N^3)$ .

Pentru a ajunge la o complexitate de $O(N^2 * log(N))$ trebuie observat ca functia $f(k) = dp[k][j]$ este crescatoare si ca functia $g(k) = X_i - X_k$ este descrescatoare. Deci, functia $h(k) = max(dp[k-1][j-1] , X_i - X_k)$ este unimodala (adica tot scade si apoi tot creste) si se poate cauta binar primul $k$ pentru care $h(k) > h(k+1)$ (minimul functiei).

Pentru $100$ de puncte vom face trecerea de la $dp[i][j]$ la $dp[i][j+1]$ folosind un iterator. Mai exact, fie $k_j$ minimul functie actuale $h_j(x)$ . Este clar ca $k_j + 1 \geq k_j$ , unde $k_j + 1$ este minimul functie $h_{j + 1}(x)$ . Astfel, putem incrementa $k$ -ul optim gasit la pasul $j$ de cate ori este nevoie pentru a afla $k$ -ul optim la pasul $j + 1$ . Complexitatea finala este $O(N^2)$ amortizat.
r
La ce ne ajuta oare dinamica calculata? Acum putem cauta binar raspunsul folosind relatia ca ne intereseaza cel mai mic $p$ astfel incat $d[K][p]$ ≤ $D$

Complexitate totala: $O(N ^ 2 + Q log N)$

Superbec

Prima observatie pe care trebuie sa o facem este ca daca un buton este apasat de $3 \cdot K + R$ ori, $0 \leq R < 3$ , sirul este modificat ca si cand ar fi fost apasat de $R$ ori. Astefel, sirul poate lua $3^9$ forme, in functie de numarul de apasari al fiecaruia dintre cele $9$ butoane. Fiecare forma este data de un sir de $9$ triti care indica, pentru fiecare buton, numarul relevant de apasari aplicate lui. Urmeaza sa verificam, pentru fiecare sir, daca forma respectiva se poate potrivi cu sirul dat in input.
A doua observatie este legata de . Sa notam cu numarul total de apasari relevante aplicate celor butoane. Ca sirul sa aiba sens, trebuie sa fie in primul rand multiplu de . Daca sirul este corect si din punct de vedere al corespondentei cu sirul din input, trebuie sa adaugam la rezultat numarul de variante de a obtine sirul cu apasari de butoane. Acest numar este egal cu numarul de moduri de a pune obiecte identice in cutii, care este egal cu combinari de luate cate . Putem calcula acest numar modulo in folosind notiunea de invers modular.
- Folosind cele $2$ observatii putem lua $70 \%$ din punctajul maxim: Incercam sa potrivim cele $3^9 \approx 20 \: 000$ forme ale sirului de triti peste sirul dat in input in $O(N)$ timp per sir, iar in caz ca sirul se potriveste, adunam la raspuns numarul de moduri de a obtine sirul de triti din $M$ mutari.
A treia observatie, necesara pentru obtinerea punctajului maxim, este ca nu este nevoie ca verificarea potrivirii sirului de triti sa fie efectuata in $O(N)$ timp. Daca ne uitam la cele $9$ butoane, observam ca modificarile aduse sirului de fiecare buton in parte se repeta fie din $1$ in $1$ , fie din $2$ in $2$ , fie din $3$ in $3$ , fie din $5$ in $5$ . Asadar, modificarile aduse de toate butoanele sunt identice din $lcm(1, 2, 3, 5) = 30$ in $30$ , deci nu trebuie sa facem decat $30$ de pasi pentru verificarea potrivirii sirurilor, daca avem precalculat $t[i] =$ caracterul aflat la pozitiile $30 \cdot K + i$ in sirul din input, precalculare care poate fi facuta in timp $O(N)$ .

Complexitate timp: $O(T \cdot N + T \cdot 30 \cdot 3^9)$
Complexitate memorie: $O(1)$

infoarena informatica de performanta

Viteze

Hamster

Superbec