Both.

No.

Codeforces Gyms
Find our contest (it's on the top now), register and solve the problems.

Remember that it's already running and you will have less time. After finish you can participate in virtual mode.

For B: calculated number of occurrences n_i of each character, probability to pick each letter is n_i/n, where n is total length of the string, and we'll see it n_i times. Expected value is sum of such probabilities.

B — ans = sum(count(c) * count(c)) / |s|, where count(c) means each char, how many times it appears in s. K — you are going to construct an array which has the inversion number equals to k, you can do it greedily.

For K, I start with the decreasing order which has the inversion equal to n * (n-1) / 2, and try to reduce it to k. For example, if the order is 5, 4, 3, 2, 1. We can reduce it by 4 by moving 5 to the end (4, 3, 2, 1, 5), then reduce it by 3 by moving 4 to the position next to 1 (3, 2, 1, 4, 5). The total number of inversion we can reduce is (n-1) + (n-2) + ... (n-m) where m is the number of time we reduce. We try to keep this sum greater than (n * (n-1) / 2)-k. Thus, for the last round of reducing, we will know the position that we need to move the number in the front to.

Here is my code 3643676

You can solve these problems in practice mode. Enter the gym (link) and enjoy.

If you're stuck on some problems, ask here, someone will help you for sure.

In Codeforces Gyms, the tests aren't shown in practice mode.

Address this question to MikeMirzayanov)

First of all, if you have WA 8, make sure that you don't output inversed permutation.

My solution:

1. We can easily check if the answer exists, using sweep line approach: make events "beginning of the segment", "point" and "end of the segment" and sort them. If we process the beginning of the segment, add pair (its end, its index) to the set. If we process point, take the minimal pair from the set (it's obvious that better to match point with the earliest closing segment). If the set is empty at this moment, matching does not exist.

2. Now check if the answer is not unique. Answer is not unique if for some points p1, p2 (p1.x <= p2.x) exist two segments s1, s2 such that max(s1.beginX, s2.beginX) <= p1.x, p2.x <= min(s1.endX, s2.endX), and they match each other in some full matching.

3. Consider that we are processing point p2 and it matches with segment s2. When the situation above can take place? There should exist some point p1 (p1 is earlier in the sorted array) such that s2.beginX <= p1.x. Also the end of the segment s1, which matches with point p1 (p1 was already processed since it is earlier in the points array) should be greater or equal than coordinate of point p2: p2.x <= s1.endX. How to check it? Let's create a segment tree which can do operations getMax(L,R) and set(index,value).

4. How does this segment tree work? For every point we will store the end of the segment which matches with this point. Ok, our sweep line is now processing point p2 and it matches with segment s2. What can point p1 be? Its coordinate should be greater or equal than s2.beginX — find the index of such point with binary search (let it be leftIndex). Then consider all points in the subarray [leftIndex, i-1] (where i is the index of the point p2, after all points are sorted). Make query on this segment and we will find the rightest end of the segment s1 which matches with such point p1 that can be also matched with segment s2. Now, if p2.x <= s1.endX, the answer is multiple. And update the segment tree using set(i, s2.endX).

In fact, we copypasted this problem from Timus. But our problem has much higher contraints :)

I've found very elegant O(N) DP for checking uniqueness of the answer after some simple O(N * log N) preprocessing.

At first I sort segments by their right ends and maintain points in the set. For i-th segment I choose the least available point on it and delete it from the set (if it exists). Denote it as best[i]. Then for future needs I also save the next least available point to next[i] (if it exists).

The matching exists if and only if best[i] exists for each i and we can find the answer easily by array best[].

Denote as segm[i] the segment that matches with i-th point. So segm[best[i]] = i.

Now how we can check uniqueness. The found matching is lexicographically smallest in some sense. Let's seek for the lexicographically next matching. For this we should try to replace best[i] by next[i] for each segment i in order N, ..., 1, since next[i] is the next best choice for the i-th segment. When we do such a replacement, the segment j = segm[next[i]] looses his point and we should either replace it by best[i] if possible, or otherwise take next[j]. In the latter case we should proceed to segm[next[j]] and so on. The replacement is possible once at some step we reach the segment that contains point best[i] and in this case we perform some cyclic shift of the subsequence of our matching.

But we don't need to do this walk each time. Instead we can check each segment by clever DP in O(1) time. Namely, let dp[i] be the smallest left end of the segments in the walk i, f(i), f(f(i)), ..., where f(i) = segm[next[i]]. Then second matching via i-th segment is possible if and only if dp[f(i)] <= leftEnd[i] dp[f(i)] <= x[best[[i]]. Calculating of dp[i] is simple: if next[i] does not exist than dp[i] = leftEnd[i], otherwise dp[i] = min(leftEnd[i], dp[j]), where j = segm[next[i]].

will a contest with four stars be as hard as CF div1 ?

Build all derivatives starting from derivatives of higher orders.

Example.

Let b = [1,0,0,1,1]

4-th derivative has length 1. Any array of length 1 is both increasing and decreasing. But we have restriction for 3-rd derivative: it should be increasing also. This means elements of 4-th derivative should be positive.

a[4] = [1]

3-rd derivative has length 2. We already have built 4-th derivative, so we know that a[3][1]-a[3][0] = 1. 2-nd derivative should be decreasing => elements of 3-rd derivative should be negative.

a[3] = [-2,-1]

With similar reasoning we get:

a[2] = [-1,-3,-4]
a[1] = [9,8,5,1]
a[0] = [1,10,18,23,24]

At every step we should keep absolute values of derivatives minimal possible to satisfy restrictions on elements of resulting array — they must be in range [-10^9..10^9].

Your checking of the existence of the answer is correct. I think you have a bug in the next part of the solution.

A hint for the second part: you can set the monochrome for each image immediately after the sorting.