Codeforces really needs a mobile compatible website... u.u

I'll edit the formatting when I get to a PC.

As helpful as always ffao, thanks! By the way, secret test data has been released and can be found here.

Nice solution to J in the editorial! Since it didn't explain the DP solution I was referring to (it also needs some bijection magic, sorry), here it is:

Take any just a bit sorted sequence with n elements and using exactly k different integers, for example "2 1 3 2" and list the positions in which 1 appears, let this list be L₁ = {2}, then similarly get L₂ = {1, 4} and L₃ = {3}.

Now concatenate these lists in reverse order (that is, L₃ then L₂ then L₁) to get the new sequence (3, 1, 4, 2).

This new sequence is a permutation of the integers from 1 to n, in which p_i > p_i + 1 for exactly k - 1 values of i. Doing the reverse procedure, you can see every just a bit sorted sequence is equivalent to one permutation like this.

But the number of permutations with n elements such that p_i > p_i + 1 for k values of i is easy to count using DP. To construct the recurrence relation, note that adding n to a permutation of length n - 1 always creates a new spot in which p_i > p_i + 1, except if you place it in a position where that condition was already true or at the end of the sequence. This gives us:

A(n, k) = (n - k) * A(n - 1, k - 1) + (k + 1) * A(n - 1, k)

On problem K my relation is to check all the possibilities of shop on the current level, is that correct?

I guess this is the relation but if i use memo on this relation i'll get Runtime Error on a big case and WA on an avarage case.

Hi ffao,

I thought of using ternary search to solve problem C and found that it is also mentioned in the editorial. Can you elaborate more on how to use Circular Line Sweep to solve the problem?

Thanks