The Reminder to Expect

Criterion 2020 Round 2

Statement Editorial Statistics Discussion

Let’s take 13 as the value of $N$ and try to calculate the expected value ( $EV_{13}$ ).

EV_{13} = \dfrac{1\%1 \; + \; 2\%1 \; + \; ... \; + \; 13\%1}{13×13} \\ + \dfrac{1\%2 \; + \; 2\%2 \; + \; ... \; + \; 13\%2}{13×13}\\ ... \\ ... \\+ \dfrac{1\%13 \; + \; 2\%13 \; + \; ... \; + \; 13\%13}{13×13}

numerator = \{1\%1 \; + \; 2\%1 \; + \; ... \; + \; 13\%1 \} + ... + \{1\%13 \; + \; 2\%13 \; + \; ... \; + \; 13\%13 \}

= \{0 + 0 + ... + 0\} + \{1 + 0 + 1 + 0 + ... + 1\} + \{1 + 2 + 0 + 1 + 2 + 0 + 1 + ... + 1\} + ... + \{1 + 2 + ... + 12 + 0\}

= \{\lfloor\frac{13}{1}\rfloor × (0)\}\\ + \{\lfloor\frac{13}{2}\rfloor × (1) + 1\}\\ + \{\lfloor\frac{13}{3}\rfloor × (1 + 2) + 1\}\\ + \{\lfloor\frac{13}{4}\rfloor × (1 + 2 + 3) + 1\}\\ + \{\lfloor\frac{13}{5}\rfloor × (1 + 2 + 3 + 4) + 1 + 2 + 3\}\\ ...

= \{\lfloor\frac{13}{1}\rfloor × \sum_{i=0}^{0}i\}\\ + \{\lfloor\frac{13}{2}\rfloor × \sum_{i=0}^{1}i + \sum_{i=0}^{13\%2}i\}\\ + \{\lfloor\frac{13}{3}\rfloor × \sum_{i=0}^{2}i + \sum_{i=0}^{13\%3}i\}\\ + \{\lfloor\frac{13}{4}\rfloor × \sum_{i=0}^{3}i + \sum_{i=0}^{13\%4}i\}\\ + \{\lfloor\frac{13}{5}\rfloor × \sum_{i=0}^{4}i + \sum_{i=0}^{13\%5}i\}\\ ...

= \sum_{j=1}^{13}\{\lfloor\frac{13}{j}\rfloor × \sum_{i=0}^{j-1}i + \sum_{i=0}^{13\%j}i\}

EV_N = \dfrac{\sum_{j=1}^{N}(\ \lfloor\frac{N}{j}\rfloor × \sum_{i=0}^{j-1}i )\ }{N^2} + \dfrac{\sum_{j=1}^{N}(\ \sum_{i=0}^{N\%j}i )\ }{N^2}

Therefore, for any given M, we have to calculate:

\sum_{N=1}^{M}(\dfrac{\sum_{j=1}^{N}(\ \lfloor\frac{N}{j}\rfloor × \sum_{i=0}^{j-1}i )\ }{N^2} + \dfrac{\sum_{j=1}^{N}(\ \sum_{i=0}^{N\%j}i )\ }{N^2})

There are almost $M×M$ number of terms each of which we can calculate in constant time. So the complexity would be $\mathcal{O}(M×M)$ .

But we can optimize further. To do that, we have find the sub sequences of this series that contain same numerators or denominators. Then we can calculate each of those sub-sequences in constant time.

Let's optimize the first part first.

\sum_{N=1}^{M}\dfrac{\sum_{j=1}^{N}(\ \lfloor\frac{N}{j}\rfloor × \sum_{i=0}^{j-1}i )\ }{N^2}

= \sum_{x=1}^{M}\sum_{N=1}^{M} \dfrac{\lfloor\frac{N}{x}\rfloor × \sum_{i=0}^{x-1}i }{N^2}

= \sum_{x=1}^{M}(\ \sum_{i=0}^{x-1}i × \sum_{N=1}^{M} \dfrac{\lfloor\frac{N}{x}\rfloor}{N^2} )

Now, let's focus on $\sum_{N=1}^{M} \dfrac{\lfloor\frac{N}{x}\rfloor}{N^2}$ .

= (\ \frac{0}{1^2} + ... + \frac{0}{(x-1)\ ^2} )\ + (\ \frac{1}{x^2} + ... + \frac{1}{(2×x-1)\ ^2} )\ + ... + (\ \dfrac{\lfloor\frac{M}{x}\rfloor - 1}{(\lfloor\frac{M}{x}\rfloor×x - x)^2} + ... + \dfrac{\lfloor\frac{M}{x}\rfloor - 1}{(\lfloor\frac{M}{x}\rfloor×x -1)\ ^2} )\ + (\ \dfrac{\lfloor\frac{M}{x}\rfloor}{(\lfloor\frac{M}{x}\rfloor×x)^2} + ... + \dfrac{\lfloor\frac{M}{x}\rfloor}{M^2} )

We can calculate this sum in $M/x$ complexity if we precalculate cumulative sum of $\dfrac{1}{i^2}$ from 1 to $M$ .

So for $x = 1 \space \text{to} \space M$ , total complexity will be near $M \space \text{log}(M)$ .

Now, for the second part:

\sum_{N=1}^{M}\dfrac{\sum_{j=1}^{N}(\ \sum_{i=0}^{N\%j}i )\ }{N^2}

= \sum_{N=1}^{M}\dfrac{\sum_{j=1}^{N}(\ \frac{(\ N\%j)\ (\ N\%j + 1)\ }{2} )\ }{N^2}

= \sum_{N=1}^{M}\dfrac{\sum_{j=1}^{N}(\ N\%j)\ (\ N\%j + 1)\ }{2 × N^2}

= \sum_{x=1}^{M} \sum_{N=1}^{M}\dfrac{(\ N\%x)\ (\ N\%x + 1)\ }{2 × N^2}

Now, let's focus on $\sum_{N=1}^{M}\dfrac{(\ N\%x)\ (\ N\%x + 1)\ }{2 × N^2}$ .

Let $N = k×x + j$ . Therefore $N\%x = j$ .

= \sum_{k}\sum_{j} \dfrac{j(j+1)}{2 × (kx +j)^2}

= \sum_{k}\sum_{j} \frac{1}{2} × \{ 1 + \dfrac{1 - 2kx}{kx + j} + \dfrac{(kx)^2 - kx}{(kx+j)^2} \}

The summation is modified in a way so that there are no variable $j$ remains in the numerator. Now we can calculate the inner sum in constant time. So, once again, the total complexity reduced to $M \space \text{log}(M)$ .

Math

Statistics

73% Solution Ratio

tmwilliamlin168Earliest, Feb '20

nusuBotFastest, 0.1s

sajib_readdLightest, 8.1 MB

Kuddus.6068Shortest, 787B