Hi all!

Today, June 12, when Russia celebrates Day of itself, Euro 2012 second round starts and I_love_natalia has a birthday, we present you Codeforces Round #124.

Contest was prepared by team Samara SAU Teddy Bears (craus, dalex, Hohol) and I_love_natalia. Also thanks to Alex_KPR and Codeforces team (Gerald, Delinur, MikeMirzayanov). We think that contest is very easy, and your task will be prove of refute this assertion :)

Scoring system is **dynamic** (Learn more about dynamic problem scoring).

Authors think that problems are sorted by difficulty in non-descending order.

Accepted solutions and successful hacks to you!

**UPD**. Contest is over, congratulations to the winners!

Div-1 (full results):

Div-2 (full results):

**UPD 2**. Tutorial is available.

Will the contest be ranked?

contests are rated normally :-/

vse deleted

Don't even think about that!

In ascending order by difficulty?

The authors believe so.

No, non-descending :)

:D

I'm not sure if the smiley indicates irony or that sweet feeling of disagreeing with the master, but for me the order actually seemed descending in difficulty (div2).

The contest doesn't seem to me as very easy :/

Subject narrative is a big problem！ It's too fuzzy to read...

wo ca

are you chinese?

What was the solution for Div2 problem A? I feel I'm missing something easy.

If at least one circle can be placed in the rectangle, then first wins, because he can place circle in the center and then play symmetrically. In other case second wins.

Wow. So nice! :) (btw, we were in the same room)

Nice questions...Short uncontradictory statements and all requiring to think..Although I did not perform well but still I got to learn a lot :)

Can someone please explain logic behind div 2 — A.

See this: http://codeforces.ru/blog/entry/4708#comment-96099

I took few cases , and In every case If FIRST can place the circle inside the rectangle then He can win otherwise , He can not win.

Some idea might be thought like if there are even no of circles possible in the rectangle , then He can just place a circle midway of two circles ,,, Means He can always change the configuration for winning move.

more clearer : if in the optimal path , if there are even no of circles inscribed in rectangle , then First can change the path by placing a circle midway of two circles . otherwise FIRST will win because last movement will be of FIRST , because no of turns are odd .

for problem D , can anybody tell me whether my idea is correct ?? for grid with position S if you are able to go to another S in it's adjacant 4 grids , Then I can walk infinitely , ans will be YES, other wise No

No.

thank you for your reply , Firstly I had an idea that if an (3 * n ) * (3 * m) grid ,,, We can go from one S to some other S then we can find a infinite cycle ,, But this used too much memory and got memory limit exceeded :(

i used the exactly idea that create an (3*n)*(3*m) maze. and while searching in the 9 times larger maze, i just terminate the process as soon as i find two 'S', then, i got an AC:) I just tried waht happened if i waiting for the searching process until it is finished, then, i got a MLE:(

Do you mean

two'S'includingthe stating 'S' (in the central block)? In other words, the starting 'S' and at leastone another?Yes. Actually, which 'S' is the starting one does not matter. But when you arrived a "border" of the larger maze, you should transfer your searching position to the oppsite "border" —— it does matter a lot :)

I think if we can go to any of the 'S' of 8 adjacent grids then it "Yes"

only itself is sufficient..

"We think that contest is very easy" You are kidding, aren't you?

I wonder how many people just guessed the answer to div2-A, without actually proving it. (I got to a proof, after I finally submitted the guessed one.)

may you explain your proof?

If First player can place even one disc, answer is "First". Since first player can always win by placing first plate at center of board. Then he can copy the moves of second player . (Because there will always a similar space available due to symmetry)

WOW, nice proof :)

brilliant, love it!! so elegant!

i tried hard to got the logic.finally i got it by your nice idea.

Happy birthdays dalex and I_love_natalia! The problems are nice. By the way, the start time is unusual, that makes me late for some minutes.

Actually, only I_love_natalia has a birthday today...

1 hour after contest is a football match in group A in Euro2012. In this group is Russia too :)

...I started the contest about 15 minutes later... To my surprise, I was in the top 20...... I had once thought that my rating would have descended dramatically... So strange...

Div1-A is

exactlythe same as SRM 518's Largest Subsequence, except that the constraint is larger... This might have given unfair advantage to those who have seen it before.And there's also one task from COCI that's really close to it.

You will have to add a new level above IGM.

I think that the only way is to add 'tourist' level for tourist.

An extra problem, only for tourist... Almost half an hour he was free, after solving the five problems.

Aliens.

Hello, I suppose it's better if you use just ordinary math. not something that like limit. I don't have any information about it. It's better if you would use some algorithmic problem or other problems related to programming instead of pure math. just my recommendation. I'm not a very professional participant. just participating here and don't know about other places. it's just a recommendation. and anyhow I appreciate your hard work for creating such a great contest. thanks.

Actually, the solution was given in the link below the test cases explanation.

really liked the content, although i found it difficult. particularly task A, which in my opinion was rather the hardest than the easiest... good job, guys!! :)

Any idea why my practice solution for div1 E TLEs (http://codeforces.com/contest/196/submission/1798783 ), while RAVEman's (slightly modified version: http://codeforces.com/contest/196/submission/1798819) easily passes? Both use Prim's algorithm in almost the same way. I went over his code line by line and can't find the key improvement.

I found 2 reason. 1. set is slightly slow than priority_queue so you solution take much more time. 2. test case is not strong enough. the way you choose start vertex is different from RAVEman (Reminder : portal might not be in order in input), he's lucky so choose largest portal number pass in time, but choose lastest portal number (in input) not.

After I fix #2 in your code to the same way as RAVEman , it's TLE at test case #39 1799522 and after I fix both #1 and #2 it's pass in 300 ms

UPD. fix font size

That's bad, I was too imprudent :( These solutions get TLE on 'reversed' test 36 where any vertex

iis renamed ton-i+ 1.UPD: New tests (76-95) were added. Try to pass them.Thanks!! I'm surprised set vs priority_queue would make such a big difference. TopCoder's STL tutorial says "the difference is about ~%0.1 of time", yet RAVEman passed test case #39 in only 50 ms. When I tried his code with set 1798838, it failed case #39.

As for the other reason, it seems the problem is that non-portal vertices can be visited multiple times. I haven't thought of a solution for this yet...

Actually, the set vs priority_queue issue might just be another vertex ordering problem in disguise. Submission 1801347 also fails case #39 even though the only change from the "modified RAVEman code" in my first post is changing the priority_queue< pl > to a priority_queue< pl, vector< pl >, greater< pl > >.

Alright, someone explained the real solution so I went ahead and implemented it! The trick is to make a sparse version of the graph of vertices which have portals. The "edges" in the portal MST will be shortest paths between pairs of portals in the original graph. There could be n^2 of these, but we don't actually need them all. MST edges are always minimum weight among edges in some cut of the graph. This solution is guaranteed to include all such edges.

Yeah, I just got lucky. I had just 15 minutes after I submitted D till the end of the round, so I decided to submit the most stupid solution that I could think of...

Usually that strategy works pretty well for me :)

And thanks for noticing the crap I wrote. This made me read the editorial to understand the intended solution.

Defeating the judge in 10 minutes is quite amazing ;)

It's nice to see a growing community around programming competitions; I still have lots to learn from all of you! (this was my first time coding MST)

In Div-2 Problem-B:

Test Case: 8

Why the answer is "-Infinity" instead of "Infinity"?

Look at this: Evaluating limits at infinity for rational functions

Because n > m and a[0] * b[0] < 0

You can simply draw a chart ;-) for example for x in ( 10, 30, 100, 300, 1000 ).

Input

cantouristsolveitlessthaninoneminute

Output

unfortunately, he can't

but he solved all problems less than 100 minutes

/*found my mistake*/