AndrewLazarev's blog

By AndrewLazarev, 8 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  

7 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.
»
5 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

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

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

»
3 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

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

[submission:13417183][problem:2B] guys I am getting wrong answer on test case 13. Can you please look into this.

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why I will get WA on test 31?What should be noticed?

Here is my code: 18299053

  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Finally I figure out that I ignore the situations with zeros

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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[0] in s)
        s[r[0]] += parseInt(r[1]);
    else
        s[r[0]] = parseInt(r[1]);

    if (s[r[0]] > max[1]) {
        max[0] = r[0];
        max[1] = s[r[0]];
    }
}

print(max[0]);
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Found my logic error. Problem solved.

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      im having the same problem ... what is it can you please tell me?

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For further reading on Problem C, the circle in the solution is called the "Circle of Apollonius".

»
6 months 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

  • »
    »
    5 months 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