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:

Spoileror

(the $$$i$$$-th line listing the times it takes to solve the problems for the $$$i$$$-th participant)