### maroonrk's blog

By maroonrk, history, 3 months ago,

We will hold AtCoder Regular Contest 137.

The point values will be 300-400-600-700-800-1100.

We are looking forward to your participation!

• +160

 » 3 months ago, # |   +18 looking forward to participate! also friendly bump as it will begin in 15 mins
 » 3 months ago, # |   +44 C++20 when
•  » » 3 months ago, # ^ |   +5 ^^^^^^
 » 3 months ago, # |   +2 Looking forward to enjoy the contest!
 » 3 months ago, # |   +1 What happened to the country leader-board ?
 » 3 months ago, # |   -31 400 points questions in ARC are much harder than 400 points questions in ABC.
•  » » 3 months ago, # ^ |   +55 Great observation
 » 3 months ago, # |   0 is D sos-dp?
•  » » 3 months ago, # ^ |   +21 Apparently, but it also has a cool serpenski triangle-like structure that leads to a simple $O(n logn)$ recursive solution. Picture
•  » » » 3 months ago, # ^ |   +8 Can you explain how to use this diagram? Because I found it too during the contest, but don't know how to make it $n\log n$.
•  » » » » 3 months ago, # ^ |   +8 Let $solve(i, k)$ be a vector of size $2^k$ that represents the effect of applying a $2^k$-length leg right triangle to $i-2^k+1, ..., i$ (ie. the right angle would be at $i$). This equals $[solve(i, k-1)+solve(i-2^{k-1}, k-1), solve(i, k-1)]$, where $[a,b]$ means vector b appended to vector a and $a+b$ implies element-wise xor. Here's my code if it helps: https://atcoder.jp/contests/arc137/submissions/30246718
•  » » » » » 3 months ago, # ^ |   +8 Now understand. Thanks!
 » 3 months ago, # |   +4 I've never seen a prime gap in my life. Dang it.
 » 3 months ago, # |   0 Bad A
 » 3 months ago, # | ← Rev. 2 →   -10 Solved D 2 minutes after the contest... I can't believe myself
•  » » 3 months ago, # ^ |   0 Poor!
 » 3 months ago, # |   +31 I've always been a fan of ARC, but isn't today's problem a bit standard? D is Lucas theorem and the high-dimensional prefix sum, and E is the maximum cost cyclic flow. Of course they are fine as standard problems, but I feel that this is a departure from ARC's past style. C is very beautiful though. Anyway thanks to the author for bringing us this contest.
•  » » 3 months ago, # ^ |   0 I think E is quite annoying that even if you figure out how to make the graph, you can't get accept without using primal-dual algorithm, which is not often used in cp.
•  » » » 3 months ago, # ^ |   +5 If the initial graph is a DAG or has no negative edge ,then the min cost flow can be solved in O(flow*N*log(n)) using Dijkstra. I think it is not rare in cp.
•  » » » 3 months ago, # ^ |   +6 You can use the Atcoder Library.
•  » » » 3 months ago, # ^ |   0 can anybody explain me primal-dual algorithm is how being applied to this problem? Since I don't know about primal-dual, I read some articles(googled them) for primal-dual, but I couldn't understand how this problem is being interpreted as so.
 » 3 months ago, # | ← Rev. 2 →   +42 Maybe it's better to mark the key word such as " largest element" in problem C.It would help those whose English isn't so good(such as me) a lot.No matter how, thanks for the good contest.
•  » » 3 months ago, # ^ |   +5 You are right. I WA on C for 10+ times because of it, and got AC quickly after the contest.
 » 3 months ago, # |   +7 spent too much time on A trying to figure out what number theory tool to use only to find out its brute force.
 » 3 months ago, # |   0 Nice contest though some algorithms aren't frequently used
 » 3 months ago, # |   0 I liked B more than A
 » 3 months ago, # |   0 can anyone tell me why this code gives wa ? https://atcoder.jp/contests/arc137/submissions/30229995
 » 3 months ago, # |   0 I was able to solve Task A during the contest purely based on intuition, but haven't been able to prove it. I am trying both L and L + 1 as x and finding the largest co-prime numbers for them to maximize the value of y - x. My Submission. It would be great if someone could help with the proof of this approach.Thanks.
•  » » 3 months ago, # ^ |   +3 Prime gap
 » 3 months ago, # | ← Rev. 2 →   +8 I got TLE in E because of my big constant, I realize the importance of making a good template.
 » 3 months ago, # | ← Rev. 2 →   +13 Solve D in an optimize brute force which time complexity is $3^{10} \times 2^{10} + 3^{10} \times 2^{10}$ https://atcoder.jp/contests/arc137/submissions/30258055
 » 3 months ago, # |   +12 Both C and D can be done by brute force + finding the pattern.For C, we can brute force all array A such that $A_N \leq K$, say, $K = 10$. Actually, by the basics of game theory (Bob wins when all next cases Alice can win, Alice wins when any next case Bob can win), the brute force can be easily done by a bitmask DP. After this bruteforcing, we can easily find the pattern.For D, we want to find which initial $A_i$-s contribute to $A_N$ in the $k$-th round. It's easy to see there's a cycle for $A_N$ among rounds, so we want to find the length of this cycle, and how each element in this cycle is composed. To check for whether an initial $A_i$ contributes to $A_N$ in the $k$-th round easily, we can set $A_i = 2^{i-1}$ initially, and check the $i$-th bit of $A_N$ in $k$-th round. After bruteforcing, we find that for $2^{c-1} < N \leq 2^c$, the length of $A_N$'s cycle is $2^c$, and if \$N_1
•  » » 3 months ago, # ^ |   0 Me: brute force C but still can't find the pattern
 » 3 months ago, # |   -6 Can any one please explain how to solve C? I couldn't understand the editorial at all.
•  » » 3 months ago, # ^ |   0 Do you people downvote people who need help?!I really wonder where the world is going.
•  » » 3 months ago, # ^ | ← Rev. 2 →   +3 Assume a[n] > a[n — 1] + 1. After the first move you can reach some positions (i. e. states of the array, this is obvious), call them p1, p2 .. pm. In particular you can move a[n] -> a[n] — 1, call this position pm. Now if any of (p1, p2 .. p_m-1 is losing you could move directly there and win. If not, it means that p_m is losing since from there you can only move to p1, p2 ... p_m-1 (all of which are winning). Hence if a[n] > a[n — 1] + 1 first player always wins. Now assume it's not the case. Players will alternate in moves, but note that you can never allow the situation, where after your move the biggest element is bigger than the second by at least 2 -> then it would mean that you just let opponent win, by the argument from the begginging. It means that all "gaps" in the array (numbers >=0 && <= a[n] that are not present in original array a) must be visited. So now parity of the number of gaps decides who will be the winner.
•  » » » 3 months ago, # ^ |   0 Thanks man really appreciate it, i got it now.
 » 3 months ago, # |   +8 What's the meaning of "Repeated applications of one-dimensional prefix sum correspond to vertical and horizontal moves in a two-dimensional grid" in the editorial of Problem D?
•  » » 3 months ago, # ^ | ← Rev. 2 →   +3 If you focus on the contribution of a single element when doing prefix sum multiple times, you will find out that stuff is similar to path on gridex.1 0 0 01 1 1 11 2 3 41 3 6 10(4 is C(4, 1), 10 is C(5, 2) etc...)
•  » » » 3 months ago, # ^ |   +8 The observation is amazing! Thanks a lot!