Dinozaur

Se observa ca daca exista o subsecventa cu lungime x care apare de doua ori atunci va exista o subsecventa de lungime x-1 care apare de 2 ori. De aici ne vine ideea de a cauta o litera care apare de doua ori.
O alta observatie ar fi ca daca , conform principiului cutiei , avem peste 26 de litere atunci rapunsul este mereu 1.

Impartiri

Vom porni de la observatia ca daca distanta maxima dintre doua drepte orizontale consecutive este l1 si distanta maxima dintre doua drepte verticale este l2, atunci configuratia curenta indeplineste conditia din enunt daca l1*l2<=K (acela va fi sub-dreptunghiul de arie maxima]). Acum, vom construi o dinamica DP[v][i] = numarul de moduri in care putem taia o linie de lungime i (de la origine pana la punctul (0, i)) astfel incat sa nu avem distanta mai mare decat v intre oricare doua drepte consecutive, stiind ca deja sunt trasate dreptele care taie linia curenta in origine si in punctul i. Astfel, vom fixa distanta dintre ultima dreapta care taie linia curenta si cea “predefinita” care taie linia in punctul i. Aceasta poate fi oricat intre 1 si v, de unde deducem ca DP[v][i] = DP[v][i-1] + DP[v][i-2] + ... + DP[v][i-v]. Calcularea valorilor DP se poate face in complexitate de timp O(N^2) folosind sume partiale.

Avand sirul DP calculat, vom incerca sa deducem in cate moduri putem combina taieturile pe cele doua axe ca sa obtinem rezultatul dorit. Presupunand ca distanta maxima dintre doua drepte consecutive care taie axa OX este D si ca exista cel putin doua drepte consecutive care sa fie situate la distanta D, observam ca distanta maxima dintre doua drepte care taie axa OY este min (K/D, M) (dreptele trebuie sa taie dreptunghiul), iar numarul de impartiri pentru distanta fixata pe OX va fi (DP[D][N]-DP[D-1][N])*DP[min (K/D, M)][M] (primul termen din produs reprezinta numarul de stari in care exista cel putin 2 drepte cu distanta D, care este si distanta maxima, iar cel de al doilea termen reprezinta numarul de stari care, combinate cu starile din primul termen, genereaza o impartire valida a dreptunghiului). In final, nu trebuie decat sa facem suma acestor produse.

Mai trebuie cateva optimizari la memorie pentru ca solutia sa se incadreze in limite. Observam ca in calcularea lui DP[v][i] avem nevoie doar de linia curenta, si astfel putem folosi doar un vector pentru a calcula o linie din matricea DP, iar in calcularea produselor avem nevoie doar de termeni de forma DP[v][N] si DP[v][M], si astfel putem retine inca doi vectori in care sa salvam exact aceste valori, iar complexitatea de memorie va fi O(N).

Orient

Consideram graful format din muchiile (a,b) din enunt cu costul 0 si muchiile (b,a) cu costul c.
In acest graf pentru fiecare muchie (a,b) vom afla drumul minim de la b la a. Costul ciclului va fi egal cu costul drumului minim de la b la a + costul muchiei (a,b)

Zaruri

Pentru inceput, sa presupunem ca n=2. Vom incerca sa gasim o strategie optima pentru a maximiza valoarea medie. Putem observa ca daca prima data am obtinut valoarea 1, vom vrea sa dam inca odata cu zarul (ce poate iesi mai rau de atat?), si vom incerca sa extindem aceasta observatie. Presupunand ca daca dam valori mai mici sau egale cu X, vom vrea sa dam inca odata cu zarul, putem gasi o formula pentru valoarea medie care se obtine in acest caz (sa-i spunem S [2]). Probabilitatea sa mai dam odata cu zarul va fi X/6 (sunt X valori pentru care dam inca odata si 6 valori in total), iar valoarea medie care se obtine daca dam o singura data cu zarul este (1+2+...+6)/6 (adica S [1]). Acum avem probabilitate 1/6 sa dam 6 cu zarul, probabilitate 1/6 sa dam 5, ..., probabilitate 1/6 sa dam X+1. Astfel, mai adunam 1/6 * ( (X+1) + (X+2) + ... + 6 ) la S [2]. Observam ca sunt singurele situatii care pot aparea, si atunci formula pentru S [2] devine X/6 * S [1] + 1/6 * ( (X+1) + (X+2) + ... + 6 ) pentru un X fixat. Formula este aceeasi si pentru n mai mare, deoarece singura mdoficiare este la cazul in care dam o valoare mai mica sau egala cu X, deoarece vom inmulti X/6 cu S [n-1] (valoarea medie maxima pe care o putem obtine daca dam de inca maxim n-1 ori cu zarul), si avem formula de recurenta S [n] = max ( X/6 * S [n-1] + 1/6 * ( (X+1) + (X+2) + ... + 6 ) ), pentru orice X natural din intervalul [0, 6].