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.
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.
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.
Here 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 B afterwards 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