026 Energii

[•fluffy]

Aici puteţi discuta despre problema Energii.

[•SergiuH]

Imi poate da careva unul din testele 10-19 (sau macar unul asemanator),  pt ca nu gasesc niciunde greseala, si am verificat sursa de zeci de ori. Iar ideea de rezolvare zic ca-i buna, pt. ca pot stoarce 50 pct.

[•cristy]

Salut, eu am facut problema dinamic, adica am incercat sa o fac si nu stiu ce am gresit, ideea e ca am format un 2 vectori, en care retine true daca se poate pune in functie i unitati de energie si falsa in caz contrar, si cmin care retine costul minim pentru a restaura i unitati de energie...ce am gresit?...

[•Sergiu]

Problema asta e cea mai ciudata problema intalnita vreodata. In algoritm  am avut o structura
IF conditie1 then executa a:=b
ELSE IF conditie2 then executa a:=b    si am luat 15pct.

Dupa ce am inlocuit structura de mai sus cu:
  IF onditie1 or conditie2 then a:=b    am luat 90pct.

Si in acest algoritm foloseam acelasi vect pe post de vect boolean si imi murea pe testele 14 si 19. Am folosit acelasi algoritm cu vect boolean separat si culmea lua tot 90 pct dar imi murea pe testele 10 si 13. Dar cum o mana spala pe cealalta, in final am stors suta de pct  

[•stifmeister]

A rezolvat cineva problema asta cu programare dinamica?

[•Cosmin]

Pai altfel mi se pare cam greu ... E problema standard de knapsack (problema rucsacului).

[•cristy]

Si poate sa imi spuna si mie cineva ce am gresit? ca doar calculam toate energiile care se puteau obtine si retineam costurile minime pentru a obtine acea energie...e tinea minte costul minim pentru a se obtine energia , deci ce nu e bine?...in final calculam minimul dintre e, i>=energia minima ceruta...ce nu e bine?

[•stifmeister]

Unde gasesc informatii despre probleme standard de knapsack (problema rucsacului)? Un link mi-ar fi de mare ajutor!!! va multumesc

[•Cosmin]

Problema rucsacului e in majoritatea manualelor de a 10-a, si daca dai un search pe google cu "knapsack problem" sigur gasesti ceva linkuri utile ... invata sa te descurci si singur nu sa ti se dea mura in gura ca daca nu cauti si te documentezi singur nu ajungi departe mai ales ca e o problema clasica ... documentatie despre knapsack gasesti in tutorialele de pe topcoder in Cormen (pe care il gasesti la resurse web pe pagina noastra) la tutorialele de pe USACO, numai daca nu vrei sa gasesti nu o sa gasesti.

[•teplesnescdenutevezi]

mie imi da WA la testele 5 si 9. la celelalte merge ... are cineva vreo idee de ce ?

[•gogu]

probabil alea sunt testele cu raspuns -1 (nu ai solutie)

[•teplesnescdenutevezi]

nu...am verificat.

[•Ignition]

Imi poate spune cineva daca este vreun caz mai ciudat (in afara de cel cu -1), ca nu imi merge pe testul 7.

[•druid]

Eu cred ca e o problema cu evaluatorul... iau 0 la toate testele si am incercat si cu un printf("-1\n"); si tot 0.

[VladS]

Nu cred ca sunt gresite testele. Sigur gresiti la implementare. Si eu m-am chinuit mult pana sa imi iasa.

Faceti mai intai solutia usoara in M*N cu memorie M*N si apoi daca nu luati nici un WA liniarizati matricea.

[cristi8]

Eu cred ca e o problema cu evaluatorul

dap.. e o problema cu evaluatorul... sa speram ca se rezolva in curand..

[•bogdan2412]

Pentru testul
2
8
8 2
10 1
raspunsul e 1 (se foloseste generatorul care face energie 10 > necesarul de 8 ) sau e 2?

[•cristy]

raspunsul e 1...se foloseste cel care produce 10 energie...

[•supernova]

In enunt este specificat ca datele de intrare vor fi in asa fel incat solutia sa fie unica. Simplifica problema in vreun fel aceasta restrictie?

[•domino]

In enunt este specificat ca datele de intrare vor fi in asa fel incat solutia sa fie unica. Simplifica problema in vreun fel aceasta restrictie?

Nu.

[•alexthero]

Eu am facut programare dinamica in W*G si iau 40 de puncte restu TLE ... Ce complexitate ati facut voi? se poate face mai repede de atat?

Multumesc

[•gogu]

O solutie de complexitate O(W*G) trebuie sa ia 100 de puncte fara probleme. Vezi daca mai poti sa mai optimizezi la ea ceva si in primul rand ai grija sa nu folosesti O(W*G) memorie.
Daca faci dinamica pe matrice vezi ca se poate cu memorie liniara.

[•alexthero]

Mersi

Am transformat in O(2*W) memorie si merge am luat 100. Tot nu inteleg de ce merge mai repede asa decat pe matrice de W*G (care intra in memorie)... dar.. asa o fi. Ms

[•filipb]

Ca sa declare memorie, programul tau consuma timp... Si de aici e mai eficient cu vectori.

[•danielp]

Cand accesezi un element dintr-o matrice mare, timpul nu este tocmai neglijabil. La multe probleme de pe infoarena trebuie sa optimizezi destul de mult algoritmul pentru ca sa iei punctaj maxim:)