maroonrk's blog

By maroonrk, history, 5 weeks ago, In English

We will hold AtCoder Grand Contest 053. This contest counts for GP30 scores.

The point values will be 400-700-900-1000-1400-2400.

We are looking forward to your participation!

 
 
 
 
  • Vote: I like it
  • +78
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it -109 Vote: I do not like it

Is It Rated?

»
5 weeks ago, # |
  Vote: I like it +63 Vote: I do not like it

Protip: don't start with A!

»
5 weeks ago, # |
  Vote: I like it +23 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +41 Vote: I do not like it

My notepad after trying to D:

https://i.imgur.com/WEUuoTx.jpg

(geranazavr555 fix images in spoilers please)

»
5 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

Any race ranking? Do AtCoder admins or clist.by admins plan to create such one?

»
5 weeks ago, # |
  Vote: I like it +28 Vote: I do not like it

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?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +71 Vote: I do not like it

    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}$$$.

»
5 weeks ago, # |
  Vote: I like it +36 Vote: I do not like it

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:

Spoiler