Berezin's blog

By Berezin, 10 years ago, translation, In English

374A — Inna and the pink pony

Lets find a solution for shifting a candy from the position (x1, y1) into position (x2, y2). On each step we shift (increase or decrease) x1 by a and y1 by b.

It is not difficult to understand that if |x2 - x1| is not divisible by a and |y2 - y1| is divisible by b answer doesn't exist.

We should also note that |x2 - x1| / a and |y2 - y1| / b Should be both even or odd as shifting is performed at a time for both values.

We should also look up for a corner case when step dropes us out from the board.

Now we can determine the way from (x1, y1) to (x2, y2) as max(|x1 - x2| / a, |y1 - y2| / b).

Lets calculate it for all corners and choose minimum or determine that the answer doesn't exist.

374B — Инна и девять

We can divide the task into subtasks because if two adjacent digits have sum none-9 the number transformation doesn't depends on other side relatively to the position between this two digits. It means we should divide our task into subtasks of kind: x or xyxyxyx...xyxy where x + y = 9. We should multiply all such answers because we are looking for the whole number of variants.

For x answer is 1. What should we do for xyxyxy? Let its length is s. Then if s is even we simply receive s / 2 nines. If s is odd one digit (any of them) will stay. Thus each sequence xyxyxyxyx...xyxyxy with odd length s increases the answer IN s times.

374C — Inna and Dima

Our task is tranformed to the task of finding cycle or maximal way, but lets solve it without any graphs.

Lets run dfs from each digit D, memorizing all already calculated tasks. If we come into the cell we have already been (in one of the previous D) than we should simply add the maximal way length to our current length. Way length is increased not in each cell but only when we come into A. If we come into the cell we have already been on current step (in our dfs running) this is the cycle and we should stop the algorithm. Don't forget to change the color of cell after droping from recursiong because you will receive "false cycle". Simply set the colour to current when come into the cell but decrease it before end of recursion for this cell.

374D — Inna and sequence

Lets note that not more than n numbers, thus it will be not more than n dropings. We will run this process using data structure Segment Tree (you can use another structures). Lets calculate the number of numbers in current segment. When the number is added we should simply go down from the root to the leaf and increase value for each segment on the way by 1. Deletetion — vice versa. If there is enough numbers in the left subtree we should go into the right one, othervise — into the left one. Don't forget to shift the ai position by decreasing on i as all numbers are droped immidiately. And don't forget to break the cycle as soon as you reach first ai such that there is no number to be droped out from it.

374E — Inna and babies

We will make the binary search to find the answer. For each time let's generate our segments and rotate them to transform them into horizontal and verticle. We can use transformation (x, y) to (x + y, x - y). Don't forget to make the union of all segments which were at the one diagonal and have an intersection. You should sort all segments of one type and iterate through them updating the size of the segment. Now we should only determine if there is at least one rectangle. For example we can iterate each verticle segment updating the set of all horizontal which begin not later than our verticle. For each verticle (the left one) we should iterate the right verticle and now calculate the set of horizontal which not only begin not later than the left verticle but also don't end earlier than the right one. Now we should only determine is ther is two or more horizontal segments from the set which satisfy also y-conditions for current vertical.

  • Vote: I like it
  • +48
  • Vote: I do not like it

| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In 374A why both |x2-x1|/a and |y2-y1|/b must be either even or odd??

  • »
    »
    10 years ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    Well, you can only jump in a diagonal direction, so try drawing your way if you had to go:

    2 up and 2 left

    3 up and 3 left

    2 up and 1 left

    Only using \ or / jumps.

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

    let's say that u make a1 moves where u decrease x by a, a2 moves where u increase x by a, b1 moves where u decrease y by b, and b2 moves where u increase y by b. now since number of moves is independent of direction, we must have a1+a2 = b1+b2.

    now if the start point is (x1,y1) and the end point is (x2,y2), we have (x2-x1)/a = a2-a1 and (y2-y1)/b = b2-b1. adding these two results in (x2-x1)/a + (y2-y1)/b = (a2-a1) + (b2-b1).

    the above two equations tell us that the LHS of the second equation is even.

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

In problem B when the length of sequence is odd, answer must be increased in s/2+1 times. For example in xyxyxy...xyx any x can stay, and there are s/2+1 x.

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

For the first question: Last case: 1 5 1 3 1 1 I guess The answer exists and its 2. first step 1+1,3+1 2-1,4+1

My program gave wrong answer on test 37. http://codeforces.com/contest/374/submission/5464380

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

    cause (1+1,3+1) is outside of the board

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

I have a question (may be silly) about question D, when i look at some implementations for , it seems that for most of them complexity is like O(n*m*log(n)) (segment tree/bit )*(enumerating m)*(treating n query 1by1) ,why can these passes with n,m at 10^6 scale

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

    It is guaranteed that you will only attempt to access your segment tree/bit O(n) times because you can have only O(n) elements to drop.