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.
- 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.
- 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.
- 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.
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.
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://mirror.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
Anyone solve 2B in python? I always got "Time limit exceeded " in test 17 or 18。 11495193
you can check it yourself.
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
For PROBLEM 2B
The 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.
Thank you!
PS: This submission is pretty intuitive.
Thanks moon crater the linked solution helped me a lot.
Thanks, Was looking for this explanation.
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 circle
By direct apllication of Menelaus theorem $$$X_1, X_2, X_3$$$ are collinear
According 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