ODDSPLIT - Editorial

editorial
, ,
1

Clearly, for N\le 3 answer is 0.

Let’s count bad permutations instead — those which can’t be split into two odd subsequences. I claim that there are 3 types of bad permutations:

  • Identity permutation
  • Permutations in which all odd numbers are on odd positions, even numbers are on even positions, and the total number of inversions is odd.
  • Permutation of form (1, 2, \ldots, A, B+1, B+2, \ldots, C, A+1, A+2, \ldots, B, C+1, \ldots, N) for some 0\le A < B < C \le N such that at least one of C-B, B-A is odd.

Knowing this, it’s not hard to count the number of permutations of each type separately: 1 identity permutation, \frac{\lfloor \frac{N}{2} \rfloor!\lceil \frac{N}{2} \rceil!}{2} of the second type (exactly half of the permutations in which all parities are preserved have an odd number of inversions, bijection by swapping 1, 3), and some polynomial of third-degree for the permutations of the third type, we can calculate all of this in O(1) for given N after precalculating the factorials.

The remaining part of this post is proving that these are the only bad permutations and that they are bad.

Let’s consider any permutation, and start by dividing it into the largest number of blocks such that all the numbers from each block are larger than all the numbers from previous blocks (for example, (1, 3, 4, 2, 6, 5) will be divided into blocks [1], [3, 4, 2], [6, 5]. For each block let’s analyze separately, into subsequences of which parities is it possible to split it, and then combine this information from all blocks (this is possible because there are no inversions between blocks).

Now, consider some block [A_1, A_2, \ldots, A_K]. Build a graph G on K nodes, and draw an edge between nodes (i, j) where i<j if A_i>A_j. As this block can’t be divided into more blocks, this graph is connected.

Now, consider 2 cases.

  1. The total number of inversions in A is odd.
  • Clearly, we can divide A into two subsequences with parities 0, 1.

  • Suppose that we can’t divide it into two subsequences with parities 0, 0. This means, that after removing any element, the parity of the remaining array is also odd. So, each element is involved in an even number of inversions. Then, no matter how we split, one of the subsequences will have odd parity, and other will have even parity. Indeed, if we move an element from one subsequence to another, both parities will change, or no parities will change (as the degree of each node in G is even), and in the case of empty subsequence, we have parities 0, 1. So, we can’t get parities 0, 0 iff each element is involved in an even number of inversions (it’s easy to see that for permutation it’s equivalent to all even elements being on even positions and all odd elements being on odd positions).

  • Suppose that we can’t divide it into two subsequences with parities 1, 1. Consider any pair (i, j) with i<j and A_i>A_j. Then, if we remove this pair, an even number if inversions must remain. As we are removing d_i + d_j - 1 inversions, this number has to be odd, and, therefore, d_i and d_j have to have the same parities. As G is connected, we get that all d_i have the same parities.
    We already considered the case when they are all even, now consider the case when they are all odd. If all degrees in a graph are odd, it must have an even number of nodes. Also note that now, when we move an element from one subsequence to another, the parity of exactly one of them changes. So, if subsequences have even sizes, they have different parities, otherwise, they have the same parities. So, the condition is just that there is no subsequence of odd length with an odd number of inversions.
    We get that in G, each triangle contains an even number of edges (that is, 0 or 2). It’s easy to see that this graph has to be a complete bipartite graph. If A_M is the largest element, A[1:M] has to form one part, and A[M+1:K] another, both these parts are sorted and all numbers from the first are larger than all numbers from the second. This means that the block is just a cyclic shift. And indeed, a cyclic shift works! The last condition is that all degrees have to be odd and the total number of inversions has to be odd — which just implies that sizes of both parts have to be odd too.

  1. The total number of inversions in A is even.

  • Clearly, we can divide A into two subsequences with parities 0, 0.

  • If we can’t divide A into subsequences with parities 0, 1, it means that after removing any element, the number of inversions is still even, so d_i must be even for all i. And indeed, if all d_i are even, then, in the same way as in 1), subsequences always have the same parity.

  • If we can’t divide A into subsequences with parities 1, 1, then look at any pair (i, j) with i<j and A_i>A_j, and remove it. We have removed d_i + d_j - 1 inversions, so if the remaining number of inversions is even, this must be even too, and d_i and d_j must have different parities. So, if d_i and d_j have different parities, i and j can’t form an inversion, and G is a bipartite graph.
    Now, note that moving an element with an odd d_i from one subsequence to another changes the parity of exactly one subsequence, and moving one with an even d_i changes parities of both or of none. Therefore, the current conditions are equivalent to the following: there is no subsequence with an even number of elements with odd d_i with an odd number of inversions. In particular, if d_i is even, and d_j, d_l are odd, then both pairs (i, j), (i, l) form an inversion, or both don’t form.
    It’s easy to see then, that if there is at least one inversion, then any pair with odd, even degrees forms an inversion, so we get a complete bipartite graph. We know that in this case, the block is just a cyclic shift, where the size of at least one part is even (as the total number of inversions is even), and the size of the other part has to be odd (otherwise there will be an inversion between two elements with even degrees in G).

Now, let’s combine the information from the blocks.

  1. Block of length 1 can only give 0, 0.
  2. Cyclic shift with at least one part of odd size can only give 0, 0 and 0, 1.
  3. If all degrees in a block are even, then it can give only 0, 1 if the total number of inversions is odd, and otherwise 0, 0 and 1, 1.
  4. In all remaining cases, we can get all possible combinations of parities.

Let’s suppose that we can’t get 1, 1, combining the parities from all these blocks. There can’t be any block of type 4). If there are at least two blocks of type 2), we will also be able to obtain any combination of parities. If there is at least one block of type 2) and at least one block of type 3), we will also be able to obtain all combinations of parities. So, we have three possibilities:

  • We have only blocks of type 1)
  • We have some number of blocks of types 3) (and some of type 1)), and the total number of blocks of type 3) with odd number of inversions is odd.
  • We have a single block of type 2) (and some blocks of type 1) ).

It’s easy to see that these are precisely the types given at the beginning of this post.

1 Like