213 Jocul

[ditzone]

Aici puteţi discuta despre problema Jocul.

[Tabara Mihai]

Problema e izbitor de asemanatoare cu "Fair Sharing de la CEOI 1995."(Problema III ziua I)
Numai ca iau INVALID MEMORY pe 50% din teste.

[•Gabi]

· 5 £ n £ 1000;

Iti sugerez sa maresti si vectorul de tati.

[Tabara Mihai]

· 5 £ n £ 1000;

Iti sugerez sa maresti si vectorul de tati.

He-he...ai avut dreptate....am luat 100!

[•sakka]

        -e ceva mai special la testele 8 si 10?iau tle la ambele
          eh, mi-o iesit pana la urma.

[•jdv]

Nu cumva e gresit testul de la problema...?
joc.out
48 49
( suma numerelor este 104 deci raspunsul 48 49 nu poate fi bun in acest caz )...
Se pot obtine 52 si 52...

[•wefgef]

Citeste mai bine enuntul. Primul numar din fisierul de intrare este n, adica numarul de betisoare. Suma numerelor este 97, iar solutia din fisierul de iesire este buna .

[•jdv]

ok...mersi

[•c_e_manu]

ok...am trimis la problema asta foarte multe solutii...si maxim 60... nu intra pe 2 teste... ce este curios e ca daca modific o condtitie intra pe acele 2 teste, dar nu intra pe alte 3 teste... intrebarea mea e daca se poate face doar cu programare dinamica... asa mi-a spus cineva, dar din moment ce cu mici modificari algoritmul meu a intrat alternativ pe toate testele banuiesc ca este bun, doar ca inca nu e perfect... Daca ma puteti ajuta va rog... exista cazuri particulare? Eu nu am gasit... Ms!

[•gabitzish1]

Nu sunt cazuri particulare.

[•c_e_manu]

Dar se poate face si fara dinamica?

[•gabitzish1]

Vad ca ai luat 8 teste, probabil se poate gasi o solutie si fara dinamica. Dar de ce nu incerci dinamica, si inveti ceva nou? (rezolvarea e foarte simpla cu dinamica).

[•DITzoneC]

ok...am trimis la problema asta foarte multe solutii...si maxim 60... nu intra pe 2 teste... ce este curios e ca daca modific o condtitie intra pe acele 2 teste, dar nu intra pe alte 3 teste... intrebarea mea e daca se poate face doar cu programare dinamica... asa mi-a spus cineva, dar din moment ce cu mici modificari algoritmul meu a intrat alternativ pe toate testele banuiesc ca este bun, doar ca inca nu e perfect... Daca ma puteti ajuta va rog... exista cazuri particulare? Eu nu am gasit... Ms!

Probabil ca tu aplici o metoda greedy, care in functie de diverse conditii iti ia anumite seturi de teste, dar nu cred ca vei gasi niste conditii care sa dea raspuns corect pentru fiecare test.

[•c_e_manu]

Pai...da... asa mi s-a parut cel mai simplu... Banuiesc ca de aceea sunt grupate testele... ca era mult 80 de pcte pe o metoda gresita... chiar daca nu complet gresita... Ms oricum de ajutor... Vad eu ce fac...

[•Mishu91]

Cam ce complexitate ar trebui scoasa pt 100 de puncte?

L.E. : Nici nu imi vine sa cred ca am scos suta cu complexitatea O(n*suma elem. din sir/2) 

[•wefgef]

O(N * Suma_lungimi) este si complexitatea oficiala.

[•miculprogramator]

Eu nu ma prind, care-i treaba cu ultimele 3 teste? Fac problema in colmpexitatea lui wefgef, declar totul pe long si merge pe tot ce-am incercat eu. Care-i smecheria ?

[•klamathix]

Cum faci ? Cam rapida sursa pentru complexitatea aia.

[•miculprogramator]

Pe masura ce introduc numerele din fisier le fac si suma. Verifica daca suma%2==0, daca da, pun in fisier suma/2<<" "<<suma/2. Daca nu, pun in fisier suma/2<<" "<<suma/2+1 .  Gresesc ceva, sau ideea este mult mai complicata?

[•klamathix]

Tu acolo ai complexitate O(N) pentru ca faci doar citirea , nu O(N * S ) .Desi nu suna prea bine , e o coincidenta ca ai luat 7 teste ) . Uite un test mic pe care busesti :

2
7
2

Aici e dinamica si chiar una draguta daca vrei sa incepi s-o inveti 

[•andrei.finaru]

Am intalnit o situatie ciudata: iau 100 de puncte la problema Jocul, desi nu dau rapunsul corect pe exemplu. Sursa am trimis-o sa vad daca iau TLE si ar trebui sa gasesc o alta abordare (TLE+WA=probabl nu e buna ideea) si am vazut ca iau 100 de puncte. Eu abordez problema astfel: verific pentru fiecare numar cat e mult ma apropia de o valoare, fara sa o depasesc, adunandu-l cu valori calculate pentru numerele dinaintea lui. Intr-adevar, pe exemplu nu merge (da 46, nu 48), dar totusi a trecut de toate testele .

[•popoiu.george]

Un hint ?  Nu ma prind cum sa adaptez problema rucsacului ...

[•stocarul]

Un hint ?  Nu ma prind cum sa adaptez problema rucsacului ...

Faci rucsacul ca să vezi toate lungimile posibile ce le poți obține.
Pe tine te interesează să le alegi pe cele mai apropiate două lungimi de jumătatea lungimii totale.
Una va fi mai mică sau egală decât jumătatea lungimii totale, iar alta mai mare sau egală.

[•ctlin04]

Nu e cam strinsa limita de timp, am facut o dinamica de complexitate O ( n*suma_elementelor/2) si iau doar 40 puncte

[•harababurel]

si eu am aceeasi problema. algoritmul meu are complexitatea o(n*suma_totala) putin optimizat (cu dinamica ma duc pentru fiecare obiect i de la suma 1 la suma primelor i obiecte (asta e maximul pentru primele i) in loc sa ma duc pana la suma totala a celor n si sa calculez degeaba pe niste stari). am incercat si citire standard si cu streamuri, in ambele cazuri am 2 tleuri, pe testele 8 si 10. cum se pot lua 100p pe problema asta?