•DITzoneC
|
|
« : Martie 01, 2008, 17:09:38 » |
|
Aici puteţi discuta despre problema Joctv.
|
|
|
Memorat
|
|
|
|
•anna_bozianu
|
|
« Răspunde #1 : Martie 02, 2008, 06:15:52 » |
|
Am trimis o sursa cu un algoritm de O(n^4) de 3 ori . Singura diferenta intre surse consta in introducerea unor comentarii. Rezultatele au fost : prima sursa ( fara comentarii ) => 80 puncte cu TLE pe testele 9 si 10 a doua sursa ( + 2 linii comentarii) => 90 puncte cu TLE pe testul 8 a treia sursa ( + 3 linii comentarii) => 70 puncte cu TLE pe testul 7, 8 si 10 Trebuie sa scriu un anume descantec in comentarii sau sa fac implementarea in O(n^3) pentru 100 p. Desigur am glumit ... dar totusi care e explicatia ? Se genereaza teste random sau sunt mereu aceleasi teste ? Later edit : A mers fara descantece cu implementarea de O(n^3)
|
|
« Ultima modificare: Martie 02, 2008, 07:04:49 de către Bozianu Ana »
|
Memorat
|
|
|
|
•devilkind
|
|
« Răspunde #2 : Martie 02, 2008, 11:14:49 » |
|
pai e destul de simplu. Sursa e la limita. E normal ca o sursa care pe un test se incadreaza in timp la limita, a doua oara sa nu mai treaca, depinde in mare de cat de solicitat este procesorul in momentul in care iti este evaluata sursa, lucru care nu este intotdeauna constant.
|
|
|
Memorat
|
|
|
|
•omu_salcam
Strain
Karma: 1
Deconectat
Mesaje: 1
|
|
« Răspunde #3 : Martie 02, 2008, 11:28:55 » |
|
Si eu am luat TLE pe testul 7. Am trimis de 3 ori una dupa alta solutii, si mi-a dat 100 de pct
|
|
|
Memorat
|
|
|
|
•devilkind
|
|
« Răspunde #4 : Martie 02, 2008, 11:30:01 » |
|
cu n^4??
|
|
|
Memorat
|
|
|
|
|
•wefgef
|
|
« Răspunde #6 : Martie 03, 2008, 18:41:58 » |
|
Iti fixezi linia cea mai de sus si cea mai de jos a zonei dreptunghiulare alese si problema se reduce la determinarea subsecventei de suma maxima in O(N).
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
|
•savim
|
|
« Răspunde #8 : Martie 03, 2008, 19:49:13 » |
|
Incearca sa nu te complici, adica sa faci sursa cat mai simpla, si daca esti atent ar trebui sa iei o suta cu un timp de executie relativ mic...la mine max a fost 12ms, si sursa a avut 0.54kb.
|
|
|
Memorat
|
|
|
|
•anna_bozianu
|
|
« Răspunde #9 : Martie 03, 2008, 21:30:31 » |
|
@Robytzza
Daca faci inainte de a incepe treaba
linia[ i ] = linia[ 1 ]+linia[ 2 ]+...linia[ i ]
folosind ideea simpla
linia [ i ]=linia [ i ]+linia[ i -1] pentru i=1..n ,
gandeste-te ce obtii in vectorul
v=linia[ j ]-linia[ k-1 ] pentru 1<=j<=k<=n
si apoi ce inseamna
v [ x ] + v [ x+1 ] + ...+ v[ y ] pt x<=y 1<=x<=y<=n.
Cam pe aici se invarte ideea pt O(n^3).
|
|
|
Memorat
|
|
|
|
•Robytzza
|
|
« Răspunde #10 : Martie 04, 2008, 16:07:25 » |
|
ms ana:D
|
|
|
Memorat
|
|
|
|
•MciprianM
|
|
« Răspunde #11 : Mai 10, 2008, 09:43:10 » |
|
v=linia[ j ]-linia[ k-1 ] pentru 1<=j<=k<=n
si apoi ce inseamna
v [ x ] + v [ x+1 ] + ...+ v[ y ] pt x<=y 1<=x<=y<=n.
Nu inteleg de ce j<=k. Nu da v<0? Si linia[1] inseamna suma elementelor de pe linia 1? Cam pe aici se invarte ideea pt O(n^3).
|
|
|
Memorat
|
|
|
|
•Mishu91
|
|
« Răspunde #12 : Mai 10, 2008, 18:47:08 » |
|
Pai iti faci sume partiale pentru fiecare coloana din matrice for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) S[i][j] = S[i-1][j] + A[i][j]; cva de genu arata codu. Si iti fixezi doua linii intre care vrei sa calculezi, iar de aici, avand precalculate sumele astea, iti ramane de aflat subsecventa de suma maxima dintr-un sir
|
|
« Ultima modificare: Mai 10, 2008, 19:00:12 de către Andrei Misarca »
|
Memorat
|
|
|
|
|
•MciprianM
|
|
« Răspunde #14 : Mai 19, 2008, 12:13:45 » |
|
L.E. Am gasit greseala.
|
|
« Ultima modificare: Mai 20, 2008, 12:55:33 de către marginean ciprian »
|
Memorat
|
|
|
|
•Bogdan_tmm
|
|
« Răspunde #15 : Ianuarie 25, 2009, 01:13:42 » |
|
for(i=1;i<=n;i++) for(j=1;j<=n;j++) { fscanf(f,"%ld",&a); s[i][j]=s[i-1][j]+a; } for(i=1;i<=n;i++) for(j=i;j<=n;j++) { s1=sm=0; for(i1=1;i1<=n;i1++) { aux=s[j][i1]-s[i-1][i1]; (de aici in jos sigur e bine) .................. } }
iau 50 p in o(4*n) si in o(3*n)-sursa asta si culmea cad aceleasi teste :|Oare dc? ( la: kiar unde zisei ca e bine nu era corect =)))))))))
|
|
« Ultima modificare: Ianuarie 25, 2009, 01:46:03 de către Tarca Bogdan »
|
Memorat
|
|
|
|
•MihaiG
Strain
Karma: -3
Deconectat
Mesaje: 1
|
|
« Răspunde #16 : Noiembrie 03, 2009, 18:50:42 » |
|
salut, cred ca ar trebuii modificat enuntu sau scrieti la restrictii pentru ca se cere un dreptunghi, iar eu am luat considerat prima data a extremitatea de jos a dreptunghiului ia val de la i+1 la n(ca sa nu mai spun numaram si coloanele pentru ca numarul acestora sa fie >=2 pentru ca solutia sa fie valida) si am luat 80. dupa ce am modificat i+1 cu i am scos tot ce era cu variabila ce memora numarul coloanelor am luat 100... inseamna ca pe 2 teste nu sunt dreptunghiuri ci sunt linii. la oli au "gresit" cativa asa? va pup
|
|
« Ultima modificare: Noiembrie 03, 2009, 20:19:31 de către Gheorghevici Mihai Florin »
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #17 : Noiembrie 03, 2009, 20:45:31 » |
|
De unde ai tras tu concluzia ca "o zona dreptunghiulara" trebuie sa fie o submatrice cu cel putin 2 coloane/linii?
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•mihai995
Strain
Karma: 1
Deconectat
Mesaje: 8
|
|
« Răspunde #18 : Aprilie 14, 2011, 22:54:57 » |
|
ar trebui marite putin limitele pentru N sau scrimbate testele... nu sunt suficient de bune si data o reevaluare... am luat 100p cu N^4
|
|
|
Memorat
|
|
|
|
•S7012MY
|
|
« Răspunde #19 : Decembrie 15, 2011, 22:59:48 » |
|
Testele la problema asta nu sunt foarte bune. Se poate lua 100 cu o sursa care nu testeaza daca dreptunghiul de suma maxima e un element de pe prima coloana.
|
|
|
Memorat
|
|
|
|
•informatician28
Strain
Karma: 6
Deconectat
Mesaje: 27
|
|
« Răspunde #20 : Ianuarie 16, 2012, 21:13:36 » |
|
Iau incorect la testul 5 . Ce ar putea fi? Verific inclusiv daca am solutie doar pe prima linie...
|
|
|
Memorat
|
|
|
|
|
•hasmasandragos
Strain
Karma: 0
Deconectat
Mesaje: 10
|
|
« Răspunde #22 : Mai 24, 2015, 21:38:35 » |
|
Concurentul poate sa aleaga o zona nula (adica sa nu aleaga nimic) daca nu exista vreo zona care sa ii aduca profit.
|
|
|
Memorat
|
|
|
|
|