•Steve
Client obisnuit
Karma: 36
Deconectat
Mesaje: 72
|
|
« Răspunde #25 : Iulie 26, 2012, 07:57:45 » |
|
Matricea aia de dinamica e problema...Suma maxima a unui set de bete e ~100 * n / 2 deci ai putea lua matricea de [2][50000] (ai nevoie numai de ultimele 2 randuri).
|
|
|
Memorat
|
|
|
|
•danalex97
|
|
« Răspunde #26 : Iulie 26, 2012, 08:50:56 » |
|
Tu ai O(n * sum/2) , cand optim e O( Const * sum/2 ) , unde Const=100 ( 1 ≤ lungimei ≤ 100 ). Succes.
|
|
|
Memorat
|
|
|
|
•SebiSebi
|
|
« Răspunde #27 : Iulie 26, 2012, 09:08:50 » |
|
Poti face dinamica folosind doar ultima linie. Eu asa am scapat de TLE.
|
|
|
Memorat
|
|
|
|
•lucian666
Client obisnuit
Karma: 16
Deconectat
Mesaje: 84
|
|
« Răspunde #28 : Septembrie 06, 2012, 17:31:41 » |
|
Buna ziua! Am facut un greedy dar iau doar 7 teste ,restul WA. Cum este dinamica pt problema asta? chiar nu-mi dau seama Multumesc!!!
|
|
|
Memorat
|
|
|
|
•visanr
|
|
« Răspunde #29 : Septembrie 06, 2012, 19:01:07 » |
|
E problema clasica de programare dinamica, cauta dupa "Impartirea cadourilor" si ar trebui sa gasesti.
|
|
|
Memorat
|
|
|
|
|
•Andrei1998
|
|
« Răspunde #31 : Ianuarie 06, 2013, 15:39:12 » |
|
Eu din aceste comentarii sunt in ceata, complexitatea optima e O(n*suma/2) sau O(100*suma/2) (fiindca 100 e lungimea maxima a unui chibrit)?
|
|
|
Memorat
|
|
|
|
•harababurel
Client obisnuit
Karma: 23
Deconectat
Mesaje: 62
|
|
« Răspunde #32 : Ianuarie 06, 2013, 23:55:26 » |
|
O(N * Suma_lungimi) este si complexitatea oficiala.
@Andrei1998: Cu O(N * Suma_lungimi) s-ar putea sa ai nevoie de putina optimizare, la fel cum am avut eu, dar se poate rezolva problema si in O(100*suma/2), complexitate care intra mult mai lejer in timp.
|
|
|
Memorat
|
|
|
|
•Andrei1998
|
|
« Răspunde #33 : Ianuarie 07, 2013, 16:28:02 » |
|
Multumesc pentru raspuns. Am reusit 100 cu O(n*suma/2). Vreun hint despre cum se face in 100*suma/2? Vector de frecventa?
|
|
|
Memorat
|
|
|
|
•addy01
Strain
Karma: -8
Deconectat
Mesaje: 5
|
|
« Răspunde #34 : Iulie 02, 2013, 15:18:02 » |
|
|
|
|
Memorat
|
|
|
|
•DorelBarbu
Strain
Karma: 0
Deconectat
Mesaje: 34
|
|
« Răspunde #35 : August 29, 2013, 12:27:21 » |
|
Salut! Am facut si eu o dinamica O(n*(suma tuturor elementelor)/2) . Am optimizat, utilizand doar o linie de matrice. Cu toate acestea pic testul 7 si 10. Ce as mai putea face? Nu am nicio idee, am stat sa ma gandesc 3 ore. Cred ca am optimizat cat se putea sursa. Ajutati-ma si pe mine, va rog!
|
|
|
Memorat
|
|
|
|
•AlexandruValeanu
|
|
« Răspunde #36 : August 29, 2013, 12:48:19 » |
|
La dinamica ta nu stiu ce mai poti optimiza dar poti lua 100 cu o alta abordare de dinamica. Tii un vector format[ i ] = 1 daca poti forma suma i si 0 altfel. Si faci ceva de genul: format[0] = true;
for ( int i = 1; i <= n; ++i ) { for ( int j = suma_elemente/2; j >= 0; j-- ) if ( format[j] ) { format[j + v[i]] = 1; } }
Daca tot nu iti iese scrie-mi in privat si mai iti explic...
|
|
|
Memorat
|
|
|
|
•DorelBarbu
Strain
Karma: 0
Deconectat
Mesaje: 34
|
|
« Răspunde #37 : August 29, 2013, 12:56:53 » |
|
Merci mult! Am inteles cum se face. La asta nu m-am ganidt. Totusi, varianta mea, adica adaptarea problemei de Knapsack, nu ar trebui sa poata lua 100 ?
|
|
|
Memorat
|
|
|
|
•AlexandruValeanu
|
|
« Răspunde #38 : August 29, 2013, 13:07:23 » |
|
In teorie ambele variante au aceeasi complexitate O(N*suma/2) dar in practica se pare ca varianta cu vectorul de sume este mai rapida. http://www.infoarena.ro/job_detail/991009 - aceasta este rezolvarea din arhiva educationala adaptata la problema asta si ia 40p asa ca se pare ca nu sunt la fel ce rapide.
|
|
|
Memorat
|
|
|
|
•DorelBarbu
Strain
Karma: 0
Deconectat
Mesaje: 34
|
|
« Răspunde #39 : August 29, 2013, 14:21:43 » |
|
Cred ca diferenta dintre timpi este data de apelul functiei max in interiorul for-urilor.
|
|
|
Memorat
|
|
|
|
•breahnadavid
Strain
Karma: -1
Deconectat
Mesaje: 15
|
|
« Răspunde #40 : Iulie 17, 2014, 11:40:20 » |
|
Cred ca ar trebui de mai schimbat niste teste.. !!! Am trimis o sursa care buseste pe testul Imi da Iar sursa ea 100.. Eu am si sursa corecta doar am modificat-o si vad ca buseste testul dar ia 100.. Presupun ca asta-i rau ..
|
|
|
Memorat
|
|
|
|
|
•tiby10
Strain
Karma: 0
Deconectat
Mesaje: 6
|
|
« Răspunde #42 : Iulie 08, 2015, 08:33:00 » |
|
Am incercat eu cate ceva dar fac ce fac si tot primesc 40p ! Se poate uita cineva pe codul meu (considerati ultima sursa trimisa, deci http://www.infoarena.ro/job_detail/1458560) va rog ?
|
|
|
Memorat
|
|
|
|
•PlayLikeNeverB4
|
|
« Răspunde #43 : Iulie 08, 2015, 11:18:34 » |
|
Ce inseamna pentru tine "MAXN*MAXN"? Cred ca altceva voiai sa scrii. Ai declarat vectorul de 1000 si tu accesezi indicele 1000, deci depasesti limitele vectorului. La check nu ai nevoie de abs, din moment ce stii clar care numar e mai mare. Nu te complica si calculeaza raspunsul doar dupa ce ai facut dinamica. Problema nu specifica ordinea in care sa afisezi lungimile, deci si aici te-ai complicat degeaba. Pentru o imbunatatire a timpului poti sa incerci sa mergi cu j-ul invers si sa iesi din ciclu mai repede.
Spor.
|
|
|
Memorat
|
|
|
|
•tiby10
Strain
Karma: 0
Deconectat
Mesaje: 6
|
|
« Răspunde #44 : Iulie 08, 2015, 13:17:55 » |
|
In legatura cu dimensiunile vectorului nu cred ca constituie o problema foarte mare dar e adevarat ce spui. Ok, voi calcula dupa ce voi calcula dinamica dar asa ar fi fost ceva mai rapid, in orice caz, voi incerca. Ba da, daca te uiti la -Restricii si precizari-, acolo spune: Daca cele doua numere difera, ele se vor scrie in fisier in ordine crescatoare. Voi incerca si voi reveni cu un edit, multumesc! EDIT: still 40p ! http://www.infoarena.ro/job_detail/1458789?action=view-source
|
|
|
Memorat
|
|
|
|
•klamathix
|
|
« Răspunde #45 : Iulie 08, 2015, 13:43:16 » |
|
Încearcă:
3 1 2 5
Limita de timp am să o schimb să fie mai decentă.
|
|
|
Memorat
|
|
|
|
•tiby10
Strain
Karma: 0
Deconectat
Mesaje: 6
|
|
« Răspunde #46 : Iulie 08, 2015, 21:47:26 » |
|
Mihai, e ok, imi da bine: Am editat ceva si nu mai am probleme cu timpul de executie, dar tot iau 40p din cauza a 3 output-uri incorecte : http://www.infoarena.ro/job_detail/1459008
|
|
|
Memorat
|
|
|
|
•klamathix
|
|
« Răspunde #47 : Iulie 08, 2015, 23:40:18 » |
|
Da, scuze, probabil mă uitasem pe o sursă mai veche. Pe asta poți încerca:
4 1 3 5 5
TLE-ul s-a rezolvat fiindcă am mărit limita de la 0.05 la 0.2.
|
|
|
Memorat
|
|
|
|
•tiby10
Strain
Karma: 0
Deconectat
Mesaje: 6
|
|
« Răspunde #48 : Iulie 14, 2015, 09:35:13 » |
|
Aveam numai incorrect.uri fara TLE la vreo 2 surse trimise inainte sa postez aici dar tot editand in speranta gasirii bug.ului am dat de TLE Oricum, am rezolvat bug.ul de la prima implementare, multumesc.
|
|
|
Memorat
|
|
|
|
•xSlive
Strain
Karma: 0
Deconectat
Mesaje: 2
|
|
« Răspunde #49 : August 21, 2016, 13:26:47 » |
|
Ma ajuta cineva sa inteleg de ce iau TLE pe ultimul test? Nu inteleg cum anume se mai poate optimiza codul.
long long profit(long i,long W){ for(int i=1;i<=n;i++){ for(int w=1;w<=W;w++){ if(w >= wt[i-1]) a[w] = max(a[w] , a[w-wt[i-1]]+wt[i-1]); } } return a[W]; }
|
|
|
Memorat
|
|
|
|
|