260A - Adding Digits

At first try to add to the right one digit from 0 to 9. If it is impossible write -1. In other case, the remaining n–1 digits can be 0 because divisibility doesn’t change.

260B - Ancient Prophesy

In this problem you have to consider every date from 2013 to 2015 year (there is no leap years in this interval), count occurrences of this date and find maximum. In one year there is 365 days, so the complexity of the solution (3·365·N).

260C - Balls and Boxes

Firstly describe simple solution. We will get by one ball from boxes (we begin from box x) from right to left (action back). At some moment there will be 0 balls in current box. This box is the first box in our initial problem (from which we took all balls and begun to put). In this box we put all balls, which we get from all boxes.

But we can’t solve the problem in such a way, because it is too long. Note, that before we meet the situation when in some box will be 0 balls, we will go through every element of array several times and subtract 1. So we can make our solution faster. We can subtract from every element of array minv - 1, where minv — minimum in array. After that you should do O(N) operations, that were mentioned above.

260D - Black and White Tree

The problem can be solved constructively maintaining the following invariant (rule) — the sum of the white vertices equals to the sum of the black vertices. The tree is a bipartite graph, so we build bipartite graph with no cycles, which will satisfy the conditions of the problem. Parts of graph will be black and white vertices.

On each step we will choose vertex v with minimum sum from white and black vertices. Then find any vertex of opposite color u and add edge (u, v) with weight s[v], and subtract from sum of u sum of v, that is s[u] = s[u]–s[v]. After each step one vertex is deleted. That’s why there will be no cycles in constructed graph. When we delete last vertex of one of colors, all other vertices can be joined in any correct way with edges of weight 0.

260E - Dividing Kingdom

Consider 9! variants of location of integers a[i] on 9 areas. When we consider some location (some grid), we can easily find amount of cities to the left of the left vertical line, to the right of the right vertical line, below the lower horizontal line and above the upper horizontal line. All these numbers is sum of three values a[i].

We assume that the lines of the answer are always in half-integer coordinates. Then, knowing the above 4 numbers, we can uniquely determine separately for x and y how to accommodate all the 4 lines. It remains only to check that in all areas there is desired number of points.

For each of four zones (to the left of the left vertical line, to the right of the right vertical line, below the lower horizontal line and above the upper horizontal line) separately check, that all three areas have correct number of cities. It can be done offline using scan-line and segment-tree, which can find sum on interval and change value in some point. You should put all queries in some array, sort them and process from left to right. Note, when you check 8 from 9 areas for every 9! variants of location, the last area (central) could not be checked, it will be correct automatically.