infoarena

Aici puteți discuta despre problema Derdelus (http://infoarena.ro/problema/derdelus).

Eu am calculat, incepand de sus pana jos, numarul de posibilitati pentru fiecare cub parcurgand in sus si pe diagonala pana la ultimul cub de unde ar fi putut sari oaia. O(N^2*M) din cate imi dau seama. Care e ideea de 100?

Poti sa tii niste sume partiale si astfel sa calculezi recurenta in O(1)

Am completat eu articolul cu solutii cu ce am stiut.

http://infoarena.ro/algoritmiada-2011/runda-2/solutii

Traiasca familia! Mi-a iesit  :D
Am uitat ca in operatiile cu module poate da valoare negativa  :aha:

Poti sa fii mai explicit? Adica tocmai pt ca % respecta semnul, cu ce mai trebuie sa fii tu atent?

Adica, de exemplu ai 7 - 5 = 2 => 7%3 - 5%3 = 1 - 2 = -1

Ms. Am gasit problema. Se pare ca / nu tine cont de semn.

_______________________________

Daca folosim algoritmi mai performanti de inmultire a matricilor putem obtine timpi mai buni, in particular cu algoritmul lui Strassen obtinem o complexitate de O ( K * N ^ 2.807 + Q ) , dar niciunul dintre acesti algoritmi nu obtine punctaj maxim.

Dc e algoritm performant daca are complexitate N ^ 2.807 (si ceva)?

Pentru ca algoritmul clasic are complexitatea O(N^3) si 2.807 < 3.

imi poate da si mie un test pe care credeti ca ar putea pica  nu intaleg ce gresesc(fac solutia n^3) si iau WA pe testele 3 si 4 #-o

Care ar fi raspunsul pentru :  5 4 0 ??
Si cum trebue de procedat, daca scaderile de module dau numere negative  ](*,)

8 12 14 12 8 

(a - b) % c = (a - b + c) % c

Ms mult, acum am luat 100, apropo, pe testul cela tot asa imi dadea si mie, problema era doar la modulo  \:D/
LE: Am corectat  :ok:

La modulo*. Modulul se refera la valoare absoluta.

Nu am inteles ideea cu sumele partiale. Eu il fac normal, dar iau 50 puncte. Am incercat cu sumele partiale, dar nu inteleg recurenta la matricea sum. Daca ma poate ajuta cineva, i-as ramane indatorat.  :!: =D&gt;

Sa zicem ca esti la celula (7, 1) (numerotare de la 1) si M = 4. Poti ajunge la ea doar de sus, mai exact din (3, 1), (4, 1), (5, 1) si (6, 1). Decat sa aduni separat valoarea de la fiecare dintre acestea la valoarea celulei curente, mai bine aduni suma de pe toata coloana (de la (1, 1) pana la (6, 1)) si scazi ce e in plus (de la (1, 1) pana la (2, 1)). Deci, trebuie sa tii o matrice ca retine suma pe coloana de la (i, j) in sus (pana unde se poate merge) si la fel si una pentru diagonala.

Sunt 90% sigur ca limita de timp nu e buna pe problema asta... Am o sursa in O(n^2) si am TLE la ultimele 2 teste.
Acelasi rezultat si dupa ce am parsat... Va rog sa verificati  :)

Limita de timp la aceasta problema este buna. Tie nu iti intra in timp pentru ca ai declarat variabilele long long in loc de int, ceea ce incetineste foarte mult programul.

Wow... Multumesc frumos. Scuze pentru afirmatia gresita. :)
Am luat 100  :yahoo: