### maroonrk's blog

By maroonrk, history, 7 months ago,

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

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

We are looking forward to your participation!

• +256

 » 7 months ago, # |   -72 good, Atcoder's new Grand math Contest, I'll like it!
 » 7 months ago, # |   -35 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.
•  » » 7 months ago, # ^ |   +5 You won't be rated.Minimum rating for being rated in AGC is 1200
•  » » 7 months ago, # ^ |   -30 I received "This contest counts for GP30 scores" in my email notification which i don't understand. Please help
•  » » » 7 months ago, # ^ |   +54 It only matters if you are ranked in the top 30 in the contest.
 » 7 months ago, # |   +28 Spending 2 hours to solve and code B , Just to know that the Entire Thought Process Was Wrong . :(
 » 7 months ago, # |   +73 Apparently I managed to guess the formula for E just by looking at small cases...... (after ~100 minutes)
 » 7 months ago, # |   +57 last 40 seconds submit be like int i = n-1; while(i>=0 && cur[i] < K) ++i; 
 » 7 months ago, # |   +6 Editorial BHow 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?
•  » » 7 months ago, # ^ |   +19 You can recover the permutation one by one starting from the last element. (just compare the prefix sums)
•  » » 7 months ago, # ^ |   +36 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
•  » » » 7 months ago, # ^ |   +20 Update x and y also
•  » » 7 months ago, # ^ |   +8 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.
 » 7 months ago, # | ← Rev. 2 →   +13 Although I had no idea how to solve D and E, it was real fun thinking about the problems and analyzing testcases on paper! In D you "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 E I 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  » 7 months ago, # | +49 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? •  » » 7 months ago, # ^ | +39 Ooops, I once made a fix but it seems like I accidently reverted to the old version. I'll update it soon. •  » » » 7 months ago, # ^ | 0 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? •  » » » » 7 months ago, # ^ | +32 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. •  » » 7 months ago, # ^ | ← Rev. 2 → +16 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).  » 7 months ago, # | -7 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]. •  » » 7 months ago, # ^ | +11 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. •  » » 7 months ago, # ^ | +7 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.  » 7 months ago, # | ← Rev. 4 → -12 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) •  » » 7 months ago, # ^ | +81 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). •  » » » 7 months ago, # ^ | ← Rev. 2 → +10 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. :)  » 7 months ago, # | +51 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. •  » » 7 months ago, # ^ | +14 The implementation code is indeed simpler, but I think the solution explanation is wrong. I claim that if$pos_i 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 thisFact: $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.
 » 7 months ago, # |   0 Problem B: Any hint on how to create the dp or references!
•  » » 7 months ago, # ^ | ← Rev. 4 →   +19 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))$
•  » » » 7 months ago, # ^ |   +5 Thank You For such a nice explanation and this DP was very new to me.
 » 7 months ago, # | ← Rev. 4 →   +10 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 •  » » 7 months ago, # ^ | ← Rev. 10 → +14 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. 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. •  » » » 7 months ago, # ^ | ← Rev. 11 → +10 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. •  » » » » 7 months ago, # ^ | +13 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
 » 7 weeks ago, # | ← Rev. 3 →   0 My explanation for condition of E, without induction SpoilerLet $a_1a_n$.We want to remove all element in $(a_1,a_n)$ . Suppose $x$ is operated at last. The sequence is divided into two parts. If $xa_n$, remove the right. Repeat the operation until the process ends. In the end, in all $x$ chosen, we can always find two indices x and y, satisfying \$a_x<=a_1,a_y>=a_n,x