We will hold AtCoder Regular Contest 227.
- Contest URL: https://atcoder.jp/contests/arc227
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20260816T2100&p1=248
- Duration: 120 minutes
- Writer: yosupo
- Tester: Nyaan, sigma425
- Rated range: 1200 ~ 2799
- Point Values: 400-500-700-700-700-800
We are looking forward to your participation!
I hope I can have 2000+ perf. Come on!
As a result you got 2104 perf and you are the only person who solved problem D in my favs! What a dsa /bx
I'll now stream solutions to A-E https://www.youtube.com/watch?v=m9vpPg4Ra3E
Thanks for the stream! I found A-C to be interesting and quite difficult.
GPT 5.6 Sol found a hack where your solution for C exceeds $$$10^6$$$ moves: $$$S=(ab)^{120}+bb+(ab)^{129}$$$
I believe it is significantly harder to hack if you randomize the indices that you merge.
Cool, thanks for the counterexample!
C is a bad problem.
Why ban any people who can solve D quickly,even D can be solved in 0.6k code.atcoder_official
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.
fun problems.
But problem F has a better approach.
Better than sqrt? Can you describe 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).
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.
You can express the recurrence as a continued fraction; then the numerator and denominator can be propagated by a simple matrix product.
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
or with $f_k = x^{k(k+2)} g_k$
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.
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?
Well well well
AtCoder's handling attitude is disappointing: appeal channels are vague, and only top-ranked contestants seem to be checked — unfair to regular participants.
AtCoder Random-banning Contest
AtCoder Random-banning Contest
AtCoder Random-banning Contest
ARC = Atcoder Random-ban Contest
C,D, andEare all very interesting.Ccan 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
Dand its solution are both elegant.Eis very hard for me, I don't understand why it's only worth 700 points, it feels like a completely different difficulty level fromCandD. 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
Cwithin $$$26n^2$$$?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.
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.