Actually, the latter half of the intended solution (after the "it can be rephrased as follows:" line in the editorial) is a famous problem. For example, I can remember the same technique was used in the problem A in the Stage 7 of the UCUP this season. Therefore I thought it would not be as hard as E and F.

In addition, testers solved the problem without great difficulty. They said it wouldn't be hard for those who are familiar with formal power series, and C and D were of a similar difficulty. This is how we chose the score of 900.

I'd also say it's not very hard for people familiar with formal power series, though I used a completely different approach from the editorial. Describing the answer using coefficients of closed form is straightforward with only difficulty coming from algebraic mistakes, expanding that into series is a bit trickier since you can choose to expand in an ugly way, but you can try multiple things there.

Basically if the OGF of choosing $$$m$$$ segments inside a slice containing $$$n$$$ unused points (the segment that would cut off this slice can't be chosen) is $$$f(x,y) [x^m y^n]$$$, then the answer is $$$f^2(x,y) [x^{N-2} y^{M-1}] \frac{N}{2M}$$$. A bit of combinatorics gives

and the square root can be expanded using Taylor series for square root. This is where things can get ugly, but it gets much nicer if we take $z = y(1+x)$ and bring $$$1-z$$$ outside the square root before expanding $$$\sqrt{1-4xz/(1-z)^2}$$$:

Then we take just the terms containing $z^{N-2}$, expand $$$(1+x)^{N-2}$$$ in them to pick the right coefficients for $$$x^{M-1}$$$ in total and we're done. It's work but doesn't require a stroke of genius, I think I could've switched solving C for D and gotten around the same result.

Would you mind sharing a full derivation? I got

where the answer is

But when I tried expanding the square root I ended up with a quadratic rather than a linear number of terms. I'm getting the correct answers for small $N$ and $$$M$$$ so it must be equivalent to the editorial somehow ...

UPDATE: It works out if you rewrite the square root as

where $$$c=a(1+b)$$$, as Xellos did above.

To calculate $$$C_p$$$, do you need to use the same method as the editorial uses to compute $$$G_k$$$?

you can do more better for c' = 3 , (4, 2 , 5 , 4, 2 , 8). But the thing is in this case c = 4 is the best we can , in the cases where c = max. is not the best it can be shown v[i+1]-v[i] thing yields the best answer.