atcoder_official's blog

AtCoder Regular Contest 227 Announcement
By atcoder_official, history, 3 weeks ago, In English

We will hold AtCoder Regular Contest 227.

We are looking forward to your participation!

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

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

I hope I can have 2000+ perf. Come on!

→ Reply
»
3 weeks ago, hide # |
 
Vote: I like it +37 Vote: I do not like it

I'll now stream solutions to A-E https://www.youtube.com/watch?v=m9vpPg4Ra3E

→ Reply
  • »
    »
    3 weeks ago, hide # ^ |
     
    Vote: I like it +48 Vote: I do not like it

    Thanks for the stream! I found A-C to be interesting and quite difficult.

    Hack for C
    → Reply
»
3 weeks ago, hide # |
 
Vote: I like it +25 Vote: I do not like it

C is a bad problem.

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

Why ban any people who can solve D quickly,even D can be solved in 0.6k code.atcoder_official

→ Reply
»
3 weeks ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

I thought C is a bfs problem and try to compress the states and it cost me the whole contest. And it turns out it is a ad-hoc intuition math problem.

Actually there is another version of C. n is small (probably 20), but you need to first minimize k, then you need to minimize L.

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

fun problems.

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

But problem F has a better approach.

→ Reply
  • »
    »
    2 weeks ago, hide # ^ |
     
    Vote: I like it +3 Vote: I do not like it

    Better than sqrt? Can you describe it?

    → Reply
    • »
      »
      »
      2 weeks ago, hide # ^ |
       
      Vote: I like it +5 Vote: I do not like it

      We represent the DP process using generating functions. Let F_{x} be the generating function for the current number of contiguous segments (gaps) equal to x. The recurrence can be rearranged into a form where F_{x}​ is proportional to F_{x−1} + F_{x+1}. This recurrence can be written in matrix form, and we can compute the product of all matrices using divide‑and‑conquer NTT, with all polynomial multiplications taken modulo x_{n+1}. Time complexity O(n log^2 n).

      → Reply
      • »
        »
        »
        »
        2 weeks ago, hide # ^ |
         
        Vote: I like it +3 Vote: I do not like it

        Yes, I got the relation $$$F_k = k x^{1+2k} (F_{k-1}+F_{k+1}+2F_k) / (1 - x^{2k})$$$ and the sqrt solution is just filling out a table for small $$$k$$$, but I don't see how it can be transformed into a computable product of matrices.

        → Reply
        • »
          »
          »
          »
          »
          2 weeks ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          You can express the recurrence as a continued fraction; then the numerator and denominator can be propagated by a simple matrix product.

          → Reply
          • »
            »
            »
            »
            »
            »
            13 days ago, hide # ^ |
             
            Vote: I like it +3 Vote: I do not like it

            Honestly, these half-sentence descriptions don't accomplish much beyond "don't abandon the following directions". The editorial's also rather barren after describing initial combinatorics.

            It's interesting that

            $$$f_k = k x^{1+2k} \left(1 - x^{2k} - 2k x^{1+2k} - k x^{1+2k} f_{k+1}\right)^{-1}$$$

            or with $f_k = x^{k(k+2)} g_k$

            $$$g_k = k \left(1 - x^2k - 2k x^{1+2k} - k x^{4(k+1)} g_{k+1}\right)^{-1}$$$

            can be derived in different ways, either through setting $f_k = F_k / F_{k-1}$ in the recurrence between DP-state-genfuncs, or thinking of ways to build a +1/-1/0 sequence that contains only values $$$\ge k$$$ and starts and ends with $$$k$$$, which gives $$$f_k = \sum_i \left(\frac{k x^{1+2k}}{1 - x^{2k}}\right)^{1+i} (2 + f_{k+1})^i$$$.

            And the answer is $$$f_1(x) / (1 - x^2) [x^{N+2}]$$$, plus 1 for empty sequence if $$$N$$$ is odd.

            Turns out I reached basically the optimal solution by myself, just didn't realise a continued fraction can be computed using multiplications of vectors (numerator of $$$f_{k+1}$$$, denominator of $$$f_{k+1}$$$) by transition matrices that go from $$$k+1$$$ to $$$k$$$. Nice method.

            And turns out the sqrt solution can surprisingly be insanely fast, below 0.3 ms for me.

            → Reply
»
2 weeks ago, hide # |
← Rev. 4  
Vote: I like it 0 Vote: I do not like it

How does Atcoder Official handle appeals from contestants whose code was wrongly flagged as AI-generated? What kind of users can submit an appeal? How do users appeal?

There are rumors claiming that Atcoder only spot-checks top-ranked contestants to see if they cheated, and that Atcoder will directly ban users who rank high but have a low level. Should Atcoder Official clarify this?

→ Reply
»
2 weeks ago, hide # |
 
Vote: I like it -27 Vote: I do not like it

ARC = Atcoder Random-ban Contest

→ Reply
»
2 weeks ago, hide # |
← Rev. 2  
Vote: I like it +6 Vote: I do not like it

C, D, and E are all very interesting.

C can be reduced to a graph problem with $$$O(n^2)$$$ nodes and then solved using BFS, without relying on any "observations" at all.

The statement of D and its solution are both elegant.

E is very hard for me, I don't understand why it's only worth 700 points, it feels like a completely different difficulty level from C and D. But it is indeed a beautiful problem. The statement is interesting and the editorial is clever. For solving such problem, I basically can only rely on brute‑force tabulation, observation with a bit of luck, and guessing, but the editorial cleverly connects it to polynomial operations.

Finally, how to find the minimum operation sequence for C within $$$26n^2$$$?

→ Reply
  • »
    »
    2 weeks ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Matter of personal aptitude, I suppose. E was super easy for me since I'm used to thinking about polynomial representations and decompositions, but I was staring at D from a thousand angles and didn't see a nice way to solve it at all.

    → Reply
  • »
    »
    2 weeks ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Guess there is big variance for these task. I also think of polynomial immediately after reading the statement and solve it in a reasonable time, but D took me a whole day to solve and I failed to solve C.

    → Reply