maroonrk's blog

AtCoder Regular Contest 137 Announcement
By maroonrk, history, 3 years ago, In English

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!

  • Vote: I like it
  • +160
  • Vote: I do not like it

Comments Comments (33)
| Write comment?
»
3 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +44 Vote: I do not like it

C++20 when

→ Reply
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Looking forward to enjoy the contest!

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

What happened to the country leader-board ?

→ Reply
»
3 years ago, # |
  Vote: I like it -31 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

is D sos-dp?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    Apparently, but it also has a cool serpenski triangle-like structure that leads to a simple $$$O(n logn)$$$ recursive solution.

    Picture
    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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$$$.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        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

        → Reply
»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -10 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +31 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      You can use the Atcoder Library.

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +42 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    You are right. I WA on C for 10+ times because of it, and got AC quickly after the contest.

    → Reply
»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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<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

→ Reply
»
3 years ago, # |
  Vote: I like it -6 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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?

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    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 grid

    ex.

    1 0 0 0

    1 1 1 1

    1 2 3 4

    1 3 6 10

    (4 is C(4, 1), 10 is C(5, 2) etc...)

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      The observation is amazing! Thanks a lot!

      → Reply