maroonrk's blog

AtCoder Regular Contest 129 Announcement
By maroonrk, history, 3 years ago, In English

We will hold AtCoder Regular Contest 129.

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

We are looking forward to your participation!

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

Comments Comments (24)
| Write comment?
»
3 years ago, # |
  Vote: I like it +40 Vote: I do not like it

AtCoder deserves a bump of this post.

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

Fun fact: when I was purple, I proposed a "bad" version of D on codeforces and it was rejected.

Screenshot
→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +36 Vote: I do not like it

I found an even more constructive solution for Problem C than the editorial.

We can use that every number can be written as the sum of three triangular numbers. Triangular numbers are numbers of form $$$n\cdot (n+1) / 2$$$. Then we can construct a number in the form of $$$\Delta_1 X_1 \Delta_2 X_2 \Delta_3$$$ with $$$\Delta_i$$$ being as many $$$7$$$s as the $$$i$$$-th triangular numbers order. But what do we write for the delimiters $$$X_1$$$ and $$$X_2$$$? Using the $$$-2,-3,-1,2,3,1$$$-divisibility rule for seven we can find the difference in positions of $$$X_1$$$ and $$$X_2$$$. If it is three, we take $$$X_1=1$$$, $$$X_2=2$$$. Else we take $$$X_1=1$$$, $$$X_2=1$$$.

So my answers will always be in the form of $$$77...77177...77177..77$$$ or $$$77...77177...77277..77$$$. See also https://atcoder.jp/contests/arc129/submissions/27432100 .

The three triangular numbers can be found easily in $$$O(n^{3/2})$$$ by iterating all three triangular numbers. This can be improved to $$$O(n)$$$ if we only iterate the first 2 triangular numbers and then calculate the third.

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

    I also solved C by this way. Actually, I thought it was intended solution during contest XD

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

    I also came up with the same solution, But my solution involved up to $$$6$$$ triangular numbers at max. But I couldn't figure out what should be an optimal choice of $$$X_i$$$ between each segment of $$$7$$$. Since the maximum length of the answer using these triangular numbers is of the order of $$$O(n^{1/2})$$$, so after every segment of $$$7s$$$, I found the optimal digit using brute force. I wasn't completely sure, whether this is absolutely correct. But this passed all the test cases. :)

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

      oh that's smart I should have done that lmao x)))

      I actually thought I could only use the two same separators and bruteforced for them but it didn't work

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

      You can make these digits equal to $$$10^{-k}$$$ mod 7, where $$$k$$$ it's position from the right. Then in any sub-number all of these digits multiplied by the appropriate degree of 10 will have the same reminder mod 7, meaning you need at least 7 of them.

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

    Why can't we use the same delimeter each time ? I am unable to find a case where it don't work.

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

      e.g. $$$717717$$$ for $$$N=5$$$

      $$$1771$$$ is divisible by $$$7$$$.

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

        Hey, I have commented my solution above. Can you please tell me why this works? OR can you help me come up with a counter case. Thanks a lot for your effort.

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

          As mentioned in my first post, this works because of the $$$−2,−3,−1,2,3,1$$$-divisibility rule for seven. See also on Wikipedia the seventh rule mentioned for seven. I guess the first mentioned rule for seven also explains this.

          Call the $$$−2,−3,−1,2,3,1$$$ sequence $$$D_i$$$. Let delimiter $$$X_i$$$ have position $$$P_i$$$. You need ($$$D_{P_1 \bmod 6} \cdot X_1 + D_{P_2 \bmod 6} \cdot X_2) \bmod 7 \neq 0$$$ (for every rotation of $$$D_i$$$).

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

        This can be easily avoided by changing it to 717177 for N=5.

        Actually, let the length of 2nd part of 7's be k, then as long as (k+1 mod 6) != 3, we can always use '1' as the same delimeter.

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

          Then take $$$77177177$$$ for $$$N=9$$$ as counter example.

          See also in my first comment, which is exactly your statement: "we can find the difference in positions of $$$X_1$$$ and $$$X_2$$$. If it is three, we take $$$X_1=1$$$, $$$X_2=2$$$. Else we take $$$X_1=1$$$, $$$X_2=1$$$."

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

            For N=9, don't use all three length 2 as 7's. Instead, use 777177.

            We can always find a length that satisfy (k+1 mod 6)!=3 to combine with other length. Then use it as the 2nd part of 7's.

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

              Do you have a proof for your statement "We can always find a length that satisfy $$$(k+1 \mod 6) \neq 3$$$"? That would be interesting to see.

              At least for some small values this statement holds true with much leeway.

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

Here is some funny overkill solution for problem A using digit DP (Submission link)

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

    Well, I did digit DP too... Took me an whole hour doing this, since I never before have done digit-DP... I somehow just don't like that topic. Solving B afterwards in 7 minutes left me flabberghasted.

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

      Same (I spent more time for A than for B, C, D).

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

Hi maroonrk, In the editorial page, instead of posting the whole solution, could you start with tags, then hints and finally solution hided with spoiler ? It would be great if all editorials are this way.

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

Could you update editorial of E ? I think some of the C( i , j )s are meant to be W( i , j ).

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

$$$h$$$a$$$h$$$a $$$t$$$h$$$i$$$e$$$u$$$ n.$$$a$$$n$$$g$$$ SPyofgame

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

    So you just tag me for nothing more than say something insult ?

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

My solution for D: finding the conserved quantity

We noticed that the quantity $$$\sum_{i=1}^{N} {i \times A_i} $$$ will be conserved unless you operate on $$$1$$$ (decrease $$$N$$$) or on $$$N$$$ (increase $$$N$$$). Letting the number of operation on $$$i$$$ be $$$a_i$$$, and we can tell $$$a_1-a_n$$$.

Maintain the value of $$$\sum_{i=1}^{N} {i \times A_i} $$$ when rotating the array, and we can tell any $$$a_i-a_{i-1}$$$. Then it's easy.

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

It can be strongly felt ARC is more and more difficult and interesting.Hope it can continue and thank you maroonrk

→ Reply