Vovochka#12868

Vovochka (Editorial)

As the order of numbers in the input doesn't matter, let's suppose that they are given in sorted order, and let's say that the median of numbers a_i, a_j, a_k is a_j for i<j<k.

Suppose that our triples are (a_{x_i}, a_{y_i}, a_{z_i}) with x_i<y_i<z_i. Wlog, they are sorted by the position of the middle element, so that y_1<y_2\ldots <y_n. Then, we must have y_i\ge 2i for each , as max(x_j, y_j)\le y_i for j\le i. Similarly, we must have y_i \le 3n+1-2(n+1-i), or y_i\le n-1+2i.

It can be shown that these conditions on y_i are sufficient: if 2i \le y_i \le n-1+2i, we can select x_i, z_i in such a way that each number from to is in exactly one triple and x_i < y_i < z_i. Just take x_i as the -th number which isn't one of y_i, and z_i as the n+i-th number which isn't one of y_i. Indeed, before y_i there are at least numbers which aren't one of , and after y_i there are at least n+1-i numbers which aren't one of .

Now, how to count the number of distinct multisets a_{y_1}, a_{y_2}, \ldots, a_{y_n} under the conditions above? We will do dp, let's process the groups of equal numbers one by one from left to right. Suppose that we are processing a group of numbers, that we already processed numbers, and selected from them as -s, let's denote dp[l][s] as the number of different ways to select those -s from first numbers.

How many numbers can we select as s from our group of numbers? If we select s_1 of them, then the following conditions have to hold:

  • s+s_1 \le n (trivial)

  • l+k \ge 2(s + s_1) (as s+s_1-th has to be among first l+k elements)

  • l+k+1 \le n-1+2(s+s_1+1) if s+s_1+1\le n, (as s+s_1+1st , if it exists, has to be starting from l+k+1-th element).

It's easy to show that if these conditions hold, we can choose s_1 s among l+1, l+2, \ldots, l+k, so that all conditions on them would be true.

So, we just have a dp, where we can transition from dp[l][s] to dp[l+k][s+s_1] when the conditions above hold. It's easy to see that for each s_1 we have at most transitions, and the sum of all s_1 is precisely , so the total complexity is O(n^2).