Official Editorial

Explanation

First we can solve an easier version of the problem where all the blocks are distinct.

Notice that if we process the blocks from largest to smallest, we can incrementally fill the even positions, starting from the bottom and working our way up to the top. In addition, we can fill in the odd positions with whatever blocks we don't use in the even positions.

We can do this problem using dynamic programming. Let $dp[i][j]$ be the number of ways to use the first $i$ blocks and place $j$ of those in the $j$ bottommost even positions (and $i - j$ of them in the odd position).

There are two transitions.

1. To $dp[i + 1][j + 1]$. If we add another even block, then there is only one place to put it.

2. To $dp[i + 1][j]$. In this case we add the block to an odd position.

Notice that we must place a block in between already placed larger blocks because of the condition that an even block is greater than its two neighboring odd blocks and later placed blocks will always be smaller. This means that there will be $\max(0, j - 1)$ positions to insert the block. When all $\frac{n}{2}$ even blocks are placed you can also insert it at the top of the stack. We also have to subtract out the $i - j$ blocks that are already placed in odd positions.

When the blocks can be of the same size, let's process them in groups of blocks that are all the same size.

There are still two possible transitions. Either we put one block into an even position and the remaining into odd or all of them into odd positions.

To determine the number of ways to insert the blocks into the odd positions, we can evaluate ${\text{number of open spots} \choose \text{number of spots that we want to fill}}$.

Our final answer will be $dp[n][\frac{n}{2}]$.

Time Complexity: $\mathcal{O}(n^2)$

Implementation

Copy
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const ll MOD = 998244353;
const int MAXN = 5000;

// https://usaco.guide/gold/combo?lang=cpp
long long fac[MAXN + 1];