dfsof's blog

By dfsof, history, 16 months ago, In English

I think the official editorial of problem G is a little bit hard to understand for me, therefore I write a learning note, with an example, in English:

Google Drive (Typo corrected): https://drive.google.com/file/d/1imUKYXcxQNw8wC28YFeTzEAkBV2wswMo/view?usp=sharing

Tencent Docs (Typo corrected): https://docs.qq.com/pdf/DU2VOa09uYUJHYU9E

The above pdf files do not contain code. My code:

Spoiler

and my submission: 211097938.

Be careful when handling indices! Here is a wrong submission with Runtime Error: 211089726.

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

| Write comment?
»
16 months ago, # |
Rev. 2   Vote: I like it +17 Vote: I do not like it

Thank you for your notes!

»
16 months ago, # |
  Vote: I like it +4 Vote: I do not like it

There seem to be small typos though which confused me for a second. For example: it says that "our solution is $$$E\left[\prod_{i = 1}^n(a_i + x_{i, j})\right]$$$" but I imagine you mean $$$E\left[\prod_{i = 1}^n(a_i + \sum_{i = 1} ^ m {x_{i, j}})\right]$$$, because the indicator RV $$$x_{i, j}$$$ you state contributes $$$v$$$ with probability $$$i / n$$$ and contributes $$$0$$$ otherwise and of course this contribution of $$$v$$$ can occur in any of the $$$m$$$ operations not a single one. But so much as I understand, if we basically expand all of the terms out, each term will be of type 1: $$$a_i * x_{u, v}$$$ or type 2: $$$x_{u_1, v_1} * x_{u_2, v_2}$$$. For type 1 EV can be calculated due to independence. And for type 2, we can calculate this EV a little differently. And the use of DP in this problem is so we can calculate these terms more quickly than one by one. Hope my overall understanding of solution is correct.

  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you for your clarification! You are right, sorry for my typos! That was a typo.

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by dfsof (previous revision, new revision, compare).

»
16 months ago, # |
  Vote: I like it +5 Vote: I do not like it

I did a problem (ABC231G) before with similar tricks about random operation, so I recommend you to solve it.