The question is :
"Twilight Sparkle was playing Ludo with her friends Rainbow Dash, Apple Jack and Flutter Shy. But she kept losing. Having returned to the castle, Twilight Sparkle became interested in the dice that were used in the game.
The dice has m faces: the first face of the dice contains a dot, the second one contains two dots, and so on, the m-th face contains m dots. Twilight Sparkle is sure that when the dice is tossed, each face appears with 1/m probability . Also she knows that each toss is independent from others. Help her to calculate the expected maximum number of dots she could get after tossing the dice n times."
https://codeforces.com/problemset/problem/453/A link to the question
https://codeforces.com/blog/entry/13190 link to editorial
The editorial mentions a solution which uses n-dimensional super-cube with m-length-side. I am unable to understand how this approach is working.
Can anyone explain the reasoning behind taking the n-dimensional super-cube ?
The "supercube" is an array of points. For example for $m=4$ and $n=3$ we have
Each dot represents one of the possible results of tossing a cube with $m$ faces (labeled 1 to $m$) $n$ times. So if $m=10$ the result of each toss would be one of $1,2,\dots,10$. Each dot represents the result of one of the possible different tosses.
Sparkle is interested in the best single toss, not the total of the tosses. That would clearly be $m$ if it occurred. The worst case would be 1, in the unlikely event that every toss came up 1. If you look at the array of dots, you can see that the maximum value corresponds to the dots on the faces of the (super)cube which have one coordinate $m$. With $n$ tosses there are $n$ such faces.
The difficulty about adding up the number of dots in faces is that the faces overlap. So the supercube idea is that the number of dots with a maximum value of $m$ correspond to the number of dots in the complete cube, less the number of dots in the cube with only $m-1$ dots per side, but including the $(1,\dots,1) vertex$, ie $$m^n-(m-1)^n\text{ dots }$$ Similarly for a maximum of $r$ dots, we need $$r^n-(r-1)^n$$ To get the expected value of $r$ we take the sum given $$\sum_{r=1}^m r\left(\frac{r^n-(r-1)^n}{m^n}\right)$$