Same day with Codeforces Round 853 (Div. 2) with 35 minutes break. Hope I'll not be too tired to take part in both contests.

A question: why ARC contests are held on Saturdays recently? I'm a little confused since they were held on Sundays before.

For every ARC, I pay attention to whether the first question is worth 300 points or 400 points. This time, it is 300. Thanks.

Scoring distribution looks nice:)

RP++

RP++

have got lots of penalties :C

also find C and D have similar statement :)

omg XY Round

Is the Writer a fan of sex chromosome? There are much XY in problems! By the way, these remind me of the biological knowledge I have learned!

It's AtCoder Regular Corner-case again.

Finally get a minor +8 rating.

New writer, nice round.

D: My solution works in 5*10^8 heavy operations. Have no idea why it passed.

E: I felt like my solution works in 10^12. Definitely had no idea why it passed during the contest. Realized it only afterward.

Good round, but I feel like a cheater :) For me it was yoloforces.

B is such a penalty hell. Feel lucky to get AC just on time.

How to generate a test in F where the matching characters are far from each other?

Is there a reason why $$$N$$$ is $$$10^4$$$ (e.g. not $$$3000$$$) in problem E? Which solutions does $$$N = 10^4$$$ cut off?

Solved A-D. This time the difficulty is truly "regular".

A: If XX=n-1 or YY=n-1, answer is true, otherwise (XY+YX)>=1 must hold. Also for each block of consecutive Y, it will contribute +1 to both XY ans YX (unless it's on the left endpoint, contribute +1 to YX, or on the right endpoint, contribute +1 to XY) and in every situation |XY-YX|<=1 must hold. In fact, these necessary conditions are also sufficient.

B: First check corner cases for k==0 or k==n. Otherwise, if k<=cnt(x), we need to flip some x to y. If we flip XXY->XYY or YXX->YYX, cnt(YY) will increase 1, and if we flip YXY->YYY, cnt(YY) will increase 2. Therefore we can find all consecutive X-blocks (excludes these on the endpoints), sort them from small to large and fill them greedily. if k>cnt(x). we need to flip all x to y, and flip (k-cnt(x)) original y to x. We can do similarly by finding consecutive Y-blocks.

C: DP. We notice that {1, t+1, (t+1)^2} = {1, t+1, t^2+2*t+1} = {{1, 0, 0}, {1, 1, 0}, {1, 2, 0}} * {1, t, t^2} (where * denotes the matrix multiplication). Let t=cnt(YY) of a single path, and dp[i][j]={sum(1), sum(t), sum(t^2)} where sum is over all paths end at (i, j). When transit from (i-1, j) to (i, j), if s[i-1][j]==s[i][j]=='Y', we need to do a linear transfrom on dp[i-1][j]: from {t1, t2, t3} to {t1, t1+t2, t1+2*t2+t3}, similarly for (i, j-1) to (i, j). Then we just need to let dp[i][j]=dp[i-1][j]+dp[i][j-1].

D: We need to divide the grid into R*C blocks where R*C=cnt(Y)/2, R<=h, C<=w, and each block contains exactly 2 Y. We can do this by 2D prefix-sum and try all divisors of cnt(Y)/2.

After reading editorials of problem B, I feel that idea of handling the case when num(x)<k is so clever and impressive! During contest, I didn't find out such a simple "transformation", and failed solving this case. Cool problem and solution, thank you atcoder team!

UPD: Oops, it seems that somehow I read problem B as "find out the longest substring consisiting of letter Y". Now, for case num(x)>k, I use a similar greedy algorithm by changing Y to X from longer segment to smaller segment and get AC as well.

I am still confused about problem D. In the editorial it states "$$$k \le 80$$$, $$$ky \le 6.1 \times 10^7$$$". But why is that true? $$$y$$$ can be up to $$$2000^2 / 2$$$. For example, the number $$$1965600$$$ is suitable. It has $$$288$$$ different divisors which brings $$$ky$$$ to be $$$\approx 5.6 \times 10^8$$$. Am I missing something?

screencast

Can anyone tell me why my submission https://atcoder.jp/contests/arc157/submissions/39214632 get WA for 8 testcases? Thanks!