maroonrk's blog

By maroonrk, history, 2 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! Comments (23)
 » 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. Screenshot » How to solve Problem C ?
 » 2 months ago, # | ← Rev. 3 →   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
•  » » 2 months ago, # ^ | ← Rev. 2 →   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
•  » » » 2 months ago, # ^ | ← Rev. 2 →   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.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   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.
•  » » » » » 2 months ago, # ^ | ← Rev. 4 →   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$).
 » Here is some funny overkill solution for problem A using digit DP (Submission link)
•  » » 2 months ago, # ^ | ← Rev. 2 →   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.
 » 2 months ago, # | ← Rev. 2 →   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 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.
 » even tho i got an idea, Can someone rephrase problem C? unable to understand the english used.
 » It can be strongly felt ARC is more and more difficult and interesting.Hope it can continue and thank you maroonrk
 » anyone explain pls task A?