We will hold AtCoder Regular Contest 157.
- Contest URL: https://atcoder.jp/contests/arc157
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20230225T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: ygussany
- Tester: maspy, Nyaan
- Rated range: — 2799
The point values will be 300-500-600-600-700-900.
We are looking forward to your participation!
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.
It’s 20 minutes break now:P
A question: why ARC contests are held on Saturdays recently? I'm a little confused since they were held on Sundays before.
There is no deep reason behind it. When choosing a date, I check available dates and ask writers their preferences. Also, I don't think there is a strong tendency toward Saturday. It's just that the recent two ARCs are on Saturday.
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!
no YY
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.
E: doesn't your solution work in sum over all vertices
(leaves in the left subtree) times (leaves in the right subtree)
? If so, it is clearly at most(number of leaves) choose 2
per test case.Yes. Indeed. But for some reason, I did not understand it during the contest. even though I specifically counted the number of leaves in subtrees and I knew this idea before. Probably my brain was just not working during the contest.
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?
It was brute force. I generated all the 3^N instances for small N, and observed the structure of such evil instances. Then, I generated all (or many random) instances with the structure for large N, and pick desired ones. The testcases include instances that need to match characters with distance 14, and I'm not sure whether this is maximum or not under N <= 50.
In the following instances, x/y means both characters are X/Y, respectively, and z means one is X and the other is Y. When N = 4, there is an evil instance "zxyz" appearing in the editorial, for which we need to match two Xs appearing 2nd and 4th to obtain the solution "XX". When N = 8, there is an evil instance "zyyxzyxz", for which we need to match two Xs appearing 1st and 4th to obtain the solution "XYYXX". Most of such evil instances are of form "z*z*z*...*z", where each * is independently xy, yx, xxy, xyy, yxx, or yyx. Thus, I checked many of such instances for large N.
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?
You don't need to consider the divisors larger than H or W.
Oh... Right... Thanks
screencast
Can anyone tell me why my submission https://atcoder.jp/contests/arc157/submissions/39214632 get WA for 8 testcases? Thanks!