infoarena

Aici puteti discuta despre problema Subsir crescator maximal (http://infoarena.ro/problema/scmax).

o mica greseala....

*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?  :wink:

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

pentru testul 2, max este initializat cu b[1], insa poz este 0. cum max nu-si mai schimba valoarea aici:
poz ramane 0 si iti intra in ciclu infinit. :)

Merci mult amandurora. Retrimit sursa.  :aha:



Yay! 70 pct

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

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

ms

Ce alte probleme folosesc sbsir crescator maximal ?
Multumesc

iau 0 puncte. la evaluare arata "Non-zero exit status." insa pentru testele care le dau la mine pe pc el functioneaza :sad:
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

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

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

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

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?

Nu. Citeste cu atentie indicatiile de rezolvare:

In opinia mea, e destul de bine explicat... :-k

M-am uitat la sursa oficiala cu AIB (http://infoarena.ro/job_detail/146356?action=view-source (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 (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 (http://infoarena.ro/stl) si pe http://www.sgi.com/tech/stl/ (http://www.sgi.com/tech/stl/).
Heapsort de mana merge mai incet decat sort din STL, probabil de-aia iei TLE ;)

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  :yahoo: , si este si codul mai scurt  :roll:

*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.

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!  :)

Mersi mult:)

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 http://infoarena.ro/job_detail/391192 :readthis:

Va rog sa ma lamuriti !
Multumesc anticipat !

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:
iar in sirul din fisierul de intrare, numarul 18812311 e inaintea lui 13552532.

Deci asta era ! :shock:
Merci beaucoup!

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

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

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

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

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

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

si care e diferenta ca nu ma prind :?

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

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

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  :-k .
L.E. Am mai trimis-o o data si am luat 100p  :yahoo: . Se pare ca timpul de rulare se afla chiar la limita.

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

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 !!!!

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.

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.

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!

vreo idee de ce iau memory limit exceeded la solutia asta (http://infoarena.ro/job_detail/575217) 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.

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

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.

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 :D.

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."

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

thanks :) i found

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

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

Numarul de solutii creste exponential.

Daca vrei sa le afisezi pe toate atunci cand actualizezi valoarea dp[ i ] ,tii o lista cu toate valorile din care poti obtine valoarea maxima pentru dp[ i ] . Iti dau un exemplu , pentru a fi mai clar :
sa zicem ca ai sirul 2 10 15 3 11 16. In acest sir elementele au urmatorii precedenti :
2 -> nu e precedat de nimeni
10-> e precedat de 2
15 -> e precedat de 10
3-> 3 precedat de 2
11 -> e precedat atat de 3 cat si 10 ambele valori ducand la un subsir de lungime 3
16-> e precedat de 11,3,15 toate 3 ducand la un subsir de lungime 4
Acum pentru a genera toate subsirurile maximale algoritmul este urmatorul :
Iei fiecare precedent al unui element pentru care dp[ i ] = 4, pentru fiecare precedent iei fiecare precedent al acestuia si tot asa ... pana ajungi la un element ce nu e precedat de nimic .
Poate nu am fost suficient de clar , nu sunt tocmai un as al explicatiilor , dar daca mai ai nelamuriri dam un pm si vad cum te pot ajuta , eventual iti dau o sursa sa vezi cum se face .

Cred ca trebuie marita putin limita de timp. Am implementat o solutie cu normalizare( cu lower_bound) + AIB + parsare si iau tle pe testul 9.

Am incercat sa implementez cu AIB si iau TLE pe testul 9. Nici sursa data ca model nu e de 100, tot din cauza testului 9, desi in josul paginii scrie ca obtine 100  :P .
Modelul : http://infoarena.ro/job_detail/809153
A mea : http://infoarena.ro/job_detail/809148

am facut un algoritm cu programare dinamica, complexitatea fiind O(N²). merge dar pe ultimele 3 teste imi da TLE. aveti vreo idee despre cum as putea modifica algoritmul in asa fel incat sa fie mai rapid? :-k

Trebuie sa scoti complexitate mai buna. Citeste indicatiile de rezolvare.

In sfarsit am luat 100 :winner1: multumesc :D

Solutia cu AIB-uri nu intra in timp (nici macar solutia oficiala) . Nu stiu daca s-a mai zis , dar m-am gandit ca e ok sa stiti.

ce inseamna erorile: killed by signal 6 si lungime incorecta. Daca s-ar putea uita cineva pe sursele mele as fi recunoscator:D

imi poate spune cineva de ce imi apare subsir incorect? :D

      Sunt nou pe infoarena si as vrea sa inteleg de ce sursa me primeste doar 10 puncte , am facut mai mult teste pe ea si toate mergeau (ex:  5 54321 : 1 1 ; 5  2412151519 : 3 12 15 19  ..etc).

Plz ajutati-ma ! :D

aici e linkul : http://www.infoarena.ro/job_detail/1971925?action=view-source

Mersi