You won't be rated.Minimum rating for being rated in AGC is 1200

I received "This contest counts for GP30 scores" in my email notification which i don't understand. Please help

You can recover the permutation one by one starting from the last element. (just compare the prefix sums)

Generate the permutation. Let current score of T and A be x and y Initially x=0 and y=0 If x<=y then put pop x1 and put it in permutation If x>y pop y1 and put it in permutation

You can construct it. Write both permutations down. We now use those to construct the full permutation. If Takahashis weight is not bigger then Aokis, we take an orange from his permutation. Else we take one from Aokis.

Ooops, I once made a fix but it seems like I accidently reverted to the old version. I'll update it soon.

In this case, I think you can write it as $$$(A + k - 3)! * (k-1) = (A+k-2)! - (A-1)(A+k-3)!$$$.

Alternatively, I had some slightly different formulas, but I dealt with this term using a combinatorial interpretation of "choosing one special element among the $$$k$$$"; then, we can choose this element first and then choose the rest (for any count).

Once you fix the two subsets, then you can permute the elements within the two subsets to fix the order in them separately. Then, there will be a unique way to combine them into a single array such that this condition holds.

Let X = T(Takahashi's Score) — A(Aoki's score)

Initially, X = 0 The process is such that, at the first step, some w[i] will be added to X, then for the next few steps 2,3,4... etc some w[i]'s shall be subtracted and finally the sum becomes 0, at the last step.

So, there are some k elements which are added to X, and some n — k elements which are subtracted from X, so that X remains 0 finally, after the process.

Let us say we have already chosen these elements: We have some k elements if the W array, whose sum is exactly equal to the remaining n — k elements.

The k elements will give positive contribution to X, and n — k will give negative contribution.

Once the elements are chosen, at the first step, the element kept shall be one of the k elements (as first step is a positive contribution.

Then, the next element must be from the other group (with n — k elements), it can be chosen in (n — k) ways, if the sum is still > 0, then again some element will be chosen from the 2nd (negative contribution group) group, this time with (n — k — 1) possibilities... next maybe (n — k — 2) possibilities and so on, until X becomes < 0, now out of the (k-1) elements of the first group, some will be chosen (of course in k-1 ways..)

Basically, the above should kind of show that once k elements with "positive role" and n — k with "negative role" are chosen, then we can take them individually in any order. I mean the elements of a particular group can be permuted with each other. So, (n — k)! * k! ways are there.

I think the fear is these problems are typically too hard to properly distinguish between low-rated people, because there are so many low scores (or 0's), so the rating would fluctuate too much. It does suck if you're new, but there are lots of ABCs and ARCs that would be rated, so just do some of those (they're way more frequent than AGCs, and possibly a better difficulty fit anyways).

The implementation code is indeed simpler, but I think the solution explanation is wrong.

I claim that if $$$pos_i<K+i$$$, then the only position it can appear in the original permutation is $$$pos_i$$$; otherwise, if $$$pos_i=K+i$$$, it can appear anywhere from $$$K+i$$$ to $$$N−1$$$ inclusive.

This is not true. Consider the final permutation (0-indexed, as in your comment) 4 2 0 1 3, with $$$K=2$$$. The only values $$$i$$$ where $$$pos_i=K+i$$$ are $$$0$$$ and $$$1$$$, but in the following possible initial permutation (with minimum number of swaps to reach the final permutation shown)

4 2 1 3 0   ->   4 2 1 0 3   ->   4 2 0 1 3

we have $$$pos_3=3$$$ (which is not $$$4$$$ like in the final permutation) and $$$pos_1=2$$$ (which is not in the range $$$[K+i, N-1] = [3, 4]$$$). Moreover, the positions where you claim value $$$i$$$ may be in the original permutation ("anywhere from $$$K+i$$$ to $$$N−1$$$ inclusive") are not independent between differents $$$i$$$'s and so cannot just simply be multiplied.

Let $$$I_i$$$ denote the number of values to the left of $$$i$$$ (i.e. position less than $$$pos_i$$$) that are greater than $$$i$$$ in the final permutation. The extra insight that extends the editorial to your linear solution is this

Fact: $$$I_i < K \iff pos_i < K + i \;$$$ (which is equivalent to $$$I_i = K \iff pos_i = K + i \;$$$, since $$$I_i \le K$$$ and, as you stated, $$$pos_i \le K + i$$$)

($$$\implies$$$) Suppose $$$I_i < K$$$, so there are less than $$$K$$$ values greater than $$$i$$$ to the left of $$$i$$$ and there are at most $$$i$$$ values (all available, 0-indexed) less than $$$i$$$ to the left of $$$i$$$, then $$$pos_i < K + i$$$.

($$$\impliedby$$$) Suppose $$$I_i = K$$$, so there are $$$K$$$ values greater than $$$i$$$ to the left of $$$i$$$. If there were some value $$$j$$$, $$$j < i$$$ to the right of $$$i$$$ then, we would have $$$I_j \ge K + 1 > K$$$, wich is a contradiction. Then, all values less than $$$i$$$ are to the left of $$$i$$$ and $$$pos_i = K + i$$$.

Moreover, when $$$pos_i = K + i$$$, all values to the right of $$$i$$$ are greater than $$$i$$$ in the final permutation. So, the number of possible relative positions for $$$i$$$ among the values not less than $$$i$$$ (like in the editorial) is $$$N - (K + i)$$$ in the original permutation. Then you can multiply those numbers for the $$$O(N)$$$ solution.

Let's try starting from the easier question: You are given $$$N$$$ objects, where the weight of each objects are $$$[w_1,w_2,...,w_n]$$$. How many ways to divide these objects into two groups such that both group have the same total weight?

Let's define our dynamic programming as follow: $$$dp_{i,j}$$$ = the number of ways of dividing objects $$$[1...i]$$$ into two groups such that the sum of weights of the first group subtracted by the sum of weights of the second group is $$$j$$$. ($$$j$$$ can be negative)

The recurrence will be $$$dp_{i,j} = dp_{i-1,j-w_i}+dp_{i-1,j+w_i}$$$ (we try both ways: adding $$$i$$$-th object to the first group, adding the $$$i$$$-th object to the second group, respectvely.)

Our answer will be at $$$dp_{n,0}$$$ = the number of ways of dividing all objects into two groups such that the sum of weights of the first group subtracted by the sum of weights of the second group is 0 (a.k.a. both group has the same weight).

The time complexity will be $$$\mathcal{O}(N \cdot sum(w_i))$$$

What helped me to solve this question is this theorem:

We have a permutation $$$P$$$ of $$$ 1,2,...,n $$$. We are given $$$I$$$, with $$$I_i$$$ being the inversion count of the value $$$i$$$. E.g.

P: 5 2 3 1 4
I: 3 1 1 1 0

$$$I_1=3$$$ because there are $$$3$$$ numbers bigger than $$$1$$$ to the left of $$$P_4=1$$$.

One can prove, there exists a bijection between corresponding $$$P$$$'s and $$$I$$$'s.

Back to the task. This is no proof, but my gut feeling: Assume we have some $$$P$$$ with $$$I$$$. Some values of $$$I$$$ are bigger than $$$K$$$. Each step that Takahashi makes decreases exactly one $$$I_i>K$$$ by one (this needs a prove, I don't have one yet. this is just my theory). The complete set of his operations transforms each $$$I_i \rightarrow min(I_i, K)$$$. This way we can show, that each of the described combinations which are mentioned in the editorial really leads to Takahashis permutation.