213 Jocul

[•Steve]

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

[•danalex97]

Tu ai O(n * sum/2) , cand optim e O( Const * sum/2 ) , unde Const=100 (  1 ≤ lungimei ≤ 100 ).  Succes.

[•SebiSebi]

Poti face dinamica folosind doar ultima linie. Eu asa am scapat de TLE.

[•lucian666]

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

[•visanr]

E problema clasica de programare dinamica, cauta dupa "Impartirea cadourilor" si ar trebui sa gasesti.

[•lucian666]

  Mersi Radu .Am luat 100

[•Andrei1998]

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)?

[•harababurel]

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.

[•Andrei1998]

Multumesc pentru raspuns. Am reusit 100 cu O(n*suma/2). Vreun  hint despre cum se face in 100*suma/2? Vector de frecventa?

[•addy01]

refaceti testele!!! am luat 100 fara sa-mi iasa exemplul

[•DorelBarbu]

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!

[•AlexandruValeanu]

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:

Cod:

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

[•DorelBarbu]

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 ?

[•AlexandruValeanu]

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.

[•DorelBarbu]

Cred ca diferenta dintre timpi este data de apelul functiei max in interiorul for-urilor.

[•breahnadavid]

Cred ca ar trebui de mai schimbat niste teste.. !!!
Am trimis o sursa care buseste pe testul

Cod:

4
1
2
4
14

Imi da

Cod:

10 11

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

[•FlorinHaja]

Nu înţeleg de ce această sursă obţine 40 de puncte (http://www.infoarena.ro/job_detail/1451529), care, teoretic, ar trebui să fie mai bine optimizată decât aceasta (http://www.infoarena.ro/job_detail/1451530).

L.E.: Am parcurs for-ul doar de la 0 până la jumătatea sumei totale şi mi-a dat 100.

[•tiby10]

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 ?

[•PlayLikeNeverB4]

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.

[•tiby10]

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

[•klamathix]

Încearcă:

3
1 2 5

Limita de timp am să o schimb să fie mai decentă.

[•tiby10]

Mihai, e ok, imi da bine:

Cod:

3 5

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

[•klamathix]

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.

[•tiby10]

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.

[•xSlive]

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];
}