maroonrk's blog

By maroonrk, history, 3 years ago, In English

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!

  • Vote: I like it
  • +256
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it -72 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it -35 Vote: I do not 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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it -30 Vote: I do not like it

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

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +54 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +28 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +73 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +57 Vote: I do not like it

last 40 seconds submit be like

int i = n-1;
while(i>=0 && cur[i] < K) ++i;
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +36 Vote: I do not like it

    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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

»
3 years ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

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

Also
»
3 years ago, # |
  Vote: I like it +49 Vote: I do not like it

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?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +39 Vote: I do not like it

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

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +32 Vote: I do not like it

        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.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +16 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it -7 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    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.

»
3 years ago, # |
Rev. 4   Vote: I like it -12 Vote: I do not like it

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)

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +81 Vote: I do not like it

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

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it +10 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +51 Vote: I do not like 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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
    Rev. 4   Vote: I like it +19 Vote: I do not like it

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

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

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

»
3 years ago, # |
Rev. 4   Vote: I like it +10 Vote: I do not like it

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

Spoiler

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.

  • »
    »
    3 years ago, # ^ |
    Rev. 10   Vote: I like it +14 Vote: I do not like it

    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 proof

    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.

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 11   Vote: I like it +10 Vote: I do not like it

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

      Spoiler
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

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

»
2 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

My explanation for condition of E, without induction

Spoiler