Lets find a solution for shifting a candy from the position (*x*_{1}, *y*_{1}) into position (*x*_{2}, *y*_{2}). On each step we shift (increase or decrease) *x*_{1} by *a* and *y*_{1} by *b*.

It is not difficult to understand that if |*x*_{2} - *x*_{1}| is not divisible by *a* and |*y*_{2} - *y*_{1}| is divisible by *b* answer doesn't exist.

We should also note that |*x*_{2} - *x*_{1}| / *a* and |*y*_{2} - *y*_{1}| / *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 (*x*_{1}, *y*_{1}) to (*x*_{2}, *y*_{2}) as *max*(|*x*_{1} - *x*_{2}| / *a*, |*y*_{1} - *y*_{2}| / *b*).

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

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.

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.

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 *a*_{i} 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 *a*_{i} such that there is no number to be droped out from it.

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.

In 374A why both

|x2-x1|/aand|y2-y1|/bmust be either even or odd??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.

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.

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.

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

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

Edit: no problem at all, sorry for inconvenience

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

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.