Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

### AndrewLazarev's blog

By AndrewLazarev, 13 years ago, ## Problem A. Winner

To solve the problem we just need accurately follow all rules described in the problem statement. Let's describe in more details required sequence of actions.
1. First of all, we need to find the maximum score m at the end of the game. This can be done by emulating. After all rounds played just iterate over players and choose one with the maximum score.
2. Second, we need to figure out the set of players who have maximum score at the end of the game. We can do this in the same way as calculating maximum score. Just iterate over players after all rounds played and store all players with score equal to m.
3. And the last, we need to find a winner. To do this we will emulate the game one more time looking for player from the winner list with score not less m after some round.
This task demonstrates that sometimes it is easier to code everything stated in the problem statement, than thinking and optimizing.

## Problem B. The least round way

First of all, let's consider a case when there is at least one zero number in the square. In this case we can easily create a way with only one trailing zero in resulting multiplication - just output way over this zero number. The only case when this is not optimal way is when a way exists with no trailing zeroes at all. So, we can replace all 0's with 10's and solve the problem in general case. If there is an answer with no trailing zeroes - we will choose this one, otherwise we will output way over zero number.

So, we can consider that all numbers in the square are positive. Let's understand what the number of zeroes in the resulting multiplication is. If we go along a way and count number of 2's and 5's in numbers factorization then the number of trailing zeros will be min(number of 2's, number of 5's). This allows us to solve the problem independently for 2's and 5's. The final answer will be just a minimum over these two solutions.

Now, the last thing left is to solve the problem for 2's and 5's. New problem interpretation is the following: there is a square with numbers inside. We are to find a way with the minimal sum of the number over the way. This is classical dynamic programming problem. Let's consider that A[r,c] is the number in cell (r,c) and D[r,c] is the answer for this cell. Then

D[r,c] = min(D[r-1,c],D[r,c-1]) + A[r][c]

## Problem C. Commentator problem.

Let's take two stadiums and find out a set of points from which the stadiums are observed at the same angle. Not very hard mathematical calculation shows that this is a line if stadiums have the same radius and this is a circle if they have different radiuses. Let's define S(i,j) as a set of points from which the stadiums i and j are observed at the same angle. Given that centers of stadiums are not on the same line, the intersection of S(1,2) with S(1,3) contains no more than two points. If we know these no more that 2 points we can double-check that they satisfy the criteria and chose the point with the maximum angle of observation. Tutorial of Codeforces Beta Round #2  Comments (35)
 I have alternative solution for C. I did it with hill climbing.I made the observation that if I have the radii of the three circles r1, r2, and r3 and the distances from the commentator's point of view d1, d2, d3 then di / dj = ri / rj. Then I did hill climbing trying to minimize the maximum of the three such ratios. One last note - I found out that if my initial step was too huge then I got thrown into the infinity so I chose a relatively small step - 10.0 but allowed for multiple using of this step in the same direction without having it reduced.
•  I looked at your solution, can you clarify on why is your starting point is average of three coordinates of the centre of three circles. You are calculating curx and cury and dividing them by 3. https://codeforces.com/contest/2/submission/11093
•  This is the medicenter of the triangle
•  It means a lot, I was stuck on it whole night. Thanks for helping out!!
•  wonderful solution!
 » Consider this testcase for problem A: 6 a 3 b 3 c 3 c -1 b -1 a -1 What is the result? "a" or "c"? Thanks
•  » » a
 » Problem A took me longer than I thought it would because there were some traps that I did not really think about. Consider this test case that I made up, this may help for clarification: input: d 13 c 12 a 1 a 1 a 1 b 10 d -12 a 9 output: c
•  » » thanks you saved my day
•  » » after 5 years, thank you so much
 » Anyone solve 2B in python? I always got "Time limit exceeded " in test 17 or 18。 11495193
•  » » you can check it yourself.
•  » » » I hadn't found this page before. Thx for your reminding.
 » [submission:13417183][problem:2B] guys I am getting wrong answer on test case 13. Can you please look into this.
 » Why I will get WA on test 31?What should be noticed?Here is my code: 18299053
•  » » Finally I figure out that I ignore the situations with zeros
 » Trying to solve problem A but failed on test #10. Tried to debug but test input is truncated. What's wrong with my code (JS)? var n = parseInt(readline()); var i, r, s = {}, max = ['', -1001]; for (i = 0; i < n; i++){ r = readline().split(' '); if (r in s) s[r] += parseInt(r); else s[r] = parseInt(r); if (s[r] > max) { max = r; max = s[r]; } } print(max); 
•  » » Found my logic error. Problem solved.
•  » » » im having the same problem ... what is it can you please tell me?
 » For further reading on Problem C, the circle in the solution is called the "Circle of Apollonius".
 » can anyone please tell me why im getting TLE in testcase 31 Problem B.i am stuggling from so long.it would be so helpful.i cant figure it out. 27893278
•  » » Because one of the number may be 0 in that test case so take care of that while finding the number of 2's and 5's as factors for that number
 » "it should end in the least possible number of zeros.", what does this statement mean? Can somebody explain this
•  » » "it should end in the least possible number of zeros."Look at the following: - 1000 (ends with 3 zeros) - 1100 (ends with 2 zeros) - 1111 (ends with 0 zeros)They want 1111 in this case.
 » For PROBLEM 2BThe path that would give min for 2s wont necessarily give min for 5s, right ? Then why should we solve the problem for 2s and 5s independently ? Wont they be interlinked based on the min no of ending zero till the point we are calculating for ?
•  » » I have the same doubt, did you find an explanation for it?
•  » » » You don't want to find a path that minimizes both 2s and 5s, but you are looking for a path that minimizes the number of 10s. This path could be either the one with minimum 2s or minimum 5s (whichever is smaller).Proof: Suppose the path that minimizes the number of 10s does not minimize either the 2s or the 5s. Then there exists a path with fewer 2s or 5s. But this path would also have fewer 10s (since 10=5*2). Which is a contradiction.
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   Thank you!PS: This submission is pretty intuitive.
•  » » » » » Thanks moon crater the linked solution helped me a lot.
 » In Problem B, exists more than 1 solution for TC 3, and others.
 » 2 years ago, # | ← Rev. 2 →   Hello Guys, I did not understand what does it mean to look at a circle from the same angle? Can someone point me to more detailed explanation?Many Thanks
 » 2 years ago, # | ← Rev. 2 →   Can anybody please explain why I am getting WA at test case 10?..here is my solution
 » thank you mr. mike for everything. love from bd.
 » in questions "Winner" i didn't understand editorial who can explain the editorial
 » 3 months ago, # | ← Rev. 2 →   About question C, in fact the intersection of $S(1,2)$ and $S(1,3)$ will all satisfy the criteria, we only need to check for the maximum :The set of points that observe 2 stadiums equal angle is an Apollonius circle (a line is treat as a circle with radius $\infty$). Let's call $I_1, I_2, I_3$ and $X_1, X_2, X_3$ the internal and external similitude centers of 3 pair of circles, then the circle with diameter $I_iX_i$ is the said Apollonius circleBy direct apllication of Menelaus theorem $X_1, X_2, X_3$ are collinearAccording to Gauss-Bodenmiller theorem, these 3 circles are coaxial, which mean if any 2 of these circles have some common points, they all pass through such points