431 Medie

[•DITzoneC]

Aici puteţi discuta despre problema Medie.

[•Florian]

Salutare! Am incercat la problema asta un brute force...20 de puncte...ceva normal... Am aplicat apoi o cautare binara...40 de puncte... Am schimbat iar metoda, folosind decompunerea in suma de 2 termeni a numarului 2*v(i) + un vector de frecventa... tot 40 de puncte.. Iau TLE pe toate celelalte,cu orice metoda.. Poate cineva sa-mi dea un hint? eventual ce complexitate trebuie sa folosesc...Multumesc!

[•Binary_Fire]

Eu am facut in n^2 . Ai grija ca variabila in care retii numarul de solutii sa fie de tip long long , din cauza ca era de tip int aveam 1 tle .

[•cos_min]

Nu este necesar long long, mie mi-a mers cu int.

[•sigrid]

nu inteleg de ce, dar imi da tle pe ultimul test (folosesc unsigned long) si iau doar 60 pct . de ce se ia in considerare punctajul pe o grupa de teste?

[•marcelcodrea]

Pentru a nu se lua punctaje apropiate de cele maxime folosindu-se solutii neoptime !

[•sigrid]

multumesc pt raspuns totusi nu cred ca o sursa care pica pe un singur test nu este optima (nu ma refer neaparat la a mea )

[•silviug]

totusi nu cred ca o sursa care pica pe un singur test nu este optima

Totusi iese din timp pe un test ceea ce, dupa mine, inseamna ca e neoptima.

[•sigrid]

nu vreau sa te contrazic...ai dreptate , dar e corect ca o sursa care ia decat 6 teste sa aiba acelasi punctaj ca o sursa ce prinde 9 teste?

[•gabitzish1]

mmmda.... nu prea e corect....  ...care e ideea care a dus la gruparea testelor???

[•Florian]

Probabil gruparea testelor reprezinta un mod de a "imbunatati" testele. Din moment ce are loc gruparea, daca iei 100 inseamna ca ai o sursa extraordinara, altfel ai un punctaj mai mic [redus la jumatate, de cele mai multe ori]. Cred k acest mijloc este cel mai la indemana de a scapa de sursele ineficiente sau incorecte. Este o idee buna insa care m-a afectat si pe mine. Orikum..eu sunt "pro-grupare"! 

[•gabitzish1]

dar e corect ca o sursa care ia decat 6 teste sa aiba acelasi punctaj ca o sursa ce prinde 9 teste?

daca iei 100 de puncte, le iei fie ca sunt fie ca nu sunt grupate testele... daca nu, cum a zis sigrid, e o diferenta intre sursa de 60 si cea de 90, diferenta care se omite....

[•Florian]

Mda..ai dreptate! Insa raman la parerea k gruparea testelor nu ar trebui sa nemultumeasca pe nimeni...la urma urmei nu e neaparat un concurs..ci doar o arhiva de probleme..stiu k e ofticant..intrucat este o diferenta intre 90 de puncte si 60..insa asta e... Dar sa schimbam subiectul.. La problema asta ar trebui sa fac vreo sortare? Nu`mi dau seama cum sa scot n^2. Mi se pare ciudat. Ce "teorie" trebuie sa aplic? un hint ceva..?   

[•silviug]

nu vreau sa te contrazic...ai dreptate , dar e corect ca o sursa care ia decat 6 teste sa aiba acelasi punctaj ca o sursa ce prinde 9 teste?

In multe cazuri da... Admit ca sursa care prinde 9 teste e ceva "mai buna" decat cea care ia doar 6. Totusi, gruparea testelor asigura niste praguri mai bine definite. Daca vrei sa diferentiezi un brute force optimizat care ia 90 si o solutie pe bune care ia 100 ce faci?

Gruparea testelor in arhiva e menita sa va motiveze sa faceti surse cat mai corecte. Cu un punctaj de 60 esti mai motivat sa bagi tare decat daca ai fi luat 95

[•Tabara]

..sa bagi tare decat daca ai fi luat 95 ..

@offtopic
  Ar fi buna o grupare a testelor la problema Sume ! 
[ce m-am enervat cu 95-ul ala!  ]
 

[•Florian]

nu inteleg de ce, dar imi da tle pe ultimul test (folosesc unsigned long) si iau doar 60 pct . de ce se ia in considerare punctajul pe o grupa de teste?

Probabil nu folosesti un QuickSort randomizat...

[•devilkind]

nu inteleg la ce ai nevoie de sortare. Eu am facut fara nici o sortare in max^2 (max e elementul maxim din sir)

[•Florian]

Dapz..nu e nevoie de sortare...pornisem eu cu o idee initial pt care imi trebuia sortare, si dupa ce mi-am dat seama cum se face in n^2 am uitat sa mai abandonez sortarea...kiar nu e nevoie...[ am fost asa de adormit, incat imi facusem functia de sortare, insa uitam sa o apelez  ]. Imi cer scuze!

[•mihai0110]

pentru hinturi verificati si pagina ONI 2006, acolo e o solutie n^2 dar n-are niciun farmec daca o faci cu solutia lor

[•gabitzish1]

Imi da cinevaa un link al paginii ONI 2006?


Later edit: MULTUMESC

[•marcelcodrea]

http://www.isjdb.ro/oni2006/

[•DjSefu]

Iau si eu pe ultimul test tle dar nu inteleg de ce . Avand in vedere k pe windows face in 1.5secunde cu datele de intrare la maxim ar trebui sa ia sub linux 0.5 secunde. Imi explica si mie cineva de ce se intampla asta? 

[•CezarMocan]

Incearca sa folosesti operatiile pe biti, adica sa inlocuiesti x/2 cu x >> 1 si x*2 cu x << 1 si o sa-ti intre in timp si pe ultimul test  .

[•Tabara]

Am si eu o intrebare.
Eu am facut initial un O(N^2 * log(N) ). ( presupunand ca am a, b, c , am cautat binar (2*c -b, respectand precizarile din enunt) ).Totusi nu TLE-urile pe ultimele 6 teste ma deranjeaza, ci faptul ca iau WA pe pe testele 1, 3, 4. Am diferente foarte mici. ( chiar o unitate pe 2 teste ).Nu imi dau seama ce poate sa fie .... ( pe exemplele problemei imi da corect. ). Am tot facut Debug dar nu imi dau seama ce gresesc.

In al doilea rand, m-am uitat dupa aceea pe solutia oficiala.La ce foloseste functia aia de random() pe valorile sirului inainte de aplicarea efectiva a rezolvarii descrise ?

 

[•Mishu91]

Am o intrebare
Desi am facut-o in n^2, am facut toate operatiile pe biti(atat modulo, cat si impartirea), iar rezultatul e de tip long iau un TLE. Cam care ar putea fi motivele?