026 Energii

[•pirosl]

Nu gresesti, dar nu ti se pare suficient de mare 10 000 * 1000, cum calculezi valorile ca sa iti intre in timp ?

Am scris mai sus cum calculez. Mi se pare ciudat ca 19 teste trec cu timpi sub 5 ms si unul pica dupa 100 si ceva de ms. In plus conditia din enuntul problemei (1< eg,gg < 10001) e falsa, pentru ca se pare ca sunt teste pt care gg e 0 (!?!?).
Sa inteleg ca exista un singur test cu valori mari?

[•wefgef]

Pentru urmatorul test, ce face programul tau?

Cod:

2
10
7 10000
8 10000

M-am uitat in codul tau si eroarea vine de la faptul ca declari maxsize prea mic. Ar trebui sa fie 10.000.000, nu 1000. Dupa cum a spus si Adi mai sus, incerca sa regandesti problema, pentru ca solutia ta nu merge pentru costuri mari. Faptul ca ai luat 95 de pct nu inseamna ca ai un mic bug in implementare, ci ca testele sunt proaste. Cu maxsize = 10.000.000 (atat cat ar trebui sa fie), primesti Killed by signal 11, pentru ca declari prea multa memorie. Daca il pun 1.000.000, desi iti intra in memorie, primesti TLE. Pentru a verifica daca o solutie e buna, incearca sa iti dai teste maxime. Un exemplu pentru problema aceasta ar fi:

Cod:

1000
1000
1 10000
1 10000
.............
1 10000

G = 1000, W = 1000, si fiecare generator are EG = 1, si EC = 10000. Raspunsul corect este 10.000.000

[•pirosl]

Pentru urmatorul test, ce face programul tau?

Cod:

2
10
7 10000
8 10000

M-am uitat in codul tau si eroarea vine de la faptul ca declari maxsize prea mic. Ar trebui sa fie 10.000.000, nu 1000. Dupa cum a spus si Adi mai sus, incerca sa regandesti problema, pentru ca solutia ta nu merge pentru costuri mari. Faptul ca ai luat 95 de pct nu inseamna ca ai un mic bug in implementare, ci ca testele sunt proaste. Cu maxsize = 10.000.000 (atat cat ar trebui sa fie), primesti Killed by signal 11, pentru ca declari prea multa memorie. Daca il pun 1.000.000, desi iti intra in memorie, primesti TLE. Pentru a verifica daca o solutie e buna, incearca sa iti dai teste maxime. Un exemplu pentru problema aceasta ar fi:

Cod:

1000
1000
1 10000
1 10000
.............
1 10000

G = 1000, W = 1000, si fiecare generator are EG = 1, si EC = 10000. Raspunsul corect este 10.000.000

Great...multam de tip....am incercat sa ma joc cu acel maxsize pt a intelege ce e cu acel test care pica (si probabil ca ultima sursa e cu maxsize prea mic).

[•nash]

 E o chestie care nu o intaleg ...
      Problema cere "o solutie de cost minim, pentru a produce o cantitate de energie egala sau mai mare cu cea necesara repornirii centralei"  , adica daca eu tebuie sa fac rost de G - energie cu cost min ... si observ ca nu se poate forma cantitatea acesta de energie atunci incep sa caut in G+1 , G+1 ... etc .. energie care se poate forma de cost min .

 Eu fac ceva in genul urmator ...

Cod:

for(i=1;i<=N;i++)
         for(j=1;j<=2*G;j++) {
             Energie[i%2][j] = max( verifica((i-1)%2,j-reactor[i]) , Energie[(i-1)%2][j] );
             cost_min[i%2][j]=MAXINT;
             if(Energie[i%2][j]) {
                if(verifica((i-1)%2,j-reactor[i])) cost_min[i%2][j]=min(cost_min[(i-1)%2][j-reactor[i]]+cost[i] , cost_min[i%2][j]);
                cost_min[i%2][j]= min(cost_min[i%2][j],cost_min[(i-1)%2][j]);
             }
         }

E logic ca trebuie sa iasa din timp ( fac pana la 2*G ) dar nu e logic de ce pe cele care intra .. da raspuns gresit ..

[•nash]

Nu are nimeni nici o idee ?

[•megabyte]

pai nu inteleg dece mergi pana la 2*G, G ii numarul de generatoare, poate fi un singur generator care produce 10 000 "1 < EGi,CGi < 10001 "
problema ii un knapsack, prima data trebuie sa o rezolvi cu o matrice c[nr_gen][en]-costul minim cu care poti obtine energia en cu nr_gen generatoare, si mergi cu en pana la WMAX .Dupa ce ai rezolvat-o cu matrice incerci sa reduci memoria la 2 linii , sau mai mult poti folosi un singur vector
LE: sau stai, ca la tine N ii nr de generatoare, atunci cand incerci sa introduci un generator nou verifici starea c[nr_gen-1][en-generator[nr_gen]] si nu (i-1)*2 si 2*i , s-a discutat mult la problema asta si poti gasi detalii in paginile anterioare...

[•nash]

daca ai citi bine rezolvarea mea .. ti-ai da seama ca am folosit problema rucsacului .. etc ... chestia cu liniic ...ca e nevioe decat de doua .. daca te-ai utia .. chiar cu 2 linii lucrez ... .. lucrez  " % 2"  ...

[•gabitzish1]

Eu am facut asa:
Am facut un rucsac pt a gasi energiile ce se pot obtine si daca gaseam o valoare mai mare decat G si cu costul < minim, actualizam minimul (initializat initial cu o valoare destul de mare). Mi'am creat o structura in care retin costul si energia unui generator si 2 vectori pe care ii construiesc la rucsac: E[ i ] == 1 => energia se poate obtine folosind generatoarele altfel E[ i ] == 0 si C[ i ] - costul necesar obtinerii energiei i ...

[•myrcea]

eu trimis o problema( energii),merge,dar evaluatorul imi da doar 0p imi apare eroare de compliare 

[•gabitzish1]

Nu e un bug ci sursa ta e de vina.. daca citeai putina documentatie, stiai ca in loc de void main() tre sa pui int main() si functia sa returneze 0.

[•myrcea]

ms

[•drywater]

am incercat cu greedy si imi da 45 puncte pe sursa

[•cos_min]

Incearca dinamica si o sa iei 100. 
Daca nu reusesti sa te prinzi, sfaturi gasesti in pag anterioare ale acestui subiect sau vezi ca sursele la pb asta sunt publice. Spor!

[•blue_phoenix]

Imi cer scuze ca scriu aici...am mai multe manuale si carti de C++ (cum ar fi "Algoritmi fundamentali in C++" de Doina Logofatu), si lucrez de aproximativ 2 saptamani, dar tot nu reusesc sa inteleg programarea dinamica.... , puteti sa-mi recomandati vreo carte care sa trateze mai clar subiectul?(am cautat linkuri, dar nu am gasit cine stie ce)Multumesc!

[•wefgef]

Din cormen ai citit? Este un capitol intreg despre dinamica acolo...

[•blue_phoenix]

nu stiu... cormen e carte sau problema? 

[•wefgef]

cormen, CLR sau biblia... se refera la cartea "Introducere in algoritmi". O poti cumpara de pe net in limba romana, sau ai o varianta in engleza, online, aici.

[•blue_phoenix]

Multumesc mult!
Pentru cine nu a inteles programarea dinamica, eu m-am lamurit din cartea Emanuelei Cerchez,"Culegere de probleme pentru liceu", editura Polirom.

[•Irnuk]

tinand cont ca nu stiu programare dinamica am incercat sa fac aceasta problema cu un greedy, dar iau doar 45 pct. La toate cele 11 teste pe care iau 0 primesc WA.
Este din cauza ca gresesc eu ceva, sau pe aceasta problema nu pot lua 100 cu greedy?

[•pauldb]

Nu, nu ar trebui sa poti lua 100 cu greedy, deoarece nu este o rezolvare corecta (presupun ca iti poti gasi exemple usor, pentru care nu ar trebui sa mearga rezolvarea ta). Ar fi bine sa inveti programare dinamica, nu cred ca o sa te descurci la concursuri fara.

[•popoiu.george]

Fac dinamica si tin o matrice Cost(i,j) = costul minim necesar pentru a da o energie >=j, folosind primele i generatoare si iau 0 puncte.

intr-un vector sum(i) retin suma energiilor primelor i generatoare.

Uitati cum fac.

Cod:

for(int i=1;i<=W;i++)Cost[0][j]=INF;
for(int i=1;i<=G;i++)
    {
   for(int j=1;j<=W;j++)
       {
       if( j-E[i]>=0 && sum[i-1]>=j-E[i] && Cost[i-1][j-E[i]]+C[i]<Cost[i-1][j] ) Cost[i][j]=Cost[i-1][j-E[i]]+C[i];
       else Cost[i][j]=Cost[i-1][j];
       }
    }

Am citit in topic ca au mai incercat si altii asa si nu le-a iesit si vreau sa stiu ce e gresit in judecata, ca sa inteleg mai bine dinamica. Imi puteti explica, va rog?  

[•vladtarniceru]

am si eu 2 intrebari
un generator poate fi pornit o data sau de mai multe ori?
si daca am :
  3
  4
  100 2
  200 3
  300 4
 
afisez -1?(pentru ca am dat prea multa energie?)

sau -1 afisez in cazul

  2
  1000
  1 2
  2 3

(pentru ca fol generatorul decat o singura data)

[•popoiu.george]

O data.

[•xtreme]

Testele nu corepund cu restrictiile din enunt:
1 < EGi,CGi < 10001
Am verificat cu assert.
http://infoarena.ro/job_detail/491459

[•SpiderMan]

Da, trebuie corectat asa : 0 <= EG_i, CG_i < 10001 . ( http://infoarena.ro/job_detail/491472?action=view-source )