### nick_301's blog

By nick_301, history, 8 days ago,

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?

• +17

 » 5 days ago, # |   +35 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:If we denote the length of the subarray chosen in operation $i$ as $l_i$, we can see that the problem wants us to find the expected value of $\left(\sum_{i=1}^k l_i\right)^2$Expanding this out we get $\sum_{i=1}^{k}l_i^2 + 2\sum_{i=1}^{k}\sum_{j=i+1}^k l_i\cdot l_j$Using linearity of expectation we get that the answer is the expected value of $k \cdot l_1^2 + k(k-1)l_1 \cdot l_2$Using the definitions of $E_1(n)$ and $E_2(n)$ given above, we get $A(n,k) = k\cdot E_2(n) + k(k-1)(E_1(n))^2$as desired.Claim: $E_1(n) = \frac{n+2}{3}$ Proof:Since expected value is just the average value, we want to find the average value of $l$ which is $\frac{2}{n(n+1)}\sum^{n}_{sz = 1} sz(n+1-sz)$ Why?The summation just goes through all the possible subarray sizes, $sz$ and multiplies it by the number of subarrays of size $sz$, $n+1-sz$.We can simplify this to get $\frac{2}{n(n+1)}\left[(n+1)\sum^{n}_{sz = 1} sz - \sum^{n}_{sz = 1}sz^2\right]$Using the fact that $\sum_{i = 1}^{n}i = \frac{n(n+1)}{2}$and$\sum_{i = 1}^{n}i^2 = \frac{n(n+1)(2n+1)}{6}$this simplifies to$$E_1(n) = \frac{n+2}{3}$$ as desired.Claim: $E_2(n) = \frac{(n+1)(n+2)}{6}$ Proof:Similar to how we found $E_1(n)$, we can see that $E_2(n) = \frac{2}{n(n+1)}\sum^{n}_{sz = 1} sz^2(n+1-sz)$This simplifies out to $\frac{2}{n(n+1)}\left[(n+1)\sum^{n}_{sz = 1} sz^2 - \sum^{n}_{sz = 1}sz^3\right]$Using the fact that $\sum_{i = 1}^{n}i^2 = \frac{n(n+1)(2n+1)}{6}$and$\sum_{i = 1}^{n}i^3 = \left(\frac{n(n+1)}{2}\right)^2$ this simplifies to $E_2(n) = \frac{(n+1)(n+2)}{6}$as desired.
•  » » 5 days ago, # ^ |   +18 Thank you so much.You have explained it so well here.Could you suggest some similiar problems or articles where I could practice?
•  » » » 3 days ago, # ^ |   +18 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 H — This solution in my opinion is more intuitive and easier to understand than the official one.Edu 57 FThere 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.
•  » » » » 3 days ago, # ^ |   +10 I will go through them. Thank you again.