Inversion Graph Coloring (Easy Version)

A subsequence is good iff its inversion graph is bipartite. That sounds graphy, but the clean way in is much simpler.

If two indices have the same color, they are not allowed to be an inversion. So within each color, values must appear in nondecreasing order. Therefore:

A subsequence is good iff it can be partitioned into two nondecreasing subsequences.

By the standard chain-cover fact, that is equivalent to:

The subsequence has no strictly decreasing subsequence of length $3$.

One direction is immediate: if you split the sequence into two nondecreasing parts, then any strictly decreasing triple would need three different colors. Bad news, there are only two colors.

The other direction is the usual greedy/patience-sorting argument: if the longest strictly decreasing subsequence has length at most $2$, then two nondecreasing piles are enough.

So now the problem is: count subsequences of $a$ that avoid a pattern

$$i < j < k, \qquad a_i > a_j > a_k.$$

No graph coloring needed anymore. The graph was wearing a fake mustache.

State

Scan the original array from left to right and build subsequences by deciding whether to take each element.

For a currently built subsequence with no decreasing triple, define:

• $x$: the smallest possible last value of a strictly decreasing subsequence of length $1$ inside it.
• $y$: the smallest possible last value of a strictly decreasing subsequence of length $2$ inside it.

If such a decreasing subsequence does not exist, use sentinel value $n+1$.

The empty subsequence starts at:

$$(x,y) = (n+1,n+1).$$

Smaller ending values are more dangerous: a future value $v$ extends a decreasing pair exactly when that pair ends at a value greater than $v$.

Transition

Suppose the next array value is $v$.

For every state $(x,y)$, we can always skip $v$.

If we take $v$:

• If $y > v$, then some decreasing pair can be followed by $v$, creating a decreasing triple. Invalid.
• Otherwise, if $x > v$, then $v$ extends a length-$1$ decreasing subsequence into a length-$2$ one, so go to $(x,v)$.
• Otherwise, $v$ creates no new danger, so stay at $(x,y)$.

DP

Let $dp[x][y]$ be the number of ways to obtain state $(x,y)$ after processing a prefix.

Initialize:

$$dp[n+1][n+1] = 1.$$

For each value $v$, copy all states for the skip option, then add the valid take transitions.

At the end, every state is a valid good subsequence, including the empty one, so the answer is:

$$\sum_{x=1}^{n+1}\sum_{y=1}^{n+1} dp[x][y].$$

Correctness Proof

A subsequence is good iff it can be split into two nondecreasing subsequences: same-colored elements cannot form inversions, and two nondecreasing parts can be colored red/blue directly.

A sequence can be split into two nondecreasing subsequences iff it has no strictly decreasing subsequence of length $3$. A decreasing triple needs three different nondecreasing parts, while the greedy pile process uses at most two piles exactly when no third decreasing layer exists.

The DP invariant is: after processing a prefix, $dp[x][y]$ counts exactly the valid subsequences whose best length-$1$ and length-$2$ decreasing-subsequence ending values are $(x,y)$.

The initial empty subsequence satisfies this. Skipping preserves the state. Taking $v$ is rejected exactly when it creates a decreasing triple, and otherwise updates the best length-$2$ ending value precisely when $x>v$. Therefore every valid subsequence is counted once, and no invalid subsequence is counted.

So the DP counts exactly the good subsequences.

Complexity

There are $O(n^2)$ states and $n$ elements, so the time complexity is $O(n^3)$ with $O(n^2)$ memory. For $n\le 300$, that is comfortably fine.