C: The answer is $$$\phi(n) \cdot \binom{n-1}{k-1}$$$, which you can compute in $$$O(k)$$$ time (note that $$$k \le \frac{n}{4}$$$ so it's barely fast enough.

E: Compute a maximum matching (of size $$$M$$$) using Edmond's Blossom Algorithm. Basically, you can reduce the problem of whether there is a vertex cover of size $$$M$$$ to 2-SAT (because the vertex cover must contain at least one vertex per edge in the matching), which you can solve in $$$O(m+n)$$$ time. For the case $$$M+1$$$, try all extra unmatched vertex to take into the vertex cover as well as all edges in the matching where both endpoints are taken.

The contest is still running for Div.2 :) As it was postponed 3 times, and then started, but without problems(!), and so later it restarted again :)

UPD. It's just finished. How to solve Div.2 Problem H. "Ending by 3"?

If that holds, then you can also solve the problem in $$$\mathcal{O}(n C^{1/3})$$$ without assuming that all $$$p_i$$$ are distinct, by grouping items with equal $$$p_i$$$, and noticing that if we have a group of elements with equal $$$p_i$$$, and in the optimal solution to $$$dp[i][k]$$$ we take $$$m$$$ of them, then in $$$dp[i][k+1]$$$ we take $$$m$$$ or $$$m+1$$$ of them.

I didn't notice that all $$$p_i$$$ are distinct during the contest, so this was what I did. I don't know how to prove that that observation holds, though.

I'm pretty sure you can't just solve max matching just by trying random matchings; there are graphs with few max matchings, so finding one randomly is probably impossible.

I think the editorial is referring to randomized algorithms like https://github.com/kth-competitive-programming/kactl/blob/master/content/graph/GeneralMatching.h.

Or use a "better formula" (courtesy of Wikipedia):

Of course, with a brute force when $$$k$$$ is small.

The issue is not in calculation of $$$\ln$$$ itself, the issue is in taking difference of them, which creates awful relative error.

There is a link to the editorial in the post.

Each multiplier is at least $$$(1 + \frac{1}{\sqrt{B}})$$$, there are $$$\sqrt{B}$$$ of them, $$$(1 + \frac{1}{k})^{k} \ge 2$$$ for any $$$k \ge 1$$$.