infoarena

Aici puteţi discuta despre problema Medie (http://infoarena.ro/problema/medie).

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!

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 .

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

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?

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

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

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

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

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

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"!  :thumbup:

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

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..?   :sad:

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

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

Probabil nu folosesti un QuickSort randomizat...

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

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  :aha: ]. Imi cer scuze!

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

Imi da cinevaa un link al paginii ONI 2006?


Later edit: MULTUMESC ;)

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

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

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

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 ?

 ](*,)

Am o intrebare :D
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?  :?

Motivul pentru care iei un TLE e ca nu ai complexitatea cea mai fericita. Solutia oficiala este O(vmax^2), unde vmax este valoarea maxima din sirul V.

Multzam fain... asa mi-a intrat in timp  :yahoo:

Nu este cumva o greseala in enunt, la exemplul 2?  :) eu vad una: 2 este media aritmetica a 3 si 1     
(i,j,k): (3,1,4)
Ma insel? :-s

3 e numarul de elemente.

Scuze, am fost neatent :oops: