008 Subsir crescator maximal

[•filipb]

Aici puteti discuta despre problema Subsir crescator maximal.

[•rEbyTer]

Fie un vector a cu N elemente. Numim subir al lui a de lungime K un vector a' = (ai1, ai2, ..., aiK) astfel incat sa avem i1 < i2 < ... < iK.

o mica greseala....

[•Nicholas]

*Primul meu post!*

De ce imi da "Time limit exceeded!" la cel de-al doilea test? Chiar nu imi dau seama. Poate sa se uite cineva pe sursa mea? 

[•toni2007]

pare bine... dar de ce citesti numerele cu %ld cand ele sunt inturi?

[•tm_radu]

pentru testul 2, max este initializat cu b[1], insa poz este 0. cum max nu-si mai schimba valoarea aici:

Cod:

for (i=1;i<=n;i++)  
        if (max<b[i]) {max=b[i]; poz=i;}  

poz ramane 0 si iti intra in ciclu infinit.

[•Nicholas]

Merci mult amandurora. Retrimit sursa. 



Yay! 70 pct

[•MciprianM]

Imi poate da cinneva un link spre explicarea solutiei din cartea lui Catalin Francu la aceasta pb?

[•wefgef]

In josul paginii: http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence

sau pe wikipedia: http://en.wikipedia.org/wiki/Longest_increasing_subsequence

Poate te ajuta si implementarea mea pe aceeasi idee: http://infoarena.ro/job_detail/190091?action=view-source

[•MciprianM]

ms

[•log2]

Ce alte probleme folosesc sbsir crescator maximal ?
Multumesc

[•MBlue]

iau 0 puncte. la evaluare arata "Non-zero exit status." insa pentru testele care le dau la mine pe pc el functioneaza
http://infoarena.ro/job_detail/270611
va rog, cineva sa se uite peste sursa mea...

va rog... imi spune cineva 

Nu posta consecutiv. Editeaza mesajele precedente

[•devilkind]

Exista un topic intitulat mesaje de eroare. Intrebarea ta a mai fost pusa de vreo cateva ori.

[•Cristian_B]

Imi spune si mie cineva ce am inteles gresit la problema asta de iau doar 20 de p?

[•Florian]

Spune-ne, mai intai, cum ai inteles-o tu. Asa poate mai ai o sansa sa fii ajutat. 

[•Cristian_B]

Ha ) pai eu am inteleso asa, in primu rand algoritmul e de O(n^2), deci iau maxim 70p. Ideea mea este asa: prima data iau in vector sirul de numere apoi parcurg vectorul si pentru fiecare v merg cu un j, care initial este i si pun intr-o stiva v[j] daca este mai mare decat toate celelalte elemente din stiva si cand am gasit o stiva de lungime maxima o retin, apoi afisez stiva. E bine?

[•Florian]

Nu. Citeste cu atentie indicatiile de rezolvare:

O prima rezolvare utilizeaza programarea dinamica. Se noteaza best[ i ] - lungimea maxima a unui subsir crescator care se termina pe pozitia i . Obtinem astfel urmatoarea relatie de recurenta: best [ i ] = 1 + max(best[j]) cu 1 ≤ j < i si a[ j ] < a[ i ] . Pentru a reconstrui solutia mai retinem un vector cu semnificatia pre[ i ] - pozitia valorii care preceda elementul i in subsirul crescator care se termina pe pozitia i.

In opinia mea, e destul de bine explicat...

[•mlazari]

M-am uitat la sursa oficiala cu AIB (http://infoarena.ro/job_detail/146356?action=view-source) si am vazut ca se folosesc functii, cum ar fi sort si lower_bound. Eu nu prea stiu functiile astea, asa ca am facut sortarea folosind un heap (http://infoarena.ro/job_detail/314061). Partea cu AIB-urile este cam aceeasi ca si in sursa oficiala. Complexitatea programului parca e tot O(N*log₂N). De ce iau TLE la testele 8 si 10? 

[•tvlad]

M-am uitat la sursa oficiala cu AIB (http://infoarena.ro/job_detail/146356?action=view-source) si am vazut ca se folosesc functii, cum ar fi sort si lower_bound. Eu nu prea stiu functiile astea, asa ca am facut sortarea folosind un heap (http://infoarena.ro/job_detail/314061). Partea cu AIB-urile este cam aceeasi ca si in sursa oficiala. Complexitatea programului parca e tot O(N*log₂N). De ce iau TLE la testele 8 si 10? 

Functiile de care vorbesti sunt din librariile STL, vezi mai multe in articolul asta http://infoarena.ro/stl si pe http://www.sgi.com/tech/stl/.
Heapsort de mana merge mai incet decat sort din STL, probabil de-aia iei TLE

[•mlazari]

Mersi, m-am uitat. Mi se par la inceput un pic cam dificile functiile astea, dar poate ca e doar o aparenta. Cat despre problema, am luat 100p. cu MergeSort  , si este si codul mai scurt 

[•andrei.finaru]

*first post by noob:(* eu zic ca am scris o sursa de 70 da imi da WA la 8 teste... si fiindca unul din testele la care am rezultatul corect e grupat cu altele 2 nu-mi da decat punctele de la celalalt:| daca ma puteti ajuta as aprecia.

[•Florian]

Tu rezolvi problema pentru subsecventa. Trebuie sa o faci pentru subsir ( care nu are elementele pe pozitii consecutive in sirul initial ). Citeste cu atentie enuntul! 

[•andrei.finaru]

Mersi mult:)

[•PavelRazvan]

Am si eu o nelamurire : iau 65 pct si am verificat testele pe care iau "Subsir incorect!" si programul meu afiseaza alte numere, dar totusi le-am verificat cu un alt program si subsirul e bun. De ce primesc atunci "Subsir incorect!" , atata timp cand

Daca exista mai multe solutii se poate afisa oricare.

http://infoarena.ro/job_detail/391192

Va rog sa ma lamuriti !
Multumesc anticipat !

[•ionutz32]

M-am uitat pe sursa ta si mi-am dat seama ca tu cauti binar pozitia din b pentru fiecare element, ceea ce nu iti garanteaza ca la sfarsit elementele se vor gasi in aceeasi ordine in sirul initial (adica in b nu ai un subsir). De exemplu, la testul 3 programul tau afiseaza:

38
6625742 13552532 18812311 (...)

iar in sirul din fisierul de intrare, numarul 18812311 e inaintea lui 13552532.

[•PavelRazvan]

Deci asta era !
Merci beaucoup!