Problem A (div2):
It is obvious that we need to make sequence of moves like: 1, 2, 1, 2, ...
So the answer is 2 * n / 3. After that we have either 0, 1 or 2 stones left. If we have 0, we are done, otherwise we have 1 or 2 left, so we only can give 1 more stone.
Final formula is: (2 * n) / 3 + (n % 3 != 0 ? 1 : 0);
Problem B (div2):
We can just emulate grasshopper behavior and save all positions it visits. It is obvious that we will have no more than O(n) different positions. If grasshopper appears in the same position twice that means that there is a loop and the answer is INFINITE. Otherwise the answer is FINITE.
Problem A(div1)/C(div2):
Let's have 2 matrices: a, idx. In a we will have NULL for cell if we don't know the value or the value. idx will be initialized with idx[i][j] = {i, j}; Then we need to emulate the process on matrix idx. If we have 3rd query we can set up the value in matrix a, because we know the original position of that cell keeping idx.
Problem B(div1)/D(div2):
The key in this problem is that order of all elements in odd positions and in even positions is the same. Let's say we have 2 arrays: [1, 3, 5, ...] and [2, 4, ...] (odd positions and even positions). Now if we call 2nd commands we just swap these 2 arrays, but order is the same. Obviously 1st command also keeps the order. By order I mean cyclic order (right neighbor is the same in cycle position).
Let's just keep the position of 1st boy and 2nd boy. Now if we apply 1st operation we move it by X or -X. Second type of the query just swaps the positions. In the end we can construct the answer if we know positions of 1st and 2nd boys.
Problem C(div1):
First, let's solve inverse problem: find minimum (maximum) of two distributions. Let's use the following formulas:
P(a = k) = P(a <= k) — P(a <= k-1) P(max(a, b) <= k) = P(a <= k) * P(b <= k)
For minimum:
P(min(a, b) >= k) = P(a >= k) * P(b >= k) = (1 — P(a <= k-1)) *(1 — P(b <= k-1))
Now in our original problem minimum and maximum defines system of square equations for each pair P(a <= k), P(b <= k).
Solving these equations we get P(a<=k), P(b<=k) = (u + v ± sqrt((u + v)^2 — 4u)) / 2, where u = P(max(a,b) <= k), v = P(min(a,b) <= k). Now we can notice that if there exists an answer, then there exists an answer when we chose the signs for each pair equally (check out this comment)
Problem D(div1)/E(div2):
There are many ways to solve this problem. One of the ways was SQRT-decomposition. First let's compress all times. Now for each block in the decomposition we will store for each element the balance in that block. So to answer the query we need to calculate sum of balances from first block to the block before the one where our element is located and then just process all requests in the current block.
Another way was to use data structure from std library, described here. For each element we have two trees: remove times and add times. Then by getting order of the time in remove and add tree we can calculate the answer.
Problem E(div1):
Let's build for both 2-SAT formulas implication graph and let's find strong connected components in this graph. If both of the formulas are not satisfiable then the answer is SIMILAR. If only one formula is not satisfiable then we can find an answer for the second one and output it.
Now, let's assume both formulas are satisfiable. Let's have a transitive closure for both of the graphs. Let's call the variable X fixed in the formula F if there is a path -> x or (x -> ). If there is a fixed variable in one formula, but not fixed in the other (or fixed but has other value) we can find the solution for that second formula with opposite value of that fixed variable — that will be an answer. If we could not find these variables, we can remove all of them. There is no fixed variables in the rest of them. Let's find an edge u->v, presented in one graph, but not presented in the other. Let's find the solution for formula without the edge with u = 1 and v = 0 (we always can find it). That is the answer.
Problem F(div1):
Let's define k-clique B the descendant of k-clique A, if B could be produced from A with the sequence of the following steps: add vertex to the clique, connected with all clique vertices in the graph description and remove exactly one other vertex. Let's calculate the DP with states (k-clique, separation its vertices to the components) — number of spanning forests int the graph, induced by the clique and all its descendants so that clique will be divided to different connected components according to the defined vertices separation (all of the rest vertices will be connected with some of these components). To calculate that we need to precalculate all separations from k to k+1 elements and transitions:
1) (separation of k+1 vertices) x (separation k+1 vertices) -> (separation k+1 vertices | null), transform pair of separations — forests to the set of connected components of their union or null if there appears a cycle.
2) (separation of k+1 vertices) x (vertex) -> (separation of k+1 vertices | null), transform forest to the new forest, generated by adding new edge from vertex to vertex k+1 (or null, if there appears a cycle)
3) (separation of k+1 vertices) -> (separation of k vertices | null), projecting the separation on the first k vertices (or null, if k+1-th vertex creates a separate component)
Check out details in the author solution.
