008 Subsir crescator maximal

[•alexandru92]

Ar putrea sa-mi dea cineva un hint despre cum pot rezolva problema folosind aib ?

[•blasterz]

Normalizezi vectorul, ca să ai elemente în intervalul 1-n.
Te gândeşti la dinamica normală :
dp[ i ] = max ( dp [ j ] cu a [ i ] > a [ j ] ) + 1

E si tu trebuie să iei un maxim  din dp- urile până în momentul respectiv, dar luând în considerare doar elementele mai mici decât a [ i ].

Deci o să menţii un aib[1 . . . Valoarea maximă a din vectorul normalizat ] ce îţi da maximul dp-urilor elementelor < o anumită valoare.

Sper că ai înţeles unde bat. . . PS. Sunt pe tren si editez de pe mobil

[•alexandru92]

In mare cred ca mi-am facut o imagine, multumesc
Dar ce inseamna "normalizezi vectorlul", il sortezi ?

[•Mishu91]

Îl sortezi și reții doar ordinea numerelor. De exemplu, șirul 13 98 44 11 va deveni 2 4 3 1.

[•dudut]

cine ma poate ajuta si pe mine putin? m-am gandit sa rezolv problema in felul urmator:
fac un for cu care citesc sirul, dar in acelasi timp fac si comparatiile
atunci cand urmatorul numar nu mai este ordonat, verific daca lungimea sirului este maxima, si salvez cu max locul de unde incepe sirul, si cu nrmax nr de elemente crescatoare care nu se repeta
dar nu stiu din ce motiv, pe 7teste nu e bun nr maxim de elemente ordonate
cine imi poate da un indiciu?
http://infoarena.ro/job_detail/405201?action=view-source

[•Florian]

Tu calculezi cea mai lunga subsecventa crescatoare. Problema cere cel mai lung subsir crescator. subsir != subsecventa.

[•dudut]

si care e diferenta ca nu ma prind

[•Florian]

subsecventa = elementele apar pe poziti consecutive in sirul initial
subsir = elementele nu apar neaparat pe pozitii consecutive in sirul initial.

[•dudut]

aha,ms
se pare ca nu am fost prea atent
poate o sa refac sursa maine

[•ssergiuss]

Imi poate spune cineva daca as mai putea face optimizari la sursa mea cu arbori de intervale sa iau 100p? Iau TLE pe un test si nu stiu ce sa mai optimizez   .
L.E. Am mai trimis-o o data si am luat 100p  . Se pare ca timpul de rulare se afla chiar la limita.

[•ariel_ro]

V-as ruga, daca puteti, sa postati un link cu explicatia rezolvarii folosind arbori indexati binar (am cautat si nu am gasit).
Va multumesc!

[•mrares]

Imi da careva un hint/ o idee cum se face cu arbori de intervale ? In comentarii n-am gasit... iar sursele... plagiate una dupa alta (toate cu cautare binara) )

arbori de intervale nu AIB !!!!

[•pauldb]

Sortezi numerele in ordine crescatoare, iar atunci cand adaugi un numar nou, vrei sa numeri cate numere au fost introduse deja in stanga pozitiei. Daca intelegi ce se intampla intr-o sursa cu AIB, exact aceeasi operatie se poate efectua si cu un arbore de intervale.

[•attila3453]

Imi pare rau, dar la indicatii nu trebuia scris ca best este lungimea unui subsir crescator care incepe cu pozitia i? Pentru ca pe exemplu best este [1 3 2 2 1], si cea cu 3 elemente incepe cu 12.

[•gabitzish1]

E ok la indicatii. Pe exemplu, vectorul best e [1, 1, 2, 2, 3].
Se construieste vectorul de la prima spre ultima pozitie, tu probabil stii o rezolvare care construieste best de la ultima spre prima pozitie.
Uita-te la recurenta, poate te ajuta sa intelegi de ce e corect : best = 1 + max(best[j]) 1 <= j < i, deci nu ai cum sa obtii best[2] = 3.

[•attila3453]

E ok la indicatii. Pe exemplu, vectorul best e [1, 1, 2, 2, 3].
Se construieste vectorul de la prima spre ultima pozitie, tu probabil stii o rezolvare care construieste best de la ultima spre prima pozitie.
Uita-te la recurenta, poate te ajuta sa intelegi de ce e corect : best = 1 + max(best[j]) 1 <= j < i, deci nu ai cum sa obtii best[2] = 3.

Da, ai drepate, e acelasi lucru dar eu faceam in sens opus. Mersi!

[•nicolaetitus12]

vreo idee de ce iau memory limit exceeded la solutia asta pentru cazul 2?

Later edit : problem solved, am pus prev[1]=1; in loc de prev[1]=0; 

Editat de moderator: Nu posta de mai multe ori consecutiv pe acelasi subiect, editeaza posturile anterioare.

[•VisuianMihai]

imi puteti explica si mie metoda cu cautare binara? nu prea inteleg ce face...

[•adavidoaiei]

Cum pot vedea testele care ruleaza in Monitorul de Evaluare ca sa pot sa le iau local si sa fac debug, ca sa vad ce am gresit.

[•SpiderMan]

Pe pagina problemei, http://infoarena.ro/problema/scmax, aici, ai pe chenarul verde, imediat sub tabelul cu datele "tehnice" sa le zic asa, "De asemenea, poti vedea si testele accesand atasamentele". Apesi click pe atasamentele, si acolo ai fiecare test, evaluatorul si etc .

[•adavidoaiei]

Am gasit un comment pe problema care raspunde la intrebarea mea: "In coltul din dreapta-sus pe pagina problemei ai un link "Listeaza atasamente"... acolo gasesti si testul si raspunsul."

[•SpiderMan]

Da, e exact ce-am scris si eu, ori dai listeaza atasamente, ori dai pe butonul ala, ai 2 optiuni .

[•adavidoaiei]

thanks i found

[•SebiSebi]

Cum s-ar putea face cu arbori de intervale ? Iese din timp pe ultimele 3 teste.

[•RaduDo]

Va rog ajutor ! Cum sa fac sa afisez toate solutiile, nu doar una ? (Ma chinui de ceva timp si degeaba)