### maroonrk's blog

By maroonrk, history, 10 months ago,

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!

• +190

 » 10 months ago, # |   +40 AtCoder deserves a bump of this post.
 » 10 months ago, # |   +24 Fun fact: when I was purple, I proposed a "bad" version of D on codeforces and it was rejected. Screenshot
 » 10 months ago, # |   0 How to solve Problem C ?
 » 10 months ago, # | ← Rev. 3 →   +36 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.
•  » » 10 months ago, # ^ |   +21 I also solved C by this way. Actually, I thought it was intended solution during contest XD
•  » » 10 months ago, # ^ | ← Rev. 2 →   +8 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. :)
•  » » » 10 months ago, # ^ |   0 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
•  » » » 10 months ago, # ^ | ← Rev. 2 →   +16 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.
•  » » 10 months ago, # ^ |   0 Why can't we use the same delimeter each time ? I am unable to find a case where it don't work.
•  » » » 10 months ago, # ^ | ← Rev. 2 →   0 e.g. $717717$ for $N=5$$1771$ is divisible by $7$.
•  » » » » 10 months ago, # ^ |   0 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.
•  » » » » » 10 months ago, # ^ | ← Rev. 4 →   0 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$).
•  » » » » 5 months ago, # ^ | ← Rev. 6 →   0 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.
•  » » » » » 5 months ago, # ^ |   0 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$."
•  » » » » » » 5 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » » » 5 months ago, # ^ | ← Rev. 2 →   0 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. Spoilerlong long tri(long long a) { return a * (a + 1) / 2; } bool checkCanUseTwoOnes(long long sum) { for(int i = 0; tri(i) <= sum; i++) { for(int j = i; tri(i) + tri(j) <= sum; j++) { for(int k = j; tri(i) + tri(j) + tri(k) <= sum; k++) { if(tri(i) + tri(j) + tri(k) == sum) { if(i % 6 != 2 || j % 6 != 2 || k % 6 != 2) return true; } } } } return false; } int solve() { for(long long i = 0; i < 50; i++) { for(long long j = i; j < 50; j++) { for(long long k = j; k < 50; k++) { long long sum = tri(i*6+2) + tri(j*6+2) + tri(k*6+2); if(checkCanUseTwoOnes(sum)) cout << ""; else cout << "NO\n"; } } } return 0; } 
•  » » » 5 months ago, # ^ |   0 We can use '1' as the same delimiter. 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.
 » 10 months ago, # |   +24 Here is some funny overkill solution for problem A using digit DP (Submission link)
•  » » 10 months ago, # ^ | ← Rev. 2 →   +14 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.
•  » » » 10 months ago, # ^ |   +8 Same (I spent more time for A than for B, C, D).
 » 10 months ago, # |   +31 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.
 » 10 months ago, # | ← Rev. 2 →   0 Could you update editorial of E ? I think some of the C( i , j )s are meant to be W( i , j ).
 » 10 months ago, # |   -19 $h$a$h$a $t$h$i$e$u$ n.$a$n$g$ SPyofgame
•  » » 10 months ago, # ^ |   0 So you just tag me for nothing more than say something insult ?
 » 10 months ago, # |   +24 My solution for D: finding the conserved quantityWe 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.
 » 10 months ago, # |   0 even tho i got an idea, Can someone rephrase problem C? unable to understand the english used.
 » 10 months ago, # |   0 It can be strongly felt ARC is more and more difficult and interesting.Hope it can continue and thank you maroonrk
 » 10 months ago, # |   0 anyone explain pls task A?