Feedback Runda 6

[•vladii]

Runda 6 a concursului Monthly 2012 s-a încheiat. Felicitări primilor clasați!

Premiul special oferit de catre firma IXIA va merge la Heidelbacher Andrei, deoarece a rezolvat problema Impartiri avand penalizarea (56 de puncte) cea mai mica! Felicitari!

Asteptam opiniile si eventualele sugestii ale voastre în legatura cu organizarea, subiectele propuse și orice probleme intampinate.

Mult succes în continuare!

[•PlayLikeNeverB4]

Faine probleme! Avea ceva special testul 4 la Orient?

[•S7012MY]

Felicitari pentru runda. Ma bucur ca au inceput sa fie mai dificile problemele. ce idei ati avut la orient ?

[•PlayLikeNeverB4]

ce idei ati avut la orient ?

Cu aceasta ocazie imi poate confirma cineva daca e buna ideea. Am considerat graful neorientat cu costurile pe muchiile "inverse" fiind -c. Am cautat toate ciclurile si pentru fiecare am calculat suma muchiilor pozitive si separat a celor negative (in modul). Am luat minimul dintre aceste sume.

[•klamathix]

Mm ideea la orient era ca pentru fiecare muchie x -> y sa cauti drumul minim de la y la x. Muchiile au cost 0 daca le parcurgi in sensul bun si costul asociat daca le parcurgi invers.

[•Schumi]

Misto problemele, cu exceptia problemei zaruri. Sunt curios cum se face problema impartiri Cand puneti articolul cu solutii?

P.S. In seara asta primim rating? 

[•elfus]

Mi-au placut problemele, totusi au fost putin cam grele pentru o runda de monthly. Care era ideea la Impartiri? Si la orient am incercat cu Roy Floyd, dar cred ca am busit ceva. Solutia oficiala tot Roy Floyd era pentru aflarea tuturor drumurilor? Btw, vedeti ca pe pagina a doua este cineva cu penalizare 44 la impartiri, nu ar trebui sa castige acela premiul?

[•S7012MY]

Mm ideea la orient era ca pentru fiecare muchie x -> y sa cauti drumul minim de la y la x. Muchiile au cost 0 daca le parcurgi in sensul bun si costul asociat daca le parcurgi invers.

Intra in timp ?

[•klamathix]

Nu, omul de fier e out of contest. Si ca fapt general, cine vrea premiul trebuie sa submiteze de pe un cont cu nume valid.
La Impartiri cel mai mare dreptunghi ramas dupa taiere e de dimensiune max(x(i) - x(i - 1)) * max(y(j) - y(j - 1)) unde x() si y() sunt punctele in care se fac taieturi pe ox/oy. Iti faci o dinamica ca sa afli in cate feluri poti taia o axa astfel incat cea mai mare sectiune ramasa sa fie exact X cu X de la 1 la N. Apoi iti variezi ambele dimensiuni ale dreptunghiului maxim ramas si aduni la solutie acelea care au aria <= K.

@Petru Intra. Noi avem 1 secunda pe 2 teste si <= 200 ms pe restul.

[•Schumi]

Multumesc 

[•S7012MY]

http://acm.timus.ru/problem.aspx?space=1&num=1004 ->orient

[•mihaipopa12]

Felicitari, foarte misto problemele!   

[•danalex97]

Faine probleme. Mi-au placut toate , zaruri si orient in special.

[•klamathix]

http://acm.timus.ru/problem.aspx?space=1&num=1004 ->orient

Pai da, mi se pare genul de enunt la care s-au gandit si altii in alte locuri si in alte vremuri . Si nu e chiar acelasi lucru, oricum.

[•danalex97]

Cand o sa apara articolul cu solutii ?

[•dushmi]

Pagina pentru solutii este aici. Cei care au reusit sa rezolve probleme sunt rugati sa ne ajute, adaugand solutiile. Vom adauga noi rezolvarile la cele care raman necompletate .

Felicitari tuturor celor care au participat! 

[•scipianus]

@Petru Intra. Noi avem 1 secunda pe 2 teste si <= 200 ms pe restul.

Mda,chestia e ca eu trimisesem astazi o sursa (http://infoarena.ro/job_detail/765312) care lua 2 TLE-uri,iar apoi am modificat doar o singura chestie (cand scot din coada un nod la care distanta pana la el e deja mai mare decat solutia actuala,nu il mai expandez) si am luat 100pct (http://infoarena.ro/job_detail/765313) cu niste timpi surprinzator de mici (cel mai mare 80ms)

[•ctlin04]

Ma ajuta cineva si pe mine la problema "Orient", iau TLE pe testul 2 si 6, cu toate ca celelalte teste merg in maxim 4 ms, eu fac un dfs si surprind toate ciclurile posibile alegindul pe cel minim, iar in cazul cind costul devine mai mare decit minimul curent nu mai merg in directia respectiva  , se pare ca ideea e buna in timp ce celelalte teste merg asa de repede 

[•klamathix]

Ce ai tu acolo e un back optimizat si e normal sa nu-ti intre in timp 

[•darren]

Deoarece pe paginile problemelor nu se pot pune comentarii, o sa postez aici ceva legat de problema Zaruri.

Nu inteleg de ce pentru cazul N=2 rezultatul da 4.25. Strategia optima, pentru N=2, este sa mai dai odata cu zarul daca prima tura ai nimerit 1, 2 sau 3. In solutie s-a considerat ca, media daca mai dai odata este 3.5 (ceea ce e adevarat), si ca, atunci rezultatul e (3.5 + 3.5 + 3.5 + 4 + 5 +6) / 6 = 4.25.
Totusi, nu am inteles exact de ce este asa. Expected value e definit ca (valoare_posibila1 * probabilitate1 + valoare_posibila2 * probabilitate2 + ...). Pentru cazul N = 2, numarul de posibilitati totale pentru strategia optima este 21 ([1, 1..6], [2, 1..6], [3, 1..6], [4], [5], [6]). Numarul de cazuri in care la final am 1 este 3 (prima data as fi putut da 1, 2, sau 3). La fel e numarul de cazuri si pentru 2 si 3. Pentru 4, 5, si 6, numarul de cazuri este 3+1=4 (se adauga 1 pentru cazul cand nimeresc din prima 4, 5 sau 6). Asa, expected value este (1*3 + 2*3 + 3*3 + 4*4 + 5*4 + 6*4) / 21 = 3.71.

Imi poate spune cineva de ce nu este bun acest rationament?

EDIT: Mi-am dat seama singur, nu mai este nevoie.

[•a_h1926]

Salut Rares!
Eu am gandit altfel probabilitatea sa am o anumita valoare X la final. Probabilitatea ca la sfarsit sa am 1, 2 sau 3 este 3/6 * 1/6 (pentru ca e probabilitate 3/6 sa dau 1, 2 sau 3 din prima si atunci dau inca odata, si inmultesc cu 1/6 ca sa dau un numar la a doua aruncare), iar probabilitatea ca la sfarsit sa am 4, 5 sau 6 este 3/6 * 1/6 + 1/6 (1/6 fiind probabilitatea sa dau din prima, 3/6 e probabilitatea sa dau inca odata cu zarul si asta o inmultesc cu probabilitatea sa iasa un numar la a doua aruncare). Acesta a fost rationamentul meu. Daca vrei, mai putem discuta diseara.

[•darren]

Multumesc pentru raspuns!
Eu consideram ca probabilitatea de a nimeri un numar din a doua aruncare este aceeasi cu cea de a nimeri numarul din prima.
M-am corectat si mi-a iesit si problema pana la urma.  

[•a_h1926]

Salut! Stie cineva cand va avea loc Runda a 7-a a concursului Monthly? Va multumesc anticipat.

[•dushmi]

Undeva la inceputul lui august. Nu stim exact cand . In principiu pe 6-7.

[•a_h1926]

Multumesc mult .