maroonrk's blog

AtCoder Regular Contest 110（Sponsored by KAJIMA CORPORATION）Announcement
By maroonrk, history, 4 years ago, In English

We will hold AtCoder Regular Contest 110（Sponsored by KAJIMA CORPORATION）.

The point values will be 300-400-500-600-800-900.

We are looking forward to your participation!

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

Comments Comments (47)
| Write comment?
»
4 years ago, # |
  Vote: I like it +25 Vote: I do not like it

I thought for a second that KOJIMA PRODUCTIONS is sponsoring this round. XD

→ Reply
»
4 years ago, # |
  Vote: I like it +25 Vote: I do not like it

So finally kazama from Shinchan became an Industrialist and sponsoring this . Nice to see his dream come true.

→ Reply
»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

I am desperate to destroy this round ᕙ༼=ݓ益ݓ=༽ᕗ

→ Reply
»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Bump, how do you solve F?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    Hint: Suppose that $$$P$$$ contains $$$1 \ 2 \ ... \ k$$$ as a continuous subsequence. Try to extend it to $$$1 \ 2 \ ... \ k+1$$$.

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

      What about Um_nik's magical solution ?

      https://atcoder.jp/contests/arc110/submissions/18575753

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        I don't remember how to prove it, I just copied it from my 5 years old submission to this problem and fixed a bit because of 0-indexation in this one.

        → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      Unexpected solution: assume doing random operations gets random permutations. There's 1/N probability of the permutation being one big cycle, so keep doing random operations until it's a big cycle then you can solve by using only 0.

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

        Yes, I did something similar, tried to use 0, if not then do some random swap. I was surprised that it passed the tests, maybe reducing the limit on number of operations from $$$2e5$$$ would have helped to avoid such solutions.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +23 Vote: I do not like it

          Actually no, this solution uses way less operations than intended. N <= 1e3 would be possible with this, not sure about much higher.

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

        Can you elaborate on this? What does it mean to "solve by using only 0"?

        I also wasn't sure what you mean by the permutation being one big cycle, since 0 always points to itself.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          operation 0 swaps positions 0 and a[0], so if every position is in the same cycle then we can solve it by repeating N-1 0's.

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

            Oh got it, you’re using a[0] and not the a[i] = 0.

            I took a look at your submission on Atcoder and it seemed like something completely different, so I’m guessing you came up with this idea afterward.

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

          There are $$$(n - 1)!$$$ permutations which consist of exactly one cycle (or, in terms of Stirling numbers of the first kind, $$$s(n, 1) = (n-1)!$$$). Next, there are $$$n!$$$ permutations in total, so for a random permutation there is a $$$1/n$$$ probability of being a one big cycle.

          I was surprised too, because I always knew that there are $$$(n-1)!$$$ ways to pick a cycle, but never heard of this in terms of $$$1/n$$$ probability

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it +10 Vote: I do not like it

            Yep and in fact, in a random permutation the expected number of cycles of length k is $$$\frac1k$$$ for all k. This also immediately shows that the expected number of cycles in total is about $$$\ln n$$$.

            → Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

How to do C ?

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

    First, priority is to get '1' on the first position. So suppose if '1' is at fourth position, we will have to bring '1' to 1st pos by swapping it 3 times. Now also keep an array to remember if you have swaped a certain position Pn and P(n-1) [you can't swap twice]. Now keep doing tis for every index [if indexis 'i' bring the number 'i+1' to that pos by swapping] and store the order of swaps in some array.

    Now, if you came to an indice where the swap has already been done and the value on index isn't equal to (index)+1 , you print "-1" and return bcoz you can't fix that index by swapping.

    Atlast, iterate thru the "visited" array you used, to keep check of what index has been swaped and confirm that each of the indices have been swaped.[We need to swap it EXACTLY one time]. If some index hasnt been swapped, return. Otherwise just print the order array

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

      can you share your code ?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Not very readble code
        → Reply
»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Any idea how to solve D?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    $$$\displaystyle\binom{m+n}{\sum{a_i}+n}$$$

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      I mean how to find this formula, except using generating function?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        How can it be found using generating functions?

        → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +63 Vote: I do not like it

      Why this works: the problem is equivalent to placing $$$\sum{a_i} + n$$$ bars between $$$m - \sum{a_i}$$$ stars, after this we consider the bars number $$$a_1 + 1$$$, $$$a_1 + a_2 + 2$$$, etc $$$a_1 + \ldots + a_n + n$$$ as the real bars, and the other "bars" between them being the chosen objects (there are $$$a_1$$$ of them before the first real bar, $$$a_2$$$ between the first and the second and so on). All stars before the last bar are the unchosen objects from $$$b_i$$$.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        Brilliant, thanks a lot Sir.

        → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 4   Vote: I like it 0 Vote: I do not like it

        I tried to show if $$$\sum b_i-\sum a_i=d, N+\sum a_i=X$$$, then the product of $$$\binom{b_i}{a_i}$$$ over all such $$$b_i$$$ is $$$\binom{X+d-1}{d}$$$

        If I prove $$$\sum\limits_{b_1+b_2=S} \binom{b_1}{a_1} \binom{b_2}{a_2}=\binom{S+1}{a_1+a_2+1}$$$, I can easily win by induction.

        Consider binary strings of length $$$S+1$$$ with $$$a_1+a_2+1$$$ 1's. There are $$$\binom{S+1}{a_1+a_2+1}$$$ of them. Summing over the $$$a_1+1$$$ th 1 gives the other sum.

        Therefore, we are done by the Hockey Stick Identity.

        → Reply
»
4 years ago, # |
  Vote: I like it +28 Vote: I do not like it

E as the hardest problem again? I admit the solution is similar idea-wise to some AGC E, except without some ugly special casing that made that problem much harder.

We can see that each character in the resulting string is formed from a substring. When does a substring $$$I$$$ form 'A'? The key is that in each operation, the number of occurrences of each character switches parity. At the end, we have 'A' once and 'B', 'C' zero times, so in the starting string, the number of occurrences of 'A' must also have a different parity than for 'B', 'C'.

Is this sufficient? We can always perform operations till we end up with a constant string. This can't be all 'B' or all 'C' because they don't satisfy this necessary condition, but it could be an odd number of 'A'. The last operation, however, gave us 'A...A' from w.l.o.g. 'A...ABCA...A'; we can simplify 'CAA' or 'AAC' to 'C' and 'BAA' or 'AAB' to 'B', which gives us at most one 'A' on each side; we know that we're getting an odd number of 'A', so it couldn't be 'ABC' or 'BCA'. Now 'BC' is ok and 'ABCA' can be transformed into 'CCA' and that into 'A'. The condition is sufficient.

If you were reading carefully, you noticed a special case: a constant substring can't be changed. If the initial string is constant, the answer is $$$1$$$. Otherwise, let's look at the string we want as the result. If it's non-constant, even if we perform some operations and end up with some extra 'AA', 'BB' and 'CC', we can always remove substrings 'AA', 'BB' and 'CC'. If it's constant, we look at the last operation and apply the same reasoning as above to see that if we can get 'A...AAA', we can also get 'A...A'.

For each resulting string, we can now associate its characters greedily with consecutive substrings of $$$S$$$. If the shortest prefix from which the first $$$p$$$ characters can be obtained is $$$S_1, \ldots, S_l$$$, then we find the smallest $$$r$$$ such that $$$S_{l+1}, \ldots, S_r$$$ gives the $$$p+1$$$-th character. We wouldn't gain anything by choosing a larger prefix than $$$S_1, \ldots, S_r$$$; this is obvious if we rewrite the condition for "we can create character from substring" to "are these prefix sums different?".

If we reverse that, we get a DP solution: for each prefix of $$$S$$$, find the number of prefixes of the resulting substring that are associated with it. State transitions are "add character" and can be processed in $$$O(1)$$$ with the above mentioned prefix sums. At the end, we can only use strings associated with some prefix if the remaining suffix has the same parities of the number of occurrences of each character, but that's easy to check. $$$O(N)$$$.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can we calculate coefficient of $$$x ^ M$$$ in the below equation ,just curious, if yes then how ?? i thought it for long time but couldn't think anything after reducing to this for D .

$$$(\prod_{i=1}^{N} ( \sum_{j=a_i}^{\infty}\binom{j}{a_i}x^j)) * (\frac{1}{1-x})$$$

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

    The polynomial for ai is actually x^ai / (1 — x)^(ai+1) so you want to calculate the coefficient of x^m in x^(sum of ai) / (1 — x)^(sum of ai + n + 1)

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

      Can you explain how did you get $$$\frac{x^{a_i}}{(1-x)^{a_i+1}}$$$?

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

        sum (N+i choose N) * x^i = 1 / (1 — x)^(N+1) so multiply that by x^ai to get the exponent shift.

        → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

B Can someone help me with this code? I am getting 2 test cases wrong!! Thanks in advance.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B ?

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    for B what i did was convert it into classic question of given a string $$$S$$$ and $$$T$$$ we can append $$$S$$$ total $$$x$$$ times and find the occurences of $$$T$$$ using some linear function as we know the delta or difference we get of $$$ K * S $$$ and $$$ ( K + 1) * S$$$ is constant, where $$$ \vert S \vert \geq \vert T \vert $$$, so to satisfy this condition i appended $$$110$$$ total $$$10^6$$$ times, like $$$110110....$$$ let it be $$$S^\prime$$$

    then i used prefix function on $$$S^\prime$$$ and $$$T$$$, where $$$T$$$ is the pattern we have to find number of occurrences of,let that val be $$$V_1$$$ and then again do same thing for $$$ S^\prime + S^\prime $$$ and $$$T$$$ ,let that val be $$$ V_2$$$,

    So my answer will be $$$V_1 + (V_2 - V_1) * 9999 $$$

    multiplied by $$$9999$$$ because we already chose $$$10^6$$$ so remaining factor will be $$$10^4$$$ as $$$10^4 * 10^6 = 10^{10}$$$

    My submission link

    → Reply
»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

This ARC is missing the "Discuss" link that points here. (So was ARC 109, but it's there now.)

→ Reply
»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Hi, I have alternative (bad) solution for F

(1) Do random operation (2) Announce 0 until 0 comes into P_0 (3) if sorted, done. else, go back to (1)

I think this works with around 1/N probability each iteration and this in contest passed with time around 700ms with python.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    In Question A : for N = 30 -> ans =2329089562801, (2*10^13 ) is Giving AC, And the limit for Ans is N-10^13

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

      Have you tried comparing 2329089562801 and 2*10^13 e.g. in Python?

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

anyone can help me for task D solution? https://atcoder.jp/contests/arc110/tasks/arc110_d

→ Reply
»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

so……no ediorial in English?

→ Reply