maroonrk's blog

By maroonrk, history, 3 months 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

»
3 months 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

»
3 months ago, # |
  Vote: I like it +44 Vote: I do not like it

C++20 when

»
3 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Looking forward to enjoy the contest!

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

What happened to the country leader-board ?

»
3 months 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.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

is D sos-dp?

  • »
    »
    3 months 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
    • »
      »
      »
      3 months 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$$$.

      • »
        »
        »
        »
        3 months 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

»
3 months ago, # |
  Vote: I like it +4 Vote: I do not like it

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

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Bad A

»
3 months 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

»
3 months 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.

  • »
    »
    3 months 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.

    • »
      »
      »
      3 months 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.

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

      You can use the Atcoder Library.

    • »
      »
      »
      3 months 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.

»
3 months 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.

  • »
    »
    3 months 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.

»
3 months 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.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice contest though some algorithms aren't frequently used

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I liked B more than A

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone tell me why this code gives wa ? https://atcoder.jp/contests/arc137/submissions/30229995

»
3 months 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.

»
3 months 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.

»
3 months 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

»
3 months 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

»
3 months 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.

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

    Do you people downvote people who need help?!

    I really wonder where the world is going.

  • »
    »
    3 months 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.

»
3 months 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?

  • »
    »
    3 months 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...)

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

      The observation is amazing! Thanks a lot!