AndrewLazarev's blog

By AndrewLazarev, 15 years ago, In English

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.
  • Vote: I like it
  • +13
  • Vote: I do not like it

| Write comment?
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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.
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone solve 2B in python? I always got "Time limit exceeded " in test 17 or 18。 11495193

»
7 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have the same doubt, did you find an explanation for it?

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like 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.

»
2 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

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