Problem А.
Since the restrictions were not so big you can offer many different solutions. For example, you can construct a graph with N * 4 vertices and use bfs. But there was a faster solution with complexity O(1): enumerate the integer points lying on the square, for example, as is shown below:
Then finding the number of a point by its coordinates isn’t difficult. For example if a point has coordinate y == n -> then its position is n + x (if the numeration, is as shown, i.e. starts with zero). It turns out that we have transformed the square into a line with a small complication: cells N * 4 - 1 and 0 are adjacent, so we have not a line but a circle, where for the base points from 0 to 4 * N-1 the distance between the adjacent two points is 1. It is easy to take the difference of indices of the points and find the distance when moving clockwise and counterclockwise: (a-b +4 * n)% (4 * n) and (b - a + 4 * n)% (4 * n), the shortest distance will be the answer.
Problem B
Under the restrictions on the number of requests, you cannot iteratively add staircase. But the problem is simplified by the fact that the number of cells in which it was necessary to know the number of stones was no more than 100. That’s why you can check for each "interesting" cell all the queries and calculate how much each of them adds stones, so the complexity is: O (K * M), which fits within the given 2 seconds well. A faster solution with complexity O(N + M + K) is as follows: we will keep in mind two variables: a – how many items should be added now to the cell, v - how much should change a next step. So problem is to update the value of a and v so that a equaled to the number of stones in the cell after all the operations, and v – to how much a increases during the transition to the next cell. Then the problem will be reduced to that you need to properly update a and v, which is not very difficult to do, for example if there is a request (x, y, z) – then in the cell x you need to add x to a and add 1 to v, since with each next cell the number of stones for some staircase will increase by 1. Similarly, after the cell y is passed you need to subtract 1 from v and pick up from “a” the current number of stones subquery. If you save all such pairs of queries in a single array and it's possible to calculate everything in one cycle.
Problem C
First, let's count how many there are arrays in which each successive element starting from the second one is no less than the previous one. To do this quickly, let’s take a piece of squared with height of one square and the length of N*2 - 1 square, then select N-1 squares and put crosses in them - let it encode some array, let the number of blank cells from the beginning of the array before the first cross be equal to the number of ones in the array, the number of blank cells from the first cross to the second – to the number of 2 in the array, and so on. It is easy to see that the number of empty cells will be equal to N * 2-1 - (N-1) = N. It turns out that each paper encodes an array which suits us, and moreover all the possible arrays can be encoded using such paper. There is exactly C (N * 2-1, N) different pieces of paper (the binomial coefficient of N * 2-1 to N). This number can be calculated by formula with factorials, the only difficulty is division. Since the module was prime - it was possible to calculate the inverse number in the field for the module and replace division by multiplication. So we get the number of non-decreasing sequences, respectively have the same number of non-increasing, we just need to take away those who were represented in both array sets, but they are just arrays with a similar number like {1,1,1,...,1} or {4,4,...,4,4} just subtract n.
Problem D
Let's see, if there is no occupied cells, then it is not difficult to calculate the answer - the answer is a sum of Manhattan distances, taking into account the fact that the Manhattan distance can be divided: first we can calculate the distance of one coordinate and then of another one and then just to sum up, so the answer is not difficult to find. What do we have when there are occupied cells? If the cell from which we seek the distance does not lie on the same horizontal or vertical with occupied cells – then it absolutely does not affect the difficulty of accessing the rest of the cells:
This happens due to the fact that in each cell from the previous distance front (the distance to the set of cells with maximum distance from the start cell, the fronts form a diamond as you can see in the picture or from the Manhattan distance formula) there are two ways how to get to the cell, we take into account the rule that no two cells can be adjacent (either diagonally or vertically or horizontally), it turns out that such a cell does not interfere with us. But a close look at the picture brings to mind the obvious: it is the cell which is located on the same vertical / horizontal that has only one neighbor from the previous front, let’s see what happens in such case:
All the cells after occupied one starts "to lag" at 2 in distance, but more importantly, that changed the front! Now (with the upper side of the front) are 2 cells for which the transition from the previous front is unique, and as a consequence there are two cells meeting of which will produce a new segment of a late cells, and the angle of the front will change again. Since we are only interested in one side of its expansion (on the other hand there can not be occupied cells by the condition) so we can assume that it was expand from the start cell:
It turns out that you can count how many cells will be "delayed", especially considering that the lag always equals to two. For each direction, you can choose each occupied cell and check in the left and right directions for adjacent cells series, and add delay for interval of free cell before occupied cell (in the current direction). It is possible to calculate such delays with complexity: square of the number of occupied cells (it is not greater than min(N, M)). The rest is details. You need to compute all Manhattan distances, taking into account the existence of occupied cells. To do this, first calculate the sum of distances for an empty field, then for each occupied cell calculate the distance to all the others - subtract it twice, as the extra distance is subtracted for the first time when we got out of this cell and for the second time when takes away from all other cells to the given one. But in this case we will take away twice the distance between two occupied cells - so we’ll have to add them (the complexity is also a square). A total complexity of solution is O (K ^ 2) where K is the number of occupied cells.
