611A - Новый год и дни

There are two ways to solve this problem.

The first is to hard-code numbers of days in months, check the first day of the year and then iterate over days/months — http://ideone.com/4TYPCc

The second way is to check all possible cases by hand. The 2016 consists of 52 weeks and two extra days. The answer for "x of week" will be either 52 or 53. You must also count the number of months with all 31 days and care about February. http://ideone.com/Bf9QLz

611B - Новый год и старые свойства

Each number with exactly one zero can be obtained by taking the number without any zeros (e.g. 63₁₀ = 111111₂) and subtracting some power of two, e.g. 63₁₀ - 16₁₀ = 111111₂ - 10000₂ = 101111₂. Subtracting a power of two changes one digit from '1' to '0' and this is what we want. But how can we iterate over numbers without any zeros? It turns out that each of them is of form 2^x - 1 for some x (you can check that it's true for 63₁₀).

What should we do to solve this problem? Iterate over possible values of x to get all possible 2^x - 1 — numbers without any zeros. There are at most values to consider because we don't care about numbers much larger than 10¹⁸. For each 2^x - 1 you should iterate over powers of two and try subtracting each of them. Now you have candidates for numbers with exactly one zero. For each of them check if it is in the given interval. You can additionally change such a number into binary system and count zeros to be sure. Watch out for overflows! Use '1LL << x' instead of '1 << x' to get big powers of two. http://ideone.com/Kfu8sF

611C - Новый год и домино

How would we solve this problem in O(wh + q) if a domino would occupy only one cell? Before reading queries we would precalculate dp[r][c] — the number of empty cells in a "prefix" rectangle with bottom right corner in a cell r, c. Then the answer for rectangle r1, c1, r2, c2 is equal to dp[r2][c2] - dp[r2][c1 - 1] - dp[r1 - 1][c2] + dp[r1 - 1][c1 - 1]. We will want to use the same technique in this problem.

Let's separately consider horizontal and vertical placements of a domino. Now, we will focus on horizontal case.

Let's say that a cell is good if it's empty and the cell on the right is empty too. Then we can a place a domino horizontally in these two cells. The crucial observation is that the number of ways to horizontally place a domino is equal to the number of good cells in a rectangle r1, c1, r1, c2 - 1.

You should precalculate a two-dimensional array hor[r][c] to later find the number of good cells quickly. The same for vertical dominoes. http://ideone.com/wHsZej

611D - Новый год и древнее пророчество

By {x... y} I will mean the number defined by digits with indices x, x + 1, ..., y.

Let dp[b][c] define the number of ways to split some prefix (into increasing numbers) so that the last number is {b... c} We will try to calculate it in O(n²) or . The answer will be equal to the sum of values of dp[i][n] for all i.

Of course, dp[b][c] = 0 if digit[b] = 0 — because we don't allow leading zeros.

We want to add to dp[b][c] all values dp[a][b - 1] where the number {a... b - 1} is smaller than {b... c}. One crucial observation is that longer numbers are greater than shorter ones. So, we don't care about dp[a][b - 1] with very low a because those long numbers are too big (we want {a... b - 1} to be smaller than our current number {b... c}). On the other hand, all a that (b - 1) - a < c - b will produce numbers shorter than our current {b... c}. Let's add at once all dp[a][b - 1] for those a. We need . Creating an additional array with prefix sums will allow us to calculate such a sum in O(1).

There is one other case. Maybe numbers {a... b - 1} and {b... c} have the same length. There is (at most) one a that (b - 1) - a = c - b. Let's find it and then let's compare numbers {a... b - 1} and {b... c}. There are few ways to do it.

One of them is to store hashes of each of n·(n + 1) / 2 intervals. Then for fixed a, b we can binary search the first index where numbers {a...} and {b... } differ. http://ideone.com/Rrgk8T. It isn't an intended solution though. Other way is to precalculate the same information for all pairs a, b with dynamic programming. I defined nxt[a][b] as the lowest x that digit[a + x] ≠ digit[b + x]. Now, either nxt[a][b] = nxt[a + 1][b + 1] + 1 or nxt[a][b] = 0. http://ideone.com/zczsc3

611E - Новый год и три мушкетёра

The answer is  - 1 only if there is some criminal stronger than a + b + c. Let's deal with this case and then let's assume that a ≤ b ≤ c.

Let's store all criminal- s in a set (well, in a multiset). Maybe some criminals can be defeated only by all musketeers together. Let's count and remove them. Then, maybe some criminals can be defeated only by b + c or a + b + c (no other subsets of musketeers can defeat them). We won't use a + b + c now because it's not worse to use b + c because then we have the other musketeer free and maybe he can fight some other criminal. Greedily, let's remove all criminals which can be defeated only by b + c and at the same time let a defeat as strong criminals as possible. Because why would he rest?

Now, maybe some criminals can be defeated only by a + c or b + c or a + b + c. It's not worse to use a + c and to let the other musketeer b defeat as strong criminals as possible (when two musketeers a + c fight together).

We used a + b + c, b + c, a + c. We don't know what is the next strongest subset of musketeers. Maybe it's a + b and maybe it's c. Previous greedy steps were correct because we are sure that .

Now in each hour we can either use a, b, c separately or use a + b and c. Let's say we will use only pair a + b and c. And let's say that there are x criminals weaker than a + b and y criminals weaker than c. Then the answer is equal to . The explanation isn't complicated. We can't be faster than because we fight at most two criminals in each hour. And maybe e.g. y (because c is weak) so c will quickly defeat all y criminals he can defeat — and musketeers a + b must defeat x - y criminals.

Ok, we know the answer in O(1) if we're going to use only a + b and c. So let's assume it (using only these two subsets) and find the possible answer. Then, let's use a, b, c once. Now we again assume that we use only a + b and c. Then we use a, b, c once. And so on.

What we did is iterating over the number of times we want to use a, b, c. http://ideone.com/R3Oy3F

611F - Новый год и уборка

Let's not care where we start. We will iterate over robot's moves.

Let's say the first moves are LDR. The very first move 'L' hits a wall only if we started in the first column. Let's maintain some subrectangle of the grid — starting cells for which we would still continue cleaning. After the first move our subrectangle lost the first column. The second move 'D' affects the last row. Also, all cells from the last row of our remaining subrectangle have the same score so it's enough to multiply the number of cells there and an index of the current move. The third move 'R' does nothing.

Let's simulate all moves till our subrectangle becomes empty. To do it, we should keep the current x, y — where we are with respect to some starting point. We should also keep max_x, max_y, min_x, min_y — exceeding value of one of these four variables means that something happens and our subrectangle losts one row or one column.

But how to do it fast? You can notice (and prove) that the second and and each next execution of the pattern looks exactly the same. If we have pattern RRUDLDU and the first letter 'U' affects out subrectangle in the second execution of the pattern, then it will also affect it in the third execution and so on. If and only if.

So, we should simalate the first n moves (everything can happen there). Then, we should simulate the next n moves and remember all places where something happened. Then we should in loop iterate over these places. Each event will decrease width or height of our subrectangle so the complexity of this part is O(w + h). In total O(w + h + n). http://ideone.com/xrU9u2

CHALLENGE FOR PROBLEM F (CLEANING ROBOT) — I was considering an alternative version of this problem, harder one. The same constraint for n but this time h, w ≤ 10⁹. Describe a solution in comments and optionally implement it (it should get AC on this problem, right?). I will mention here the first person to solve this challenge.

611G - Новый год и торт

We are given a polygon with vertices P₁, P₂, ..., P_n. Let Poly(i, j) denote the doubled area of a polygon with vertices P_i, P_i + 1, P_i + 2, ..., P_j - 1, P_j. While implementing you must remember that indices are in a circle (there is 1 after n) but I won't care about it in this editorial.

We will use the cross product of two points, defined as A × B = A.x·B.y - A.y·B.x. It's well known (and you should remember it) that the doubled area of a polygon with points Q₁, Q₂, ..., Q_k is equal to Q₁ × Q₂ + Q₂ × Q₃ + ... + Q_k - 1 × Q_k + Q_k × Q₁.

Let smaller denote the area of a smaller piece, bigger for a bigger piece, and total for a whole polygon (cake).
smaller + bigger = total
smaller + (smaller + diff) = total
diff = total - 2·smaller (the same applies to doubled areas)
And the same equation with sums:
where every sum denotes the sum over possible divisions.

In O(n) we can calculate total (the area of the given polygon). So, the remaining thing is to find and then we will get (this is what we're looking for).

For each index a let's find the biggest index b that a diagonal from a to b produces a smaller piece on the left. So, .

To do it, we can use two pointers because for bigger a we need bigger b. We must keep (as a variable) the sum S = P_a × P_a + 1 + ... + P_b - 1 × P_b. Note that S isn't equal to Poly(a, b) because there is no P_b × P_a term. But S + P_b × P_a = Poly(a, b).

To check if we should increase b, we must calculate Poly(a, b + 1) = S + P_b × P_b + 1 + P_b + 1 × P_a. If it's not lower that then we should increase b by 1 (we should also increase S by P_b × P_b + 1). When moving a we should decrease S by P_a × P_a + 1.

For each a we have found the biggest (last) b that we have a smaller piece on the left. Now, we will try to sum up areas of all polygons starting with a and ending not later than b. So, we are looking for Z = Poly(a, a + 1) + Poly(a, a + 2) + ... + Poly(a, b). The first term is equal to zero but well, it doesn't change anything.

Let's talk about some intuition (way of thinking) for a moment. Each area is equal so the sum of cross products of pairs of adjacent (neighboring) points. We can say that each cross product means one side of a polygon. You can take a look at the sum Z and think — how many of those polygons have a side P_aP_a + 1? All b - a of them. And b - a - 1 polygons have a side P_a + 1P_a + 2. And so on. And now let's do it formally:

Poly(a, a + 1) = P_a × P_a + 1 + P_a + 1 × P_a
Poly(a, a + 2) = P_a × P_a + 1 + P_a + 1 × P_a + 2 + P_a + 2 × P_a
Poly(a, a + 3) = P_a × P_a + 1 + P_a + 1 × P_a + 2 + P_a + 2 × P_a + 3 + P_a + 3 × P_a
...
Poly(a, b) = P_a × P_a + 1 + P_a + 1 × P_a + 2 + P_a + 2 × P_a + 3 + ... + P_b - 1 × P_b + P_b × P_a

Z = Poly(a, a + 1) + Poly(a, a + 2) + ... + Poly(a, b) = 
 = (b - a)·(P_a × P_a + 1) + (b - a - 1)·(P_a + 1 × P_a + 2) + (b - a - 2)·(P_a + 2 × P_a + 3) + ... + 1·(P_b - 1 × P_b) + 
 + P_a + 1 × P_a + P_a + 2 × P_a + ... + P_b × P_a

The last equation is intentionally broken into several lines. We have two sums to calculate.

1. The first sum is (b - a)·(P_a × P_a + 1) + (b - a - 1)·(P_a + 1 × P_a + 2) + ... + 1·(P_b - 1 × P_b). We can calculate it in O(1) if we two more variables sum_product and sum_product2. The first one must be equal to the sum of P_i × P_i + 1 for indices in an interval [a, b - 1] and the second one must be equal to the sum of (P_i × P_i + 1)·(i + 1). Then, the sum is equal to sum_product * (b + 1) - sum_product2.

2. The second sum is P_a + 1 × P_a + P_a + 2 × P_a + ... + P_b × P_a = SUM_POINTS × P_a where SUM_POINTS is some fake point we must keep and SUM_POINTS = P_a + 1 + P_a + 2 + ... + P_b. So, this fake point's x-coordinate is equal to the sum of x-coordinates of P_a + 1, P_a + 2, ..., P_b and the same for y-coordinate. In my code you can see variables sum_x and sum_y.

Implementation. http://ideone.com/RUY5lF

611H - Новый Год и забытое дерево

There are at most k = 6 groups of vertices. Each grouped is defined by the number of digits of its vertices.

It can be probed that you can choose one vertex (I call it "boss") in each group and then each edge will be incident with at least one boss. We can iterate over all k^k - 2 possible labeled trees — we must connect bosses with k - 1 edges. Then we should add edges to other vertices. An edge between groups x and y will "kill" one vertex either from a group x or from a group y. You can solve it with flow or in O(2^k) with Hall's theorem. http://ideone.com/7KuS1l