infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Silviu-Ionut Ganceanu din Aprilie 19, 2007, 16:05:35



Titlul: 402 Secvente
Scris de: Silviu-Ionut Ganceanu din Aprilie 19, 2007, 16:05:35
Aici puteţi discuta despre problema Secvente (http://infoarena.ro/problema/secvente).


Titlul: Răspuns: 402 Secvente
Scris de: Andrei Homorodean din Aprilie 19, 2007, 17:07:57
Cam la ce complexitate se asteapta? Nu da nimeni un hint... nu cred ca merge cum m-am gandit eu ..


Titlul: Răspuns: 402 Secvente
Scris de: Florian Marcu din Aprilie 19, 2007, 17:18:05
La acelasi lucru ma gandesc si eu...nu stiu dak se poate O(n)(pt fiecare sir in parte).. :eyebrow:


Titlul: Răspuns: 402 Secvente
Scris de: Silviu-Ionut Ganceanu din Aprilie 19, 2007, 17:19:48
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.


Titlul: Răspuns: 402 Secvente
Scris de: Florian Marcu din Aprilie 19, 2007, 17:52:07
Cu O(n log n) iau TLE pe toate testele,..deci complexitatea e liniara... :)


Titlul: Răspuns: 402 Secvente
Scris de: Savin Tiberiu din Aprilie 19, 2007, 20:22:41
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)


Titlul: Răspuns: 402 Secvente
Scris de: Ionescu Vlad din Aprilie 20, 2007, 12:31:48
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


Titlul: Răspuns: 402 Secvente
Scris de: Andrei Grigorean din Aprilie 20, 2007, 12:40:35
Atentie! Trebuie sa afli lungimea cea mai mare a unui subsir, nu a unei secvente.


Titlul: Răspuns: 402 Secvente
Scris de: Ionescu Vlad din Aprilie 20, 2007, 12:55:55
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?


Titlul: Răspuns: 402 Secvente
Scris de: Andrei Grigorean din Aprilie 20, 2007, 12:58:17
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.


Titlul: Răspuns: 402 Secvente
Scris de: Ionescu Vlad din Aprilie 20, 2007, 13:14:59
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?


Titlul: Răspuns: 402 Secvente
Scris de: Silviu-Ionut Ganceanu din Aprilie 20, 2007, 13:38:19
Problema admite o solutie elementara, care nu foloseste nicio tehnica de programare precum PD, greedy sau altceva. Evident merge si cu niste recurente.


Titlul: Răspuns: 402 Secvente
Scris de: Andrei Homorodean din Aprilie 20, 2007, 13:50:41
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..


Titlul: Răspuns: 402 Secvente
Scris de: Bondane Cosmin din Aprilie 20, 2007, 14:00:33
Mai putin de atata nu se poate  :P


Titlul: Răspuns: 402 Secvente
Scris de: Paul-Dan Baltescu din Aprilie 20, 2007, 16:26:01
Apropos, am complexitate O(n) si cred ca e singura solutie posibila..

Eu stiu 2 solutii.  :D

Later edit: Acum stiu 3. :)


Titlul: Răspuns: 402 Secvente
Scris de: Cezar Mocan din Aprilie 21, 2007, 10:13:02
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...  ](*,)


Titlul: Răspuns: 402 Secvente
Scris de: Andrei Purice din Aprilie 21, 2007, 10:44:43
 :ok:
.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  :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


Titlul: Răspuns: 402 Secvente
Scris de: Savin Tiberiu din Aprilie 21, 2007, 12:45:22
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.


Titlul: Răspuns: 402 Secvente
Scris de: Mihai Leonte din August 17, 2007, 23:53:49
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


Titlul: Răspuns: 402 Secvente
Scris de: Carabet Cosmin Andrei din Februarie 11, 2009, 01:19:00
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


Titlul: Răspuns: 402 Secvente
Scris de: Mandu Dragos din Februarie 16, 2009, 22:23:34
salut ....am si yo o intrebare...imi dati si mie testul 9 ? iau WA pe el nuj dc ....


Titlul: Răspuns: 402 Secvente
Scris de: Savin Tiberiu din Februarie 16, 2009, 22:24:31
Testele nu se fac publice la problemele din arhiva.


Titlul: Răspuns: 402 Secvente
Scris de: Mandu Dragos din Februarie 17, 2009, 00:00:22
ok....chiar nu stiam ....  :ok:


Titlul: Răspuns: 402 Secvente
Scris de: Dragos din Iunie 17, 2010, 19:47:58
Este ceva special la testul 5?  :-k

L. E. Nu mai e nevoie.


Titlul: Răspuns: 402 Secvente
Scris de: Simoiu Robert din Noiembrie 28, 2010, 15:13:22
Mici greseli : iar pe urmatoarele N3 linii al sirul 3. ( corect sirul ) ; pe linia a doua cerinta pentru al doilea sie ( sir ) .


Titlul: Răspuns: 402 Secvente
Scris de: Bratie Fanut din Februarie 15, 2013, 18:58:47
cum s-ar face problema asta cu programare dinamica? :oops:


Titlul: Răspuns: 402 Secvente
Scris de: Stefan Eniceicu din Februarie 15, 2013, 20:37:00
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.


Titlul: Răspuns: 402 Secvente
Scris de: stardust din Februarie 15, 2013, 21:00:49
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.


Titlul: Răspuns: 402 Secvente
Scris de: Bratie Fanut din Februarie 16, 2013, 09:40:42
 :) am sa incerc. multumesc :D