402 Secvente

[•silviug]

Aici puteţi discuta despre problema Secvente.

[•peanutz]

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

[•Florian]

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

[•silviug]

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

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.

[•Florian]

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

[•devilkind]

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)

[•Dastas]

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? 

[•wefgef]

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

[•Dastas]

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?

[•wefgef]

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.

[•Dastas]

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?

[•silviug]

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

[•peanutz]

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

[•cos_min]

Mai putin de atata nu se poate 

[•pauldb]

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

Eu stiu 2 solutii. 

Later edit: Acum stiu 3.

[•CezarMocan]

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

[•Protoman]

 
.in:

Cod:

6 1 2 3 4 5 6 5 6 13 18 4 2 5 2 1 2 2 2 
7 4 8 1 9 5 7 2 3 12 15 18 4 988 3131 99111 80000
10 5 10 15 20 25 30 35 40 45 50 6 100 200 300 3 6 9 8 243 765 234 7564 51542 68548 96578 34545
7 324 65375 73767 21423 445356 74574 5345 8 54326 5632 334254 3453 68566 54353 76543 53453 3 64576 7564 5325
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
1 3 1 6 1 4

.ok:

Cod:

6 4 5
7 3 3
9 6 8
5 8 1
9 5 12
1 1 0

Am avut si eu "probleme" cu testul 7 si primul test nu imi dadea dar l-am rezolvat  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

[•devilkind]

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.

[•MarcvsHdr]

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

[•cosmin79]

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

[•drag0s93]

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

[•devilkind]

Testele nu se fac publice la problemele din arhiva.

[•drag0s93]

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

[•APOCALYPTO]

Este ceva special la testul 5?  

L. E. Nu mai e nevoie.

[•SpiderMan]

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