We will hold AtCoder Grand Contest 054. This contest counts for GP30 scores.

- Contest URL: https://atcoder.jp/contests/agc054
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20210627T2100&p1=248
- Duration: 150 minutes
- Number of Tasks: 6
- Writer: yosupo, sigma425, maroonrk, wo_
- Tester: satashun, HIR180
- Rated range: 1200 -

The point values will be 300-800-800-1000-1200-1800.

We are looking forward to your participation!

good, Atcoder's new Grand math Contest, I'll like it!

Hey i would like to participate in this contest but i have a doubt whether i would be rated or not if take part in it.I have never took part in Atcoder's any contest till date.

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

It only matters if you are ranked in the top 30 in the contest.

Spending 2 hours to solve and code B , Just to know that the Entire Thought Process Was Wrong . :(

Apparently I managed to guess the formula for E just by looking at small cases...... (after ~100 minutes)

last 40 seconds submit be like

Editorial B

How can we prove that foreach pair x,y there actually exists a permutation that produces that pair? And why corresponds each x,y to exactly one permutation?

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

Update x and y also

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.

Although I had no idea how to solve

DandE, it was real fun thinking about the problems and analyzing testcases on paper!In

Dyou "just" had to place the brackets correctly, the 'o's like you wish and the 'x's inside a bracket. But how to accomplish?In

EI wanted to somehow iterate on all possible numbers on the last position $$$P_N$$$ and look at numbers of 3 Groups (I assume $$$P_1<P_N$$$, the other case is symmetric): $$$L$$$ contains numbers smaller than $$$P_1$$$, $$$R$$$ contains numbers bigger than $$$P_N$$$, and $$$M$$$ contains all numbers between $$$P_1$$$ and $$$P_N$$$ valuewise. Now I want to count all permutations, that are not valid. My assumption was: Iff (if and only if) there exists one element $$$m$$$ of $$$M$$$, such that all elements of $$$L$$$ are to the left of $$$m$$$ and all elements of $$$R$$$ are to the right of $$$m$$$, then the permutation is not valid. I'm not sure though, whether this is correct and how to count this.AlsoPermutationCoder

Thanks for the round!

It seems to me that the formulas in the editorial for E are wrong.

When inserting values from 1 to A-1, I think there are k-2+i options for the number i, not k-1+i. For example, if A=2, k=2, then we have "2 3 4" already, and when inserting number 1 we have only one option: "2 1 3 4". We also have k-2+i options for the i-th big number.

So the sum we need to compute becomes sum((A+k-3)!*(N-A-2)!*(k-1)/(k-2)!). The extra "*(k-1)" made it hard for me to actually find the closed form for this — but I guess there's some technical way to get rid of it?

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

Thanks! I guess the updated version does not give a hint as to where does the closed form identity come from :) Do you have some intuition on why is it the case?

A possible intuition is a discrete analogue of "integration by parts" $$$\int f' g = f g - \int f g'$$$.

Let $$$\Delta$$$ be the difference operator $$$\Delta f(n) = f(n+1) - f(n)$$$ and $$$E$$$ be the operator such that $$$Ef(n) = f(n+1)$$$. Then from $$$\Delta(fg) = (\Delta f) g + (E f) (\Delta g)$$$ it follows that $$$\sum (\Delta f) g = f g - \sum (E f) (\Delta g)$$$.

In our case we can set $$$f(k) = \sum \binom{A+k-1}{k}$$$ and $$$g(k) = k+1$$$ to reduce to a simpler sum.

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).

I was going through Um_nik submission for problem B , can someone explain me in line 111 , the logic of multiplying f[k]*f[n-k].

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.

Why isn't this rated for Ratings lower than 1200... I am new to AtCoder still secured a 1000 rank .. But didn't got any rating increment.. Isn't this illogical? (T_T)

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).

ecnerwala , got it.. My bad Though I am really happy that one of the all time best replied to my comment XD. inspite of the multiple down votes on it. :)

There's an extremely simple $$$O(N)$$$ solution to C that the editorial didn't cover.

Let $$$pos_i$$$ denote the final position of the value $$$i$$$ in the final permutation ($$$0$$$-indexed). It's easy to see that $$$pos_i \leq K + i$$$ in every permutation satisfying the property given.

Now, consider each position in our final permutation in increasing order. 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 isn't hard to show; if $$$pos_i < K + i$$$, then we don't have to move it at all, so we have to place it there in the original permutation, since we care about the minimum number of swaps. Otherwise, if $$$pos_i = K + i$$$, then we can place it anywhere from $$$K + i$$$ to $$$N - 1$$$ in the original permutation since we have to move it to $$$K + i$$$ eventually, so the minimum condition holds.

Getting the answer is simple: loop in increasing order. For each $$$i$$$, if its position in the final permutation is $$$ < K + i$$$ then don't change the answer; otherwise, multiply by $$$N - (K + i)$$$. Here is my code.

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

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)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.

Problem B: Any hint on how to create the dp or references!

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))$$$

Thank You For such a nice explanation and this DP was very new to me.

Could someone please clarify the second-last paragraph of the editorial of C?

Spoiler"Let us solve the original problem. For each $$$v=N,N−1,⋯,1$$$, consider the relative position of $$$v$$$ in $$$P$$$ among the values not less than $$$v$$$. Let $$$y_v$$$ be the number of values in $$$P$$$ that appear earlier than $$$v$$$ and are greater than $$$v$$$. Then, we can see that if $$$y_v<K$$$, the relative position of $$$v$$$ is fixed. On the other hand, if $$$y_v=K$$$, it can be anywhere as long as it is to the right of, or the same as, its eventual position in $$$P′$$$

Thus, the answer is the product of the numbers of candidates for every $$$v$$$"

Here is what I stucked at : I don't think $$$v$$$ can be loosely assumed "to the right of, or the same as, its eventual position in $$$P′$$$", because if some of the values that are larger than $$$v$$$ that appear ealier than $$$v$$$ in the original $$$P$$$ move far right, exceeding the position of $$$v$$$, that permutation won't recover to our original $$$P$$$.

Update: According to vkgainz's comment, such situation won't happen, because if $$$v$$$ is able to move (a.k.a. its inversion count $$$I_v=K$$$), then all the values larger than $$$v$$$ appearing before $$$v$$$ will definitely have inversion count less than $$$K$$$, hence they won't be able to move in the first place.

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.

$$$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.

Idea for proofDirection $$$P \rightarrow I$$$ is by definition. Other direction: We iterate $$$I$$$ from behind and construct $$$P$$$. $$$I_n$$$ can only be $$$0$$$ (since the inversion count of the biggest number $$$n$$$ can only be $$$0$$$). $$$I_{n-1}$$$ can only be $$$0$$$ or $$$1$$$, depending on that we place $$$n-1$$$ to the left or the right of $$$n$$$. On each of the following steps there is a unique position where to place $$$i$$$ such that it corresponds to $$$I_i$$$, the inversion counts of already placed numbers is not affected by this.

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.

Ah! it finally makes senses if we look and tweak from the perspective of the bijection from permutation to inversion array. Thank you so much!

I have an intuition proof for why if there exists $$$I_i > K$$$, there always exists $$$j$$$ such that $$$I_j > K$$$ and $$$P_j < P_{j-1}$$$.

SpoilerLet's pick any index $$$x$$$ that $$$I_x > K$$$.

If $$$P_x < P_{x-1}$$$, then we found it.

If $$$P_x > P_{x-1}$$$, that would mean $$$I_{x-1} > K$$$ too (because there are more than $$$K$$$ numbers that are larger than $$$P_x$$$ appearing before $$$P_x$$$, and $$$P_{x-1}$$$ isn't one of them and $$$P_{x-1}$$$ is smaller than $$$P_x$$$, then there must be more than $$$K$$$ numbers that before $$$P_{x-1}$$$). Then, we will continue consider $$$x-1$$$ instead.

If $$$P_{x-1}$$$ is sill larger than $$$P_{x-2}$$$, then that would mean $$$I_{x-2} > K$$$. We then will consider $$$x-2$$$ instead, and so on.

We will repeat the process and we will eventually arrive the desired index.

Oh, indeed, you can easily formalise this with extremal principle. There exist finite $$$x$$$ with $$$I_x>K$$$, so there also exists a minimum $$$x$$$ with $$$I_x>K$$$. Assume $$$P_x>P_{x-1}$$$. Then $$$I_{x-1}=I_{x}>K$$$. Contradiction to extremal $$$x$$$. This implies $$$P_x<P_{x-1}$$$.