Solving the decision problem

First let us consider how to solve the decision problem that does not require an example of how to place the cards. This problem can be solve with the following DP:

\(\text{dp}[i][j] :=\) \(1\) if we can obtain the sum \(j\) from cards \(1, \dots, i\); \(0\) otherwise

The initial state is \(\text{dp}[0][0] = 1, \text{dp}[0][x] = 0 \, (x \gt 0)\). The transition is as follows:

For all \(j\), initialize with \(\mathrm{dp}[i + 1][j] := 0\).

For all \(j\) such that \(\mathrm{dp}[i][j] = 1\), do the following, where the indices of \(a_i\) and \(b_i\) are \(0\)-based:

• If \(j + a_i \leq S\), let \(\mathrm{dp}[i + 1][j + a_i] := 1\).

• If \(j + b_i \leq S\), let \(\mathrm{dp}[i + 1][j + b_i] := 1\).

The complexity is \(O(NS)\).

For more details, see the past editorials for ABC.

Reference : ABC240C Editorial

Recovering the solution found by DP

In fact, we only need \(\text{dp}[i][j]\) to find an example of placements of the cards.

Focus on the last card. If \(\text{dp}[N][S] = 1\), at least one of \(\text{dp}[N - 1][S - a_N]\) and \(\text{dp}[N - 1][S - b_N]\) is \(1\). Here,

• If \(\text{dp}[N - 1][S - a_N] = 1\), we can obtain the sum \(S\) by placing the last card face-up and with an appropriate placements of cards \(1, \dots, N -1\).
• If \(\text{dp}[N - 1][S - b_N] = 1\), we can obtain the sum \(S\) by placing the last card face-down and with an appropriate placements of cards \(1, \dots, N -1\).

By repeating this step, we can determine the placements of cards \(N\), \(N-1\), \(\ldots\), successively in this order.

Sample code (C++)