infoarena

Aici puteţi discuta despre problema Jocul (http://infoarena.ro/problema/jocul).

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. ](*,) ](*,)

Iti sugerez sa maresti si vectorul de tati.

He-he...ai avut dreptate....am luat 100! \:D/ \:D/

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

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

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

ok...mersi :ok:

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

Nu sunt cazuri particulare.

Dar se poate face si fara dinamica?

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

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.

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

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

O(N * Suma_lungimi) este si complexitatea oficiala.

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 ? :mrgreen:

Cum faci ? Cam rapida sursa pentru complexitatea aia.

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?

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  :D

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

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

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

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?

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

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

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

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

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

 :ok: Mersi Radu .Am luat 100 :yahoo:

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

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

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

refaceti testele!!! am luat 100 fara sa-mi iasa exemplul :thumbup: :rotfl: 8)

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? :-k 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!

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:
Daca tot nu iti iese scrie-mi in privat si mai iti explic...

Merci mult! :D 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 ?

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.

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

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


Imi da


Iar sursa ea 100..  :D :D
Eu am si sursa corecta doar am modificat-o si vad ca buseste testul dar ia 100..
Presupun ca asta-i rau ..  :)

Nu înţeleg de ce această sursă obţine 40 de puncte (http://www.infoarena.ro/job_detail/1451529 (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 (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.

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 ?

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.

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:
Voi incerca si voi reveni cu un edit, multumesc!

EDIT: still 40p !  http://www.infoarena.ro/job_detail/1458789?action=view-source

Încearcă:

3
1 2 5

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

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

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.

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.

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

Nu cred ca are rost sa folosesti long long.Daca folosesti int merge mai repede.

A mers cu int in loc de long long. Nu stiam ca tipul de date poate determina viteza. Mersi mult.

Uitati-va va rog putin pe sursa mea job #2193271.NU iau ultimile tree teste.Ma poate ajuta cineva?

Uitati-va va rog putin pe sursa mea job #2193271.NU iau ultimile tree teste.Ma poate ajuta cineva?

Uitati-va va rog putin pe sursa mea job  http://www.infoarena.ro/job_detail/2193271?action=view-source .NU iau ultimile tree teste.Ma poate ajuta cineva?