768 Ksecv

[•filipb]

Aici puteti discuta despre problema Ksecv.

[•gabitzish1]

Cat va da pentru urmatoarele teste :

Cod:

50 7
41 467 334 500 169 724 478 358 962 464 705 145 281 827 961 491 995 942 827 436 391 604 902 153 292 382 421 716 718 895 447 726 771 538 869 912 667 299 35 894 703 811 322 333 673 664 141 711 253 868 

Cod:

100 17
41 467 334 500 169 724 478 358 962 464 705 145 281 827 961 491 995 942 827 436 391 604 902 153 292 382 421 716 718 895 447 726 771 538 869 912 667 299 35 894 703 811 322 333 673 664 141 711 253 868 547 644 662 757 37 859 723 741 529 778 316 35 190 842 288 106 40 942 264 648 446 805 890 729 370 350 6 101 393 548 629 623 84 954 756 840 966 376 931 308 944 439 626 323 537 538 118 82 929 541 

?

[•filipb]

Pentru primul test: 2933
Pentru al doilea test: 6250

(obtinute cu sursa mea de 100 de puncte).

[zombie_tester_2]

Ar trebui sa intre o sursa cu complexitatea O(N*(K+log N)) nu?

[•pauldb]

Se poate face in O(N*K), nu stiu daca te ajuta asta.

[zombie_tester_2]

M-am gandit si eu putin la problema.....da nu prea imi dau seama de O(n ^ 2)! Ma gandeam la ceva de genu : D[ i ][ j ] - suma minima daca am ajuns la pozitia i si am j secvente.....dar dupa cum am gandit eu iese O(n ^ 3) (iau minimu dintre           
D[ 1 ][ j-1 ]+max[ 2,i ],D[ 2 ][ j-1 ]+max[ 3,i ],.....,D[ i-1 ][ j-1 ]+max[ i,i ], unde max[ i,j ] e maximul din intervalul V[ i ]....V[ j ])
Orice indiciu ar fii binevenit

[•Marius]

Complexitatea bună e O(N * K) nu O(N²). Iar complexitatea pe care o ai în rezolvarea ta e O(N² * K). Nu-ţi rămâne decât să scapi de un N.

[zombie_tester_2]

la complexitatea aia ma refeream...doar ca m-am grabit si in loc de K am spus N.
stiu ca trebe sa scap de un N...dar intrebarea este cum?

[zombie_tester_2]

cam pustiu forumul....sau nu vrea nimeni sa ma ajute? 

[•filipb]

Intr-adevar, faci dinamica care ai spus-o tu:
M(i,j) = costul minim daca imparti primele j numere in i secvente
Relatia de recurenta este destul de usor de scos:
M(i,j) = minim(M(i-1, k) + maxim(v(k+1), ... v(j))), unde 0 <= k < j => O(N^2 * K) daca faci direct.

Un hint pentru O(N*K): Pentru a calcula M(i,j) ai doua cazuri: ori v(j) este maxim in ultima subsecventa (a i-a), ori nu. Daca consideri alt element ca fiind maxim in ultima subsecventa atunci M(i,j) = M(i, B), unde B este cel mai din dreapta element a. i. v(B) >= v(j). Egalitatea are loc deoarece maximul ultimei secvente trebuie sa fie undeva mai in stanga lui B, si elementele v(B+1) ... v(j) nu influenteaza in niciun fel costul final. Gandeste-te ce se intampla daca v(j) este maxim in secventa lui si noteaza costul pe cazul asta cu valoare_caz_2. Aceasta valoare poate fi obtinuta in O(1) amortizat.
In final M(i,j) = minim(M(i, B), valoare_caz_2).

Daca nu descoperi cum poate fi obtinuta valoare_caz_2, posteaza pe forum ca sa te lamurim .

[zombie_tester_2]

Ms foarte mult filip pt ajutor.

Banuiesc ca caz_2 e minimul dintre M[ i-1 ][ k-1],M[ i-1 ][ k-2 ]........M[ i-1 ][ i-1 ]

[•gh09]

cum se face in O(n*k) ? am scos O(n *(k + log n)) ...am bagat si parsare si iau numa 4 teste, pe restu TLE

LE....am defapt O(n*k*log n)

[•Florian]

M-am gandit la problema asta, si m-am blocat in ceea ce priveste reducerea complexitatii. Am citit postul lui Buru de mai sus si am inteles ideea. Nu inteleg insa cum as putea calcula acel B in O(1). E clar ca valoare_caz_2 este minim(S[i-1][X) + v[ j ], cu X de la B+1 la j-1 ( intervalul pe care v[ j ] "domina" ) . Daca atunci cand fac trecerea de la j, la j+1, B-ul s-ar modifica in acelasi sens mereu, mi-ar fi usor sa folosesc un deque. Problema e insa ca B-ul fie ramane acelasi sau scade ( daca v[ j ] > v[ j - 1 ] ), fie ia valoarea lui j-1 ( daca v[ j ] <= v[ j-1 ] ). Ma cam baga in ceata acea "resetare" ( B = j-1 ), pentru ca ar trebui sa golesc deque-ul, si de asemenea, cand va mai scadea, voi baga elemente pe care le-am mai bagat, ceea ce nu mai duce la O(1) amortizat. Gresesc ceva in "comportarea" lui B ? Daca nu, cum ar trebui sa rezolv? 

[•Marius]

M-am gandit la problema asta, si m-am blocat in ceea ce priveste reducerea complexitatii. Am citit postul lui Buru de mai sus si am inteles ideea. Nu inteleg insa cum as putea calcula acel B in O(1). E clar ca valoare_caz_2 este minim(S[i-1][X) + v[ j ], cu X de la B+1 la j-1 ( intervalul pe care v[ j ] "domina" ) . Daca atunci cand fac trecerea de la j, la j+1, B-ul s-ar modifica in acelasi sens mereu, mi-ar fi usor sa folosesc un deque. Problema e insa ca B-ul fie ramane acelasi sau scade ( daca v[ j ] > v[ j - 1 ] ), fie ia valoarea lui j-1 ( daca v[ j ] <= v[ j-1 ] ). Ma cam baga in ceata acea "resetare" ( B = j-1 ), pentru ca ar trebui sa golesc deque-ul, si de asemenea, cand va mai scadea, voi baga elemente pe care le-am mai bagat, ceea ce nu mai duce la O(1) amortizat. Gresesc ceva in "comportarea" lui B ? Daca nu, cum ar trebui sa rezolv? 

Încearcă să rezolvi problema 8 de aici. După aceea vei rezolva imediat şi Ksecv.

[•pauldb]

Cred ca Ksecv e totusi mai usoara ca problema aia.

[•Florian]

Multumesc! Sper sa-mi iasa. 

[•Marius]

Cred ca Ksecv e totusi mai usoara ca problema aia.

Ai dreptate, dar ideea de care are nevoie la Ksecv se găseşte acolo.

[•S7012MY]

Cred ca e putin cam mica limita de timp

[•georgerapeanu]

Am O(N*K)+parsare si tot nu intra in timp. Cred ca ar trebui marita limita