infoarena

Aici puteţi discuta despre problema Secvente (http://infoarena.ro/problema/secvente).

Cam la ce complexitate se asteapta? Nu da nimeni un hint... nu cred ca merge cum m-am gandit eu ..

La acelasi lucru ma gandesc si eu...nu stiu dak se poate O(n)(pt fiecare sir in parte).. :eyebrow:

Judecand dupa limite, complexitatea trebuie sa fie una liniara (maxim liniar logaritmica). Incearca inainte de a primi hint-uri, nu e o problema foarte grea.

Cu O(n log n) iau TLE pe toate testele,..deci complexitatea e liniara... :)

esti sigur ca ai implementat klumea?? nush cum e solutia ta in n log n dar ar trebui sa prinda totusi niste testem adik ptr n<50000   n log n ar trebuie sa intre fara probleme. Oricum dupa ce incerci o complexitate eu zic sa verifici si solutia in n log n (in primu rand vezi dak e corecta si apoi vezi dak intr-adevar are acea complexitate)

Eu am facut a[ i ] = restul impartirii la 3 a sumei primelor i numere. Cu asta pot afla toate secventele a caror suma se divide la 3 in complexitate patratica si lua pe cea mai mare... bine-nteles ca asta nu intra in timp. Merge totusi pe ideea asta, sau trebuie ceva cu totul diferit?  :-k

Atentie! Trebuie sa afli lungimea cea mai mare a unui subsir, nu a unei secvente.

Nu m-am exprimat eu bine, subsir trebuia sa spun. Asta aflu, dar singura metoda pe care o stiu eu e cea descrisa in mesajul anterior... Se poate mai bina pe aceeasi idee, sau trebuie total altceva?

Cu metoda descrisa de tine afli secvente... nu subsiruri.

secventa = multime de elemente aflate pe pozitii consecutive in sirul initial
subsir = o multime de elemente aflate pe pozitii oarecare.

hm, da, le-am incurcat. Intr-adevar, eu consideram pozitiile consecutive...

nici asa insa nu vad cum as putea face in O(n) sau O(n log n)... s-ar putea eventual construi dinamic a[ i ] = lungimea celui mai lung subsir a carui suma se divide la 3, si ar rezulta ceva gen subsir crescator maximal. Dar si asta s-ar face in O(n^2), nu?

Problema admite o solutie elementara, care nu foloseste nicio tehnica de programare precum PD, greedy sau altceva. Evident merge si cu niste recurente.

Aveai dreptate, silviu, nu e deloc grea.. Greseam un indice si luam 30, acum am modificat si iau 100. Dar e dragutza prb, totusi.. :)

Apropos, am complexitate O(n) si cred ca e singura solutie posibila..

Mai putin de atata nu se poate  :P

Eu stiu 2 solutii.  :D

Later edit: Acum stiu 3. :)

Puteti sa-mi dati ceva teste la problema asta?? Iau 90 de puncte cu WA pe testul 7 si nu stiu ce poate sa fie gresit...  ](*,)

 :ok:
.in:

.ok:

Am avut si eu "probleme" cu testul 7 si primul test nu imi dadea dar l-am rezolvat  :banana: spor

Later Edit:am gasit o greseala prin teste... si totusi am luat 100 :-? inseamna ca testele de pe evaluator nu garanteaza sursele bune :-'
L.L. Edit:Mi-am reparat programul si da bine si pe cazul acela... :-?
Ok

http://infoarena.ro/forum/index.php?board=39.0

raporteaza aici exact cum ai luat 100, altfel nimeni nu o sa stie cum sa modifice testele.

Eu m-am chinuit mult la problema asta. Intr-adevar, testele nu sunt chiar bine construite si luam 90 cu o sursa gresita.

Uite un test pe care sa il dati in caz ca primiti WA...
.IN
1 3 1 3 7 2 1 1 1 1 1 1

.OUT:
1
1
6

Am si eu o nelamurire legata de teste.Stiu ca a trecut destul de mult de la ultimul post pe forumul acestei probleme,dar ma intrebam asa...Am luat 100 pct pe problema asta http://infoarena.ro/job_detail/256082 si totusi exista teste pe care imi da gresit.Pe unul din testele postate de Andrei Purice:
in:
10 54353 64 65764 99999 499999 4352 53453 76576 8564 32341 6 423143 34534 8665 4124 54235 111111 12 432432 3232 53454 65424 4234 423432 65 8452 76542 85432 43533 78543
ar trebui sa dea:
out:
9  5 12
iar mie imi da 9 4 12.Am facut pe hartie un calcul si intr-adevar programul meu calculeaza gresit.Problema apare la secventa de nr:
 6 423143 34534 8665 4124 54235 111111
(care sunt de forma 3k+2,3k+1,3k+1,3k+2,3k+1, 3k) .Conform programului meu aceste nr sunt grupate astfel: am 3 variabile care numara nr de nr de o anumita paritate in functie de 3. Ex:nr1 reprezinta cate nr din secventa dau restul 1 la imparitrea la 3. Pe acest caz:
   nr1=3, nr2=2, nr3=1. rezultatul il calculez in felul urmator: rez=nr3+nr1/3*3+nr2/3*3,dupa care nr1 si nr 2 devin: nr1=nr1%3, nr2=nr2%3 si adun la rez 2*min(nr1,nr2). deci pe acest exemplu rez=1+3+0=4.O alegere mai comvenabila(prin care se obtinea rezultatul 5) : {3k;  3k+1;  3k+2;  3k+1; 3k+2} . Sper ca asta sa ajute la imbunatatirea testelor

salut ....am si yo o intrebare...imi dati si mie testul 9 ? iau WA pe el nuj dc ....

Testele nu se fac publice la problemele din arhiva.

ok....chiar nu stiam ....  :ok:

Este ceva special la testul 5?  :-k

L. E. Nu mai e nevoie.

Mici greseli : iar pe urmatoarele N₃ linii al sirul 3. ( corect sirul ) ; pe linia a doua cerinta pentru al doilea sie ( sir ) .

cum s-ar face problema asta cu programare dinamica? :oops:

Not sure daca e vreun algoritm de dp care sa mearga, dar poti sa faci altfel. Pentru fiecare sir imparte numerele in 3 multimi in functie de rest.

Poti tine un vector dp[ i ] lungimea celui mai lung subsir a carui suma da restul i la impartirea cu 3. E destul de usor de calculat.

 :) am sa incerc. multumesc :D