Constructive problems ask you to output an object: a permutation, a matrix, a coloring, a sequence of moves. Ad-hoc problems ask you to notice a rule that is not a named algorithm — parity, pairing, 'put the biggest in the middle.' Both feel unfair until you have a small catalog of patterns. Then they become the problems you skip B for.
The Output section will say print any or if multiple answers, print any. That is the author telling you not to search the lexicographically smallest universe unless you need to. Build the dumbest legal object.
Patterns that show up constantly:
- Always possible if [parity / bound / count]. Sum even, n ≥ 3, at most one odd, max ≤ sum/2. Check the condition in O(n), then construct.
- Print any. Sorted order, identity permutation, 1 2 3 … n, all zeros except one cell. If it satisfies the predicate, ship it.
- Greedy construction. Place the largest remaining number in the leftmost legal slot; alternate small/large; pair i with i+k. You need a one-line reason it cannot get stuck if the condition held at the start.
- Build from the sample Note. Authors often paste the intended array in the note. Generalize that picture, do not copy the constants.
- Reduce to a known object. 'Make the array good' becomes 'split into two increasing sequences' or 'color a graph with 2 colors.' If you renamed it, you might already have BFS or two pointers.
- Not constructive: count of objects modulo 10⁹+7, minimum cost, unique lexicographically smallest when the checker is exact. Those are DP / greedy-with-proof / search.
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
// 1. Impossibility in O(n)
int odd = 0;
for (int x : a) odd += x & 1;
if (odd == 0) { cout << "-1\n"; return; }
// 2. Any valid construction — here: rotate so an odd lands at front
int p = 0;
while (a[p] % 2 == 0) p++;
rotate(a.begin(), a.begin() + p, a.end());
for (int i = 0; i < n; i++)
cout << a[i] << " \n"[i + 1 == n];
}Ad-hoc is the leftover bucket: no graph, no DP state, no named structure. Attack:
1. Small n brute. If n ≤ 8 in a subtask or n ≤ 10 in the statement, generate all answers and print them. The pattern is often obvious from the list (always even positions first, always n n-1 … 1 with one swap).
2. Parity and invariants. What cannot change? Sum mod 2, color of a chessboard, gcd of the array. If the operation adds 2, you cannot change parity — that is the -1 condition.
3. One extra degree of freedom. Many 'rearrange with constraint' problems become: sort, then swap two adjacent that are safe. Try identity, then one swap, then reverse.
4. Do not fight the bounds. n ≤ 100 means you may O(n³) search for a construction. n ≤ 2·10⁵ means the construction is a formula or a single pass. Same constraint muscle as Rank 1, now applied to builders instead of shortest paths.
When the construction is ugly to type, that is still a reason to stay if you already have the iff — it is implementation, not a missing idea. When you do not have the iff after 20 minutes, skip, as in the last lesson.
Checks 0/3