353A - Domino

Let's denote the sum of numbers on the upper halves of pieces as s₁, and the sum on the lower halves — s₂. If this sums are even, than the answer is obviously 0. Note, that if the numbers on both halves of piece have the same parity, than parity of s₁ and s₂ won't change after rotation this piece. If the numbers on halves have different parity, than parities of both s₁ and s₂ will change after rotation. Therefore, if s₁ and s₂ have different parities, than the answer is  - 1. If both s₁ and s₂ are odd, than we should check, if there is a piece with numbers of different parities. If so, the answer is 1, otherwise, the answer is  - 1.

353B - Two Heaps

Let's say for shortness, that we put numbers, that are painted on cubes, in piles, instead of cubes themselves.

Note, that the answer is the product of c₁... c₂, where c_i is the number of different numbers in the i-th pile. Let's consider that all numbers are different. In this case the answer is n². Now, let's suppose that we have two equal numbers and all the other are different. Then, if we put them in different piles, the answer will be n², but if we put them in one — n·(n - 1). Obviously, the first case give greater product.

Thinking in similar manner, you can conclude, that we should do the following. Take numbers, that appear more than once, and put one of them in the first pile, one of them in the second pile and the other put aside. After that, divide the numbers, that appears once, in two equal part and put the first part in the first pile and second part in the second pile. Finally, take the numbers, that we put aside, and separate them in two pile in any kind.

353C - Find Maximum

Let's see on the highest bit of m. If it equals to zero, than for any there is a zero on the (n - 1)-th position, so a_n - 1 doesn't affect the answer and we can put it aside and find the answer for smaller number of elements.

If the highest bit of m equals to 1, than a_n - 1 for some x will present in f(x), but for some will not. Let's consider such x, that a{n - 1} will present in f(x) with zero coefficient. It is obvious that . In this case f(x) will have maximum value when x = 2^n - 1 - 1. Try to update the answer by this value.

Now we should analyze the case, when , find the maximum value of f(x) for all such x and try to update the answer by this value. Let's note, that in all such x there is 1 in (n - 1)-th position. Therefore we can find the maximum value of f(y) for all and add a_n - 1 to it.

353D - Queue

Note that if there are some girls in the begining of the line, they will never move. So let's remove them and will consider that the first schoolchildren in the line is a boy. Also note, the relative order of the girls doesn't change. Let's calculate for each girl such moment of time t_i, that after it she won't move forever. Note, that for i-th girl t_i ≥ t_i - 1. Let's calculate t_i in order from left to right. Let's denote y_i is the position in the line where i-th girl will stop, ans x_i is her current position. Therefore it is needed x_i - y_i second for girl to reach her finish position. So if x_i - y_i > t_i - 1, then t_i = x_i - y_i. Let's manage the case when x_i - y_i ≤ t_i. The girl with number (i - 1) will be on y_i-th position by t_i - 1-th second, so t_i ≥ t_i - 1 + 1. Let's consider such moment of time p, when i-th girl stand right after (i - 1)-th, but not on y_i-th position. After that, in (p + 1)-th moment of time (i - 1)-th girl and the boy standing in front of her will swap their positions, but i-th girl will save her position. Then since p + 2-th second till t_i - 1 both girls will change their positions. Finally, at (t_i - 1 + 1) - th second i-th girl will occupy her position. Therefore, t_i = t_i - 1 + 1 in this case.

353E - Antichain

Let's divide our graph on chains. Denote chain as the maximal sequence of the edges, which have the same direction. If there are more than 2 edges in each chain, then the answer is the number of such chains.

If there is a chain containing only one edge (u, v), then brute vertex, which we will take in maximal antichain (also consider the case, when we take none of them). Let's suppose we brute the vertex v. After that we put aside this vertex and all vertices, which is comparable with v. In received graph we can find the size of the maximal antichain by uning dynamic programming with O(n) time complexity. Let's show how to do this.

Write all remaining vertices in line and renumerate them from left to right by the numbers from 1 to k. After that we are going to calculate d_i — the size of the maximal antichain among vertices with numbers j ≥ i. So if i > k, then d_i = 0. In other case we can skip i-th vertex and try to update d_i by the value of d_i + 1. Also we can try to take i-th vertex to the answer. In this case we should skip all vertices, that are reachable from i-th, or the vertices, from which we can reach i-th, take the answer from the next vertex, add 1 to it and try to update the answer.