354 Campion

[•bogdan2412]

Aici puteţi discuta despre problema Campion.

[•ctlin04]

Va rog un hint pentru a lua 100 la problema asta, am facut un greedy care pica teste ca
Cod:
3 6
1 40
6 20
20 1
imi da raspunsul 3 in loc de 2, solutie care spre uimirea mea i-a 80 de puncte cu 2 teste incorect desigur, iar daca implimentez alt algoritm bazindu-ma pe aceleasi observatii dar care sigur da raspuns corect pe orice test atunci iau TLE la ultimile 5 teste si aceasta tot este firesc pentru ca teoretic a doua implimentare se apropie de O ( n^2 );
Rog pe cineva care a rezolvat sa se uite peste sursa mea sa-mi spuna macar daca e buna ideea sau trebuie cu totul altceva si daca e buna ideea atunci cum pot sa determin eficient daca un participant este la un moment oarecare <=T campion sau nu fara a parcurge tot sirul obtinut in urma prelucrarii datelor initiale, pls help 

[•veleandu]

Salut catalin.
Nu am facut problema, dar sper ca ideea mea e buna.

Nu am vazut solutia ta, dar sper ca nu e ca a mea  ca hintul meu sa te ajute.
O observatie e ca uni dintre concurenti nu conteaza pentru ca nu pot fi campioni.

Legat de chestia asta se pot scoate niste afirmatii privindui pe cei care pot sa fie la un momentdat campioni.
Nu stiu daca am fost foarte concis, dar nu am vrut sa zic prea multe.

Solutia e una frumoasa .. care foloseste sau nu prea categoria pe care o arata problema .. cea de "stiva".
Nu stiu ce sa zic despre asta.

Sper sa te ajute.

[•ctlin04]

Sa iti spun cum am facut:
La fel am observat ca unii concurenti nu pot deveni niciodata campioni, astfel din toti concurentii i-am selectat pe cei care au sansa sa fie campioni, adica mi-am creat o lista de concurenti ordonata descrescator dupa valoarea cresterii raitingului la fiecare unitate de timp si crescator dupa raitingul initial al concurentilor, in exemplu de mai sus am scris lista cum arata ea dupa sortare si selectare.
Acum e clar ca la momentul de timp 0 campion v-a fi ultimul concurent din lista, apoi controlez daca penultimul poate deveni campion, aceasta se intimpla in cazul in momentul de timp in care el il intrece pe ultimul este <=T, daca aceasta se intimpla atunci la momentul de fata el v-a fi campion, daca nu atunci el nu poate deveni campion, si asa mai departe pentru urmatorul concurent controlez daca poate sa il intreaca pe campionul curent pina la valoarea de timp T, daca da atunci campionul curent devine el insusi...
Aceasta solutie i-a 80 de puncte, greseala ei consta in faptul ca eu nu iau in consideratie cazul cind un concurent este intrecut de alt concurent cu un indice mai mic in lista inainte ca concurentul curent sa-l intreaca pe campionul curent, acesta este cazul testului de mai sus, cind concurentul 2 este intrecut de concurentul 1 inainte ca concurentul 2 sa-l intreaca pe concurentul 3, iar pentru a verifica acest caz este clar ca trebue de parcurs toti concurentii de la inceputul listei pina la pozitia curenta si astfel raspunsul este corect pe orice test dar complexitatea se apropie de n^2 si desigur nu intra in timp.
Cam asta sper ca am fost cit de cit explicit 

[•veleandu]

E ok cum zici tu.
Si eu am 2 solutii, e aceasi solutie dar difera un pic implementarea.
Pe amandoua am Killed by signal 6(SIGABRT). Si pe una am doar WA5, in timp ce pe cealalta am WA 5 si 6.
Cred ca e o problema cu precizia, dar nu stiu exact in ce consta ( nu folosesc nimic float )

Ce ai spus tu e ok.
La final mai poti face o observatie.
( eu am tinut lista ordonata descrescator dupa d )

aici e un hint care conduce catre o(n)
daca ai 3 concurenti
x,y,z
D

• >D[y]>D[z];

R

• <R[y]<R[z];

e clar ca la un momentdat concurentul z va fi inaintea lui x si y ( daca timpul e infinit )
iar daca z il depaseste pe y inainte ca y sa il depaseasca pe x, atunci e clar ca y nu mai poate fi campion

Sper sa te ajute.

Daca stie cineva ce are special testul 5 ..

[•Steve]

Testul 5 nu cred ca are nimic special saracu'. Vezi daca ai luat cazurile, de ex. cand a-ul din capul stivei = a-ul elementului curent.

[•ctlin04]

Eu cred ca testul 5 este ceva de genul:
4 2
1 50
20 3
20 2
20 1
Presupun ca tie iti da raspunsul 2, pe cind ar trebui sa dea 4, deoarece la momentul de timp 0, ultimii trei concurenti sunt campioni.
Eu nu pot lua nicidecum testul 6, la tine care e diferenta intre sursa care ia testul 6 si cea care nu-l ia?? 

[•veleandu]

Eu nu pot intelege ceva la programul meu
daca am

Cod:

bool low_time ( champ a, champ b )
    {
       if ( calc_timp(a)<= calc_timp(b))
            return 1;
        return 0;
    }

Cod:

double calc_timp ( champ a )
    {
        return ((double) (a.dp-a.d) / ( a.r-a.rp ) );
    }

e ok

dar daca pun

Cod:

bool low_time ( champ a, champ b )
    {      
        if ((double)((a.dp-a.d) / ( a.r-a.rp )) < ((b.dp-b.d) / ( b.r-b.rp )) )
            return 1;
        return 0;
    }

Sau chiar in loc sa impart inmultesc cealalte parte din inecuatie nu imi da bine.
Simt ca fac cu inima ..  practic am dat copy-paste la functia aia dar nu merge.

Catalin, cat iti da pe

Cod:

3 10000
20 0
8 8
5 10

ar trebui sa iti dea 3

[•visanr]

Cod:

 
bool low_time ( champ a, champ b )
    {      
        if ((double)((a.dp-a.d) / ( a.r-a.rp )) < ((b.dp-b.d) / ( b.r-b.rp )) )
            return 1;
        return 0;
    }

Nu ar trebui sa fie <=, ca in prima varianta?

[•ctlin04]

Imi da corect pe testul cela;
Uite daca iti da corect pe:
10 6
3 9
3 9
3 8
3 7
4 6
5 5
6 4
7 3
7 3
7 1
ar trebui sa dea 5

[•danalex97]

@ Alex : Nu ar trebui sa ai double si la a 2-a expresie ?  

Cod:

bool low_time ( champ a, champ b )
    {      
        if ( ( (double)((a.dp-a.d) / ( a.r-a.rp )) ) <= ( (double) ((b.dp-b.d) / ( b.r-b.rp )) ) )
            return 1;
        return 0;
    }

[•veleandu]

Pai acum merge ca am pus (double) peste tot 
Nu imi mergea exemplul tau catalin .. acum imi merge dar iau WA9
Daca vrei iti dau codul sa vezi diferente and so-on.

eu de exemplu cred ( cred ) ca nu imi mergea pentru ca iesea din tip, incearca si tu in loc de impartiri sa inmulesti fiecare membru si ... sa pui si tu (long long) sau double peste tot .. 

Succes si numai bine.

PS: nu conta <= adica ..
pana la urma nu aia era greseala
si era bine cu <

am dat eu cpy paste gresit >.> dar in esenta tot ramanea problema ( si cu < numai .. )
scuze de deranj 

[•danalex97]

Eu iau acum 90p cu WA pe 6. Am facut cu o stiva. Problema asta e culmea.   Oricum nu cred ca e relevant sa cauti greseala la asa o problema. Cel putin eu am gasit solutia in 10 min , am implementat in 10 min si am cautat greseala o ora. 

[•Steve]

Un bug, pe care l-am vazut rapid in sursa ta:

Cod:

while ( Val < Time[Size] && ( Val <= K )  && Size>0 ) -- Size;

In primul rand Val <= K nu e necesara din cauza ca ai pus deja conditia Val < Time[Size], in schimb, nu vad unde updatezi valoarea lui val (compari de fiecare data elementul cu varful stivei, pe care s-ar putea sa-l fi scos in while-ul ala...

Conditia

Cod:

if ( Val<0 ) continue;

n-am inteles ce rol are...am senzatia ca daca da val negativ, ar trebui pop-uit capul stivei, dar ma rog. (s-ar putea sa ma insel, nu sunt sigur cum sortezi, eu am sortat dupa a ca prioritate - am considerat concurentii functii liniare F(T) = aT + b)

Ai grija la conditii de genu "A[Stiva[Size]] == A[ i ]" cand A[] e vector de structi, etc. din cauza ca nu prea ai de unde sa stii cum se comporta operatorul==, poate sa nu fie definit corespunzator, poate sa compare locatiile de memorie. Not sure, though.

[•danalex97]

 Val <= K era lasat dinainte ( am tot modificat sursa ) , iar egalitatea la pair e bine definta. ( adica am mai folosit de multe ori si nu am observat sa fie ceva in neregula ). Daca Val da negativ inseamna ca am impartit la un numar negativ. (vezi in enunt )Oricum , merci  . Cred ca e un caz particular la care nu m-am gandit , nu de la implementare se trage ( spun asta pentru ca , Catalin a avut o abordare diferita si buseste acelasi test ).

[•Bogdan15]

Poate cineva sa imi dea o idee cum as putea rezolva problema utilizand o stiva?