We will hold AtCoder Grand Contest 053. This contest counts for GP30 scores.
- Contest URL: https://atcoder.jp/contests/agc053
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20210410T2100&p1=248
- Duration: 180 minutes
- Number of Tasks: 6
- Writer: yutaka1999
- Tester: HIR180
- Rated range: 1200 -
The point values will be 400-700-900-1000-1400-2400.
We are looking forward to your participation!
Is It Rated?
Yes!
Correction: yes, for the range $$$[1200, \infty)$$$.
Protip: don't start with A!
Does atcoder do anything about people submitting their code in an alt to avoid penalty? like plag checks? I have like 6 penalty rn and when looking at standings, I see many accounts with submissions towards the end with no comp history or 1 comp. Is this normal or am I imagining things
My notepad after trying to D:
https://i.imgur.com/WEUuoTx.jpg
(geranazavr555 fix images in spoilers please)
Any race ranking? Do AtCoder admins or clist.by admins plan to create such one?
aropan created the list on the clist. Thanks a lot.
Where does the formula from the second-to-last line from editorial of C come from? During the contest I came up with the rest of the solution in like 15 minutes and spent some decent amount of time trying to calculate this, coming to the conclusion that it's impossible :P. So is this somehow obvious?
I also didn't manage to get the formula during the contest, but that's how I understand it.
Let $$$X_i$$$ be the event where there is a greater value than $$$A_i$$$ among $$$B_1, \dots, B_{i+d}$$$. The probability we are looking for is $$$P(X_1 \cap \dots \cap X_n)$$$, which is equivalent to $$$P(X_1) \cdot P(X_2 | X_1) \cdot \dots \cdot P(X_n | (X_1 \cap \dots \cap X_{n-1}))$$$. Now it's easy to see that the mysterious $$$\frac{2i+d-1}{2i+d}$$$ is just $$$P(X_i | (X_1 \cap \dots \cap X_{i-1}))$$$ because $$$X_i$$$ won't hold only if $$$A_i$$$ is the greatest value among $$$A_1, \dots, A_i, B_1, \dots, B_{i+d}$$$.
Thanks a lot, got it.
what about (n + i-1) / (n + i) ? Can you explain more, pleaes?
Maybe it's still the same as 2i + d — 1 / 2i + d but for the case when i + d exceed N
For problem D, I don't understand the proof in the editorial that $$$t_{i,j}>=T_j$$$ for $$$i<j<=N$$$ when it takes 1, 2 or 3 minutes to solve a problem. Can somebody enlighten me?
By the way, I did find counterexamples when it could also take 4 minutes to solve a problem, for example:
or
(the $$$i$$$-th line listing the times it takes to solve the problems for the $$$i$$$-th participant)
Is there any detailed proof for problem D "don't need to check $$$i<j,t_{i,j}\le T_j$$$" ?
Polyline T does not have a suffix with slope greater than 2 means confilcts will be deal at j?