maroonrk's blog

AtCoder Grand Contest 053 Announcement
By maroonrk, history, 3 years 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

»
3 years ago, # |
  Vote: I like it -109 Vote: I do not like it

Is It Rated?

→ Reply
»
3 years ago, # |
  Vote: I like it +63 Vote: I do not like it

Protip: don't start with A!

→ Reply
»
3 years 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

→ Reply
»
3 years 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)

→ Reply
»
3 years 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?

→ Reply
»
3 years 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?

→ Reply
  • »
    »
    3 years 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}$$$.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Thanks a lot, got it.

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      what about (n + i-1) / (n + i) ? Can you explain more, pleaes?

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +14 Vote: I do not like it

        Maybe it's still the same as 2i + d — 1 / 2i + d but for the case when i + d exceed N

        → Reply
»
3 years 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
→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply