H: You are to check whether all cycle lengths in SCC divisible by some p > 1. It can be done by dfs similar to bipartite graph checking (assign every node i value x_i and solve system of equations: for every edge (a, b): ). So if no such p exists the answer is YES.

P.S. You don't have to check all p, only the prime divisors of any cycle length.

F: Let dp[L][R] be the answer for the subarray [L, R).

Which element can be the biggest in the subarray [L, R)? If the biggest element is the x-th one, x must satisfy x - r[x] ≥ L[x], x + 1 + r[x] ≤ R, and in at least one of the two inequalities, the equality must hold.

Thus, , where x moves over all possible xs. It turns out that there are O(N²) such triplets (L, R, x), so it works in O(N²).

F: let's find position of the maximum element. Its "circle" hits one of the borders and only leftmost position that hits right border with its circle and rightmost that hits left border could be the maximum. Maximum is not covered by any circle other thant its, so we reduce to two separate subproblems. How to implement: subsegment dp, for segment [l, r] you need to count number of correct ways to assign numbers from 1 to r - l + 1 modulo 10⁹ + 7 and whether there is a correct way at all. After that iterate over two possible positions of maximum on segment. Iterate over two possible maximum positions (notice that they are chosen that way that reduction to two separate subproblems happens anyway), now you want to distribute r - l numbers to two groups of sizes k ≤ r - l and r - l - k and this is just product of two dp values of smaller segments and binomial coefficient.

I can't say for easiest, but this one did not require us 2,5 hours. Let's solve for connected components separately. If there is even number of edges in connected component, then we can match them all by dfs: for every vertex match its not yet unmatched son edges between themselves and possibly edge to parent, if this can't be done, edge to parent remains unmatched and we return it higher, to match it later This way all pairs are matched, because there can be only problem with root (root will have odd number of unmatched son edges), but this is not possible, because total amount of edges is even.

How approach hard case (component has odd number of edges)? We could delete edge with smallest weight but we can get two components with odd number of edges again after this operations (edge was a bridge). Now, it is never ok to delete  ≥ 2 edges from the component, because all of them are bridges (otherwise we could delete only one of them and not ruin connectivity), this bridges separate our graph in some components after deletion (they are not necessarily biconnected, but there is still a structure of tree on them), so there is one of this component that is adjacent to  ≥ 2 bridges, so we could instead create a perfect edge matching in this component (even number of edges) + this two bridges, so solution is not optimal.

Now we need to find such edge of minimum weight that it is not a bridge that separates our connected component into two components with odd number of edges and delete it (this completes reduction to easy case). It requires just finding bridges and sizes of subtrees in dfs that calculates bridges. precalculating bridges and

Let's look: f(1)=1, f(2)=2+1, f(3)=3+1+1, f(4)=4+2+1+1, f(5)=5+f(2)+f(2)=5+2+2+1+1

But optimal sequence for n=5 is 5+2+1+1+1

All possible partitionings for n=5 is 5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1

Sequence 5+2+1+1+1 is cover all of them and it's sum is less.

What is wrong?

P.S. I found http://oeis.org/A006218

Area covered by overlapped partitions of n, i.e., sum of maximum values of the k-th part of a partition of n into k parts.

I was wondering how you came up with this recurrence? Just observation from brute force code?

It took me some time, but I finally solved it: http://mirror.codeforces.com/blog/entry/50844.

Compute maxflow twice.

1. Sources = {W_s, O_s}, Sinks = {W_t, O_t}. Suppose that the maxflow is ans₁ in this case and the amount of the flow on the edge e is f₁(e).
2. Sources = {W_s, O_t}, Sinks = {W_t, O_s}. Suppose that the maxflow is ans₂ in this case and the amount of the flow on the edge e is f₂(e).

The answer is min(ans₁, ans₂). This can be achieved by water(e) = (f₁(e) + f₂(e)) / 2, oil(e) = (f₁(e) - f₂(e)) / 2.

Denote . Let's state our problem in such way: we have n linear functions and want to find some subset of them and some ordering of that subset (i₁, i₂, ..., i_k) that g_ik(g_ik - 1(... g_i1(x)... ) is as big as possible. It is equivalent, because using f_i from original problem is equivalent either to using g_i or not using it and choosing best of this options. Now, we will just sort all linear functions by something and whether function actually does something or should be ignored won't bother us.

Now, let's look at optimal order of linear functions that we will actually use. It should satisfy such condition that we can't increase answer by swapping adjacent functions, so if the are two adjacent functions g_i, g_j (g_i before g_j), then , so (a_j - 1)b_i ≥ (a_i - 1)b_j.

Now let's consider three cases: a_i < 1, a_i = 1, a_i > 1. In first case our comparator is equivalent to , so it satisfies all qualities of good comparator (transitive and incomparablness is an equivalence relation), because it can be reduced to comparing fractions. In second case it is also ok, because it just checks whether 0 ≥ 0. Third case is similar to first one, only it is equivalent to .

Now, let's think about order of functions of this three types (in each group we will just sort them by comparator). If we look at (ax + b) - x = (a - 1)x + b (our "profit" from applying the function) then we can see that for functions with a < 1 it decreases when x increases, for a = 1 it doesn't depend on x, and for a > 1 it increases when x increases. So, because x is non-decreasing in our process, we first should apply all functions with a < 1, then all functions with a = 1, then all with a > 1. To find order in each group we can use our comparator, which is completely ok, as long we are only comparing functions from one group.

Summary of solution: first use functions with a_i < 1 in order of comparator, then with a_i = 1, then with a_i > 1 in order of comparator.

P.S. Better to use __int128 to compare fractions, but I believe that accurately written comparasion is also ok (where B = 10⁹ — bound on numbers in input).

Optimal positions are known. Since loss function is linear on segment they are x and y projections of stations onto line. The problem is to choose optimal k of them.

opencup.ru

Can you please share your solution to the timus problem?

Greedy. First you go from left to right. If you get ( push the "removal cost" into a max-heap. If you get ), try to select an opening bracket from the heap. Which one? Of course the one with higher removal cost. What if there is no ( in the heap? Then this is extra ), so omit this ).

However, this is almost correct. It fails for: ()) with cost: 1 1 100. In this way you are selecting the last ) to omit, but it might be better to omit the middle one and keep the last one. But it works fine with (s.

How to fix it? Easy, keep another heap for )s. Whenever you match ) with some (, push the cost of ) into the heap. Now when you get ) but there is no ( remaining in ('s heap, that means this ) is extra. Now look at the )'s heap. You can replace any of the previous ) with current ). Which one should you replace? Of course the one with lowest removal cost. So check if the lowest removal cost of a ) in the heap is even lower than your current )? If so, pop out the previous ), and push the current ) with higher removal cost. So I guess you can understand that )'s heap will be a min heap. And you can easily compute the total cost while processing all these heaps.

May be: http://www.cs.technion.ac.il/~itai/publications/Algorithms/2CF.pdf ?