409 Sotron

[•DITzoneC]

Aici puteţi discuta despre problema Sotron.

[•Florian]

Nu stiu de ce, dar iau 70 de puncte, cu WA pe trei teste!! Nu vad de ce se intampla lucrul asta. Adik, dupa parerea mea este imposibil sa existe cazuri particulare la o problema ca asta!!! Are cineva vreo idee? 

[•cos_min]

Maximul poate fi si negativ, probabil aici gresesti.

[•Florian]

Nu...initializez maximul cu  - MALONG (minus MAXLONG) (lucrez in c++)... Imi scapa ceva..dar nu `mi dau seama in niciun fel...

[•Tabara]

  iau 90.
WA pe testul 8.Mi-am verificat sursa cu testele oficiale si acela e intr-adevar singurul test pe care nu merge.Nu inteleg totusi de ce se intampla asta.Am verificat drumul pe exemple mai mari si merge prin matrice bine.Nu imi dau seama ce ar puteas fi gresit....

 

Am initializat maximul cu (-1)*(2<<31 ), deci nu asta ar fi problema.[cel putin nu cred].

[Later Edit] Nevermind...am luat 100  . Uitasem sa tratez separat cand n-ul este par si impar.

[•mihai0110]

ce testezi separat ca nu am inteles ce ai vrut sa zici, eu tot 90 de puncte iau, la oni am luat 50 , (am facut cu o matrice in care tineam maximu (b[i+1][j]+ a[j] , a[ i ][j]) sau (b[j-1]+ a[j] , a[ i] [j]) - depinde de paritatea liniei- si afisam maximu din b matricea b)

[•Tabara]

ce testezi separat ca nu am inteles ce ai vrut sa zici, eu tot 90 de puncte iau, la oni am luat 50 , (am facut cu o matrice in care tineam maximu (b[i+1][j]+ a[j] , a[ i ][j]) sau (b[j-1]+ a[j] , a[ i] [j]) - depinde de paritatea liniei- si afisam maximu din b matricea b)

Poi eu nu tratam cazul in care n este par.
Cand n este impar, porneam din fiecare casuta albastra de pe prima coloana si faceam drumul ei firesc, ( si calculam secventa de suma maxima ).Apoi de pe fiecare casuta alba de pe ultima linie porneam iarasi drumul firesc ( si din nou secventa de suma maxima ). Astfel alegeam maximul dintre toate secventele si luam 90.Problema e ca uitasem ca n poate fi si par, astfel ca ultima linia incepea cu o casuta alba.Deci am facut acelasi algoritm cu pornire din casutele albastre de pe prima coloana si ulterior casutele albe *( incepand cu prima de pe ultima linie ) ai am luat 100.
Ar mai fi o observatie.Era un test printre cele oficiale pe care nu il luam pentru ca secventa de suma maxima era chiar un element al matricei ( unul singur ) si eu nu verificam la initializarea in dinamica de secventa de suma maxima daca maximul putea fi chiar unul dintre elemente.

Sper sa iti iasa! 

[•Florian]

Eu am facut putin mai diferit...Pt fiecare element al matricii urmam drumul firesc pana ma opream ajungand la prima linie sau la ultima coloana, si calculam suma tuturor elemntelor prin care treceam, comparand la fiecare pas cu suma maxima obinuta pana atunci. Insa iau doar 70 de puncte..nu vad unde as putea gresi...

[•vanila_CPP]

si eu iau 70 de puncte pe o idee pe care am luat 100 la byNET. are careva vreo sugestie? 

[•ciprianf]

Nu stiu daca ai rezolvat-o intre timp dar uite o idee: i-ati matricea b(i)(j)=suma maxima care se poate obtine pornind de pe pozitia (i,j)

[•Mishu91]

ia-ti matricea b(i)(j)=suma maxima care se poate obtine pornind de pe pozitia (i,j)

Intra in n^2 asa?

[•fireatmyself]

matricea respectiva se calculeaza in O(n^3).

[•Mishu91]

Si intra in timp cu O(n^3) ?

[•fireatmyself]

da, daca tii cont de o mica observatie.

[•Mishu91]

Dar o dinamica in n^2 e mai eficienta si e relativ simplu de implementat

[•fireatmyself]

nu te contrazic. daca ai scos n^2 cu atat mai bine. eu am calculat in n^3 matricea respectiva.

[•ctlin04]

Stie cineva ce are special testul 5, iau WA si nu inteleg care ar fi problema, pot sa existe ceva cazuri speciale la problema asta ?