nick_301's blog

By nick_301, history, 4 years ago, In English

There is a array of length A. We have to perform B operations. In each operation, we can select a subarray of any length and increase all its elements by 1. All subarrays are equiprobable. Find the expected value of the square of the sum of elements. (mod 1e9+7)

Constraints:

1<=A,B<=1e9

Sample Input 1:

A=2

B=2

There are 9 different order of operations.

  1. (0,0) + (1,1) = 2

  2. (0,0) + (0,0) = 2

  3. (1,1) + (0,0) = 2

  4. (1,1) + (1,1) = 2

  5. (0,1) + (0,0) = 3

  6. (0,1) + (1,1) = 3

  7. (0,0) + (0,1) = 3

  8. (1,1) + (0,1) = 3

  9. (0,1) + (0,1) = 4

Expected Value= [4*(2^2) + 4*(3^2) + (4^2)]/9 = 68/9 (mod 1e9+7) = 555555567

How do I approach this problem?

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

»
4 years ago, # |
  Vote: I like it +35 Vote: I do not like it

Note: I used $$$n$$$ and $$$k$$$ for $$$a$$$ and $$$b$$$ respectively. I also assumed based on the example that the array starts out with all zeroes.

If $$$A(n,k)$$$ is the answer for the input $$$n,k$$$,

$$$A(n,k) = k\cdot E_2(n) + k(k-1)(E_1(n))^2$$$

where

$$$E_2(n) = \frac{(n+1)(n+2)}{6} \text{ and } E_1(n) = \frac{n+2}{3}.$$$

In an operation, a subarray of length $l$ is chosen from an array of size $$$n$$$. $$$E_1(n)$$$ denotes the expected value of $$$l$$$ and $$$E_2(n)$$$ denotes the expected value of $$$l^2$$$.

Claim: $$$A(n,k) = k\cdot E_2(n) + k(k-1)(E_1(n))^2$$$

Proof:

Claim: $$$E_1(n) = \frac{n+2}{3}$$$

Proof:

Claim: $$$E_2(n) = \frac{(n+1)(n+2)}{6}$$$

Proof:
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    Thank you so much.

    You have explained it so well here.

    Could you suggest some similiar problems or articles where I could practice?

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      Here are two tutorials by Errichto that I found pretty helpful, Part 1 and Part 2. They also have problems to help practice the techniques.

      Some problems that I can remember off the top of my head that use expected value are these:

      GR 10 HThis solution in my opinion is more intuitive and easier to understand than the official one.

      Merge CardsO(n) solution by Errichto

      Edu 57 F

      There are also some nice resources out there like this one that aren't all expected value problems but in my opinion, help to build an intuitiveness that can help solve expected value problems.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        I will go through them. Thank you again.