looking forward to participate! also friendly bump as it will begin in 15 mins

C++20 when

Looking forward to enjoy the contest!

What happened to the country leader-board ?

400 points questions in ARC are much harder than 400 points questions in ABC.

is D sos-dp?

I've never seen a prime gap in my life. Dang it.

Solved D 2 minutes after the contest... I can't believe myself

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.

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.

spent too much time on A trying to figure out what number theory tool to use only to find out its brute force.

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.

I got TLE in E because of my big constant, I realize the importance of making a good template.

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

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} \lt N \leq 2^c$$$, the length of $$$A_N$$$'s cycle is $$$2^c$$$, and if $$$N_1 \lt N_2$$$, elements in $$$A_{N_1}$$$'s cycle are prefixes of $$$A_{N_2}$$$'s cycle. This inspires us to complement the length of $$$A$$$ to $$$2^c$$$. Then we can look at some cycles ($$$A_N$$$ in binary representation) and find the pattern:

$$$N = 4$$$, the cycle is 1000 1111 1010 1100;

$$$N = 8$$$, the cycle is 10000000 11111111 10101010 11001100 10001000 11110000 10100000 11000000;

$$$N = 16$$$, the cycle is 1000000000000000 1111111111111111 1010101010101010 1100110011001100 1000100010001000 1111000011110000 1010000010100000 1100000011000000 1000000010000000 1111111100000000 1010101000000000 1100110000000000 1000100000000000 1111000000000000 1010000000000000 1100000000000000.

And it's easy to see the pattern by splitting the binary representation into two halves. According to this pattern, we can come up with a $$$O(n \log n)$$$ solution based on divide-and-conquer.

I have included the bruteforcing code in annotations of my solution.

C: https://atcoder.jp/contests/arc137/submissions/30247609

D: https://atcoder.jp/contests/arc137/submissions/30242515

Can any one please explain how to solve C? I couldn't understand the editorial at all.

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?