Titlul: 768 Ksecv Scris de: Filip Cristian Buruiana din Septembrie 13, 2008, 15:17:25 Aici puteti discuta despre problema Ksecv (http://infoarena.ro/problema/ksecv).
Titlul: Răspuns: 768 Ksecv Scris de: Gabriel Bitis din Septembrie 13, 2008, 19:24:17 Cat va da pentru urmatoarele teste :
Cod: 50 7 Cod: 100 17 ? Titlul: Răspuns: 768 Ksecv Scris de: Filip Cristian Buruiana din Septembrie 13, 2008, 20:05:51 Pentru primul test: 2933
Pentru al doilea test: 6250 (obtinute cu sursa mea de 100 de puncte). Titlul: Răspuns: 768 Ksecv Scris de: tester din Septembrie 15, 2008, 10:26:06 Ar trebui sa intre o sursa cu complexitatea O(N*(K+log N)) nu?
Titlul: Răspuns: 768 Ksecv Scris de: Paul-Dan Baltescu din Septembrie 15, 2008, 10:46:32 Se poate face in O(N*K), nu stiu daca te ajuta asta. :)
Titlul: Răspuns: 768 Ksecv Scris de: tester din Septembrie 17, 2008, 17:54:28 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 :D Titlul: Răspuns: 768 Ksecv Scris de: Marius Stroe din Septembrie 19, 2008, 09:05:09 Complexitatea bună e O(N * K) nu O(N2). Iar complexitatea pe care o ai în rezolvarea ta e O(N2 * K). Nu-ţi rămâne decât să scapi de un N.
Titlul: Răspuns: 768 Ksecv Scris de: tester din Septembrie 19, 2008, 13:18:48 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? :) Titlul: Răspuns: 768 Ksecv Scris de: tester din Septembrie 21, 2008, 20:51:06 cam pustiu forumul....sau nu vrea nimeni sa ma ajute? :boxing:
Titlul: Răspuns: 768 Ksecv Scris de: Filip Cristian Buruiana din Septembrie 22, 2008, 11:48:05 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 :peacefingers:. Titlul: Răspuns: 768 Ksecv Scris de: tester din Septembrie 22, 2008, 19:57:07 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 ] Titlul: Răspuns: 768 Ksecv Scris de: chisinau gheorghita din Decembrie 03, 2008, 17:36:59 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) Titlul: Răspuns: 768 Ksecv Scris de: Florian Marcu din Iunie 23, 2009, 11:40:59 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? :-k
Titlul: Răspuns: 768 Ksecv Scris de: Marius Stroe din Iunie 23, 2009, 14:47:51 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? :-k Încearcă să rezolvi problema 8 de aici (http://infoarena.ro/deque-si-aplicatii#problema-8). După aceea vei rezolva imediat şi Ksecv. Titlul: Răspuns: 768 Ksecv Scris de: Paul-Dan Baltescu din Iunie 23, 2009, 15:12:25 Cred ca Ksecv e totusi mai usoara ca problema aia. :)
Titlul: Răspuns: 768 Ksecv Scris de: Florian Marcu din Iunie 23, 2009, 15:23:20 Multumesc! Sper sa-mi iasa. :)
Titlul: Răspuns: 768 Ksecv Scris de: Marius Stroe din Iunie 23, 2009, 17:00:58 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. :) Titlul: Răspuns: 768 Ksecv Scris de: Petru Trimbitas din Februarie 07, 2013, 16:59:31 Cred ca e putin cam mica limita de timp :(
Titlul: Răspuns: 768 Ksecv Scris de: Rapeanu George din Aprilie 20, 2017, 11:45:01 Am O(N*K)+parsare si tot nu intra in timp. Cred ca ar trebui marita limita
|