Constructive Algorithms

A constructive algorithm requires you to build a specific example that satisfies a set of rules, or prove that no such example exists.

Unlike standard algorithmic problems where you might calculate a shortest path or a maximum profit, constructive problems ask for the object itself (e.g., “Print an array that…”).

Let’s look at a few examples immediately to see how this works.

Example Problems

Zero Sum Array

Given an integer \(N\), print \(N\) distinct integers such that their sum is equal to \(0\).

Solution

The Construction: Instead of searching for random numbers, we can construct the answer using a fixed pattern.

We know that for any number \(x\), the sum \(x + (-x) = 0\). We can simply output pairs of positive and negative numbers. If \(N\) is odd, we add \(0\) to the mix.

\(N = 1\): 0
\(N = 2\): 1 -1
\(N = 3\): 1 -1 0
\(N = 4\): 1 -1 2 -2 0

#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;

    for (int i = 1; i <= n / 2; i++) {
        cout << i << " " << -i << " ";
    }

    if (n % 2 != 0) cout << 0;
    cout << endl;
}

Anti-Identity Permutation

Construct a permutation of length \(N\) (1-based index) such that for every index \(i\), \(A[i] \neq i\).

For example, if \(N=3\), [1, 2, 3] is invalid because \(1\) is at index \(1\). [2, 3, 1] is valid.

Solution

If we simply rotate the array by one position, no number will remain in its original spot.

Formula would then be \(A[i] = i+1\), for all \(i < N\) and \(A[N] = 1\).

\(N=3\): 2 3 1
\(N=4\): 2 3 4 1
\(N=5\): 2 3 4 5 1

Note: For \(N=1\), it is impossible to place \(1\) anywhere other than index \(1\), so no solution exists.

Chessboard Domineering

You have a standard \(8 \times 8\) chessboard with two opposite corners removed (leaving 62 squares). Find a way to cover the entire board with \(2 \times 1\) dominoes?

Solution

We tricked you!

Sometimes the “Construction” is proving that the task is impossible.

A standard chessboard has 32 Black and 32 White squares. Opposite corners are always the same color. If we remove two opposite corners (e.g., white), we are left with 32 Black and 30 White squares. A single domino covers exactly 1 Black and 1 White square. To cover the board, we would need equal counts of Black and White squares. Conclusion: It is impossible.

This is not a regular practice, but it can occur from time to time. The lesson to be learned here is that it can be much easier to solve the task by pen and paper and thinking outside of the box, then to try and code stuff.

How to solve contructive problems?

Now that you’ve seen what these problems are, here is how to tackle them. Unlike Graph Theory or DP, you don’t use standard algorithms like Dijkstra. You use logic and observation.

Try Small N

This is the most important strategy. If the problem asks for a solution for \(N=100000\), do not guess the complex formula immediately. Grab a pen and solve it for \(N=1, 2, 3, 4\). Many constructive problems are solved by spotting a pattern in small cases.

Parity (Odd vs Even)

Many constructions rely on the properties of even and odd numbers (Odd + Odd = Even).

Example: If a problem asks “Can you equalize these numbers by adding 2?”, check the parity. If one number is odd and the other is even, they will never meet, because adding 2 never changes parity.

Pigeonhole Principle

If you have \(N\) items and \(N-1\) boxes, at least one box must contain 2 items. This is frequently used to prove that a solution exists (or proves impossibility).

Construction by Induction

Ask yourself: “If I have a valid answer for \(N\), can I easily add one element to make it valid for \(N+1\)?” This allows you to build the answer incrementally.

Check the “Worst Case”

Sometimes the answer is trivial. Before overthinking, check if the answer is simply:

The sorted array 1, 2, 3...
The reverse sorted array N, N-1, N-2...
All zeros or all ones.