### ivan.popelyshev's blog

By ivan.popelyshev, 13 years ago, translation, Lets start from the end.

## Problem С. Commentator problem

Let R be the distance from point А to a circle with center О and radius r. From this point the circle is observed at the angle .
So, the three stadiums are observed at the same angle if R1 / r1 = R2 / r2 = R3 / r3.
Take two different points A, B. The set of points C that AC / BC = const is either a line (perpendicular bisector of AB) or a circle with center somewhere on the line AB. This circle is easy to find. It contains two points that lie on AB and satisfy AC / BC condition.

Let X1 be the set of points from which stadiums 1 and 2 are observed at the same angle. Let X2 be the set of points from which stadiums 2 and 3 are observed at the same angle. The answer belongs to both X1 and X2 . The centers of the three stadiums don't lie on one line, so the number of points in the intersection of  X1 and X2 will be finite.
Check them all. The answer is the point that lies closer to any of the stadiums. The stadiums don't intersect, so that point will not lie inside any of them.
How to get a big circle for X1 : put the centers of the stadiums in the points far away, for example in (0, 0) and (1000, 0). The ratio of the radii should be the closer possible to 1, for example . The center and the radius of the new circle will have the order 106 . The answer should be known with 10 - 5 precision. Roofly speaking, we need 11 digits, double precision will be enough.

## Problem B. The least round way

Let us solve the problem in the case of positive matrix.
Let the number in the end be N = 2k· 5m·(other primes). The number of zeroes at the end of N is equal to min(k, m). At the aid of dynamic programming find minimal value of k (let it be k1) and minimal value of m (let it be m1), and paths that lead to these values. In case of k1 < m1 choose the path corresponding to k1, else  m1.
So min(k, m) is the upper bound for the answer. Let us prove that it is the lower bound too. If there exists a path leading to a number with number of zeroes less than min(k, m) then in the factorization of that number the power of two is k < k1 or the power of five is m < m1. We come to a contradiction.
So we need to calculate the power of 2 and 5 in the factorization of each value in the matrix and use dynamic programming on each of the two matrices.

In the case of matrix containing zeroes, calculate separately the best path not containing zeroes and any path containing zeroes:

Replace all 0 by 10 and use the method described above. For paths containing zeroes the result will contain at least one zero at the end. If the method returned a number without zeroes at the end, the corresponding path is the answer, else any path containing zeroes is the answer.
The complexity of the algorithm depends on the complexity of the dynamics, it is O(N· M).

## Problem A. Winner

Simple problem, just code it.
At the first pass calculate the sum of points for each player at game end. Let M be the maximum of these sums. At the second pass check every round. If current player X has not less than M points and his final score is equal to M then he is the winner.
The following test illustrates that player could receive more than M points, then lose some and, finally, win.
Input:
Masha 12
Masha -5
Sasha 10
Masha 3
Output:
Masha Tutorial of Codeforces Beta Round #2  Comments (29)
 Excellent tutorial !! Would like to see more from you...
 » task B, submission #3726143, I got: Test: #31, time: 3421 ms., memory: 172 KB, exit code: 0, checker exit code: 1, verdict: WRONG_ANSWER ... Checker Log wrong answer Jury has better answer: ja=1 vs pa=2974 Can I see what concrete input was in this test to find the reason? And who is Yuri? ))
•  » » There is one zero in the test — the best answer.
•  » » » you saved hours of debugging. Thanks mate
 » 7 years ago, # | ← Rev. 3 →   In problem C, I've seen many people using this for checking the equality of R1 / r1 = R2 / r2 = R3 / r3:pow(R1/r1-R2/r2, 2)+pow(R2/r2-R3/r3, 2)+pow(R3/r3-R1/r1, 2);Why we have to sum up the squares of the difference rather than sum up the absolute values of the difference, like:fabs(R1/r1-R2/r2, 2)+fabs(R2/r2-R3/r3, 2)+fabs(R3/r3-R1/r1, 2);(This calculation doesn't work and I have no idea why...)
 » could someone help me with the problem B, please ? here's my code: http://ideone.com/1Juljlthanks in advance :)
•  » » why didn't it appear in the recent actions? I need some help.
 » 19849823 problem B test case 5 wrong answer expected zero count mismatched with actual:0 vs 1 thanks in advance!!
 » why problem B is O(n*m)? isn't it o(n*n)?
 » What if two or more players getting the same points at the end. How will you write a program to tell that who achieves the maximum score first during input of "name score". ?
•  » » the first one achieved will be the winner
 » "it should end in the least possible number of zeros.", what does this statement mean? Can somebody explain this
•  » »
 » what is wrong with this solution http://codeforces.com/contest/2/submission/44454112
•  » » It fails in test 10.
•  » » Take a simple test: 4 a 10 b 2 b 3 a -10Answer: b
•  » » » I got it thnx.
•  » » » i got b in my code but wrong answer at test case 10
•  » » » Thank U get help from this test case !
 » not able to find the bug please guys help me http://codeforces.com/contest/2/submission/44475190
 » 2 years ago, # | ← Rev. 3 →   [Solved]
 » 2 years ago, # | ← Rev. 2 →   In problem B if the input is 31 2 34 5 6 7 8 9can one solution could be RRDD too?
•  » » Yes, I think so. Usually in the problem statement, it says "if there are more than one such path, print any possible path." I don't know why they didn't say it in this problem.
 » 2 years ago, # | ← Rev. 4 →   Problem A)Failing test case 10 W.A Can anybody please help me ?my submission link is here — https://codeforces.com/contest/2/submission/94976880 int n; map score_board; map> rev_board; void solve() { cin >> n; for(int i=0; i> name >> score; score_board[name] += score; rev_board[score_board[name]].push_back(name); } auto it=rev_board.end(); --it; cout << it->second; } 
 » Just a doubt, why aren't we taking the time to find the number of 2's and no of 5's in a number in the calculation of time complexity?. I mean shouldn't the time complexity be something like O(N*M*log(N)*log(M))?
•  » » This is in Problem B.
 » Sasha reaches 10 point at round 3 but Masha reaches 10 point at round 4. I seams that Sasha reaches the max before Masha. Why is Masha the winner in this test case?
•  » » Masha gets 12 points at round 1
 » https://codeforces.com/contest/2/submission/123555547 could someone help me?it fails on Test #22. I don't figure out what is wrong.===Output is:2469DDDRDDDDDDRRDDDDDDDRD...Answer is:2469DDDRDDDDDDRRDDDDDDDRD...Checker Log:wrong answer expected zero count mismatched with actual: 2469 vs 2477