We will hold AtCoder Regular Contest 129.

- Contest URL: https://atcoder.jp/contests/arc129
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20211121T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: maroonrk
- Tester: maspy, satashun
- Rated range: — 2799

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

We are looking forward to your participation!

AtCoder deserves a bump of this post.

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

ScreenshotI found an even more constructive solution for

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

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

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

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

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.

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

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

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

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.

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

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.

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

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.

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.

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

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

Bafterwards in 7 minutes left me flabberghasted.Same (I spent more time for A than for B, C, D).

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.

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

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

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

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.

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