SyntaxPilot
Courses/Competitive Programming/Lesson 15

Competitive Programming · Lesson 15 of 90 · 11 min

Constructive problems: build any valid answer

queued

These are the notes for Competitive Programming episode 15. Some contest problems don't ask for a number: they ask you to build something (a permutation, an array, a grid) and accept any valid one. These are constructive problems. The original problem Quiet Row asks for a seating order of roll numbers 1..n where no two neighbours have consecutive numbers. Trying every order gets Time Limit Exceeded, but the same brute force, run on tiny n, prints answers we can stare at. A guessed pattern (odds, then evens) passes the sample, and a stress test with our own checker catches it failing at n = 4. Evens first fixes it, and every impossible case is proved. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.

The real-life hook: the exam-hall seating plan

A teacher seats students with roll numbers 1 to n in one long row. Students with consecutive roll numbers sat together all year and chat, so roll 3 must not sit next to roll 4. The teacher needs one plan that keeps every such pair apart, not the best plan and not the number of plans. And checking a plan is easy: the invigilator walks the row and looks at each pair of neighbours. Finding a plan can be hard; checking one is easy. That asymmetry is the heart of constructive problems.

The problem: Quiet Row

Problem O · Quiet Row (written for this course). Arrange the numbers 1..n in a row, each exactly once (a permutation p), so that no two neighbours are consecutive numbers:

|p[i] − p[i+1]| ≠ 1 for every i.

Print any valid arrangement, or -1 if none exists. The input has t test cases, each a single n.

1 ≤ t ≤ 10^4, 1 ≤ n ≤ 2·10^5, the sum of n over all tests is at most 2·10^5.

Sample input One valid output
3
5
2
1
1 3 5 2 4
-1
1

Because many outputs are correct, the judge grades with a checker (special judge), not by comparing files. 2 4 1 3 5 is also accepted for n = 5.

Brute force: try every order (Time Limit Exceeded)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> p(n);
        iota(p.begin(), p.end(), 1);
        bool found = false;
        do {
            bool ok = true;
            for (int i = 0; i + 1 < n; i++)
                if (abs(p[i] - p[i + 1]) == 1) ok = false;
            if (ok) { found = true; break; }
        } while (next_permutation(p.begin(), p.end()));
        if (!found) { cout << -1 << '\n'; continue; }
        for (int x : p) cout << x << ' ';
        cout << '\n';
    }
    return 0;
}
  • iota(p.begin(), p.end(), 1) fills p with 1, 2, ..., n.
  • next_permutation rearranges p into the next order in dictionary (lexicographic) order and returns false after the last one.

Output on the sample: 1 3 5 2 4 / -1 / 1 (matches the sample exactly).

On n = 20 it got Time Limit Exceeded: every order starting with 1 2 is bad, and there are 18! ≈ 6.4·10^15 of them before the second number even changes.

The brute force as a tool

The brute force is slow but correct, and for tiny n it is instant. Asking it for n = 1..8 (input 8 then 1..8) printed:

1 
-1
-1
2 4 1 3 
1 3 5 2 4 
1 3 5 2 4 6 
1 3 5 2 6 4 7 
1 3 5 2 6 8 4 7 
n Brute-force answer What we notice
1 1 no neighbours, always fine
2, 3 -1 impossible
4 2 4 1 3 evens first (we ignored this at first!)
5 1 3 5 2 4 odds, then evens
6 1 3 5 2 4 6 odds, then evens

Inside a block of odd numbers (or even numbers) neighbours differ by 2, never 1. So the guess: odds, then evens.

Checkers: many right answers

In an exam On the judge
Maths paper: one answer key; the examiner compares Normal problem: your output must equal the expected output
Seating plan: many good plans, no single key Constructive problem: many valid outputs
The invigilator checks the rules pair by pair Checker / special judge: a program that tests validity
Practise with your own invigilator before the exam Write your own checker and stress test

The guess: odds, then evens (passes the sample)

        if (n == 2 || n == 3) { cout << -1 << '\n'; continue; }
        for (int x = 1; x <= n; x += 2) cout << x << ' ';
        for (int x = 2; x <= n; x += 2) cout << x << ' ';
        cout << '\n';

Output on the sample: 1 3 5 2 4 / -1 / 1. Exactly the sample, and still wrong.

The stress test (finds n = 4)

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

bool good(const vector<int>& p) {
    for (int i = 0; i + 1 < (int)p.size(); i++)
        if (abs(p[i] - p[i + 1]) == 1) return false;
    return true;
}

bool bruteHas(int n) {
    vector<int> p(n);
    iota(p.begin(), p.end(), 1);
    do if (good(p)) return true;
    while (next_permutation(p.begin(), p.end()));
    return false;
}

vector<int> solve(int n) {
    if (n == 2 || n == 3) return {};
    vector<int> p;
    for (int x = 1; x <= n; x += 2) p.push_back(x);
    for (int x = 2; x <= n; x += 2) p.push_back(x);
    return p;
}

int main() {
    for (int n = 1; n <= 2000; n++) {
        vector<int> p = solve(n), s = p;
        sort(s.begin(), s.end());
        bool perm = (int)s.size() == n;
        for (int i = 0; perm && i < n; i++) perm = s[i] == i + 1;
        if (p.empty() && n <= 9 && bruteHas(n)) {
            cout << "n = " << n << ": -1, but brute found one\n";
            return 0;
        }
        if (!p.empty() && (!perm || !good(p))) {
            cout << "n = " << n << ": BAD";
            for (int x : p) cout << ' ' << x;
            cout << '\n';
            return 0;
        }
    }
    cout << "all n from 1 to 2000: OK\n";
}

Output:

n = 4: BAD 1 3 2 4

Why n = 4 breaks. Inside each block the gap is 2, so only the junction (where the blocks meet) can fail. Odds-then-evens puts the largest odd next to 2; when the largest odd is 3 (n = 4), the gap is 1.

The fix: evens, then odds. Now the junction puts the largest even number next to 1. For n ≥ 4 the largest even is at least 4, so the gap is at least 3. Swapping the two loops in solve and re-running printed:

all n from 1 to 2000: OK

Impossible cases: prove every -1

  • n = 2: the only orders are 1 2 and 2 1; 1 and 2 are always neighbours.
  • n = 3: the number 2 has at least one neighbour, and it is 1 or 3. Both differ by 1.
  • n = 1: one number, no neighbours: the answer is 1, not -1.

Changing the impossible check to if (n <= 3) return {}; makes the stress test print:

n = 1: -1, but brute found one

The accepted solution

Input Output
the sample (3 / 5 / 2 / 1) 2 4 1 3 5 / -1 / 1
4 / 1 / 2 / 3 / 12 1 / -1 / -1 / 2 4 6 8 10 12 1 3 5 7 9 11

2 4 1 3 5 differs from the sample's 1 3 5 2 4 and is still accepted: the checker tests the rule, not the exact text.

Solutions in C++, Java and Python

C++

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        if (n == 2 || n == 3) { cout << -1 << '\n'; continue; }
        for (int x = 2; x <= n; x += 2) cout << x << ' ';
        for (int x = 1; x <= n; x += 2) cout << x << ' ';
        cout << '\n';
    }
    return 0;
}

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();
        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine().trim());
            if (n == 2 || n == 3) { sb.append("-1\n"); continue; }
            for (int x = 2; x <= n; x += 2) sb.append(x).append(' ');
            for (int x = 1; x <= n; x += 2) sb.append(x).append(' ');
            sb.append('\n');
        }
        System.out.print(sb);
    }
}

Python

import sys

def main():
    data = sys.stdin.buffer.read().split()
    t = int(data[0])
    out = []
    for i in range(1, t + 1):
        n = int(data[i])
        if n in (2, 3):
            out.append("-1")
        else:
            out.append(" ".join(map(str, list(range(2, n + 1, 2)) + list(range(1, n + 1, 2)))))
    print("\n".join(out))

main()

All three print 2 4 1 3 5 / -1 / 1 on the sample (Java and Python checked with the same inputs; Python joins without the trailing space, which judges ignore).

The constructive recipe

  1. Brute force tiny n and print the answers. The slow code is a microscope, not a submission.
  2. Stare at the answers until a simple rule appears (odds/evens, a zigzag, a reversed block).
  3. Write a checker: is an output valid? Checking is easy even when building is hard.
  4. Stress test the rule on every n you can (here 1..2000), comparing -1 cases with the brute force for tiny n.
  5. Prove every impossible case. Never trust the sample alone: your answer may differ from it and be right, or match it and be wrong.

Brute force vs construction

Brute force (every order) Construction (evens, then odds)
Work per test up to n! orders × n O(n)
n = 9 9! = 362,880 orders: fine as a tool instant
n = 20 18! ≈ 6.4·10^15 orders: TLE instant
sum n = 2·10^5 hopeless 2·10^5 numbers printed

Common mistakes (and the real messages)

Mistake What you see Why Fix
Odds, then evens stress test: n = 4: BAD 1 3 2 4 the junction puts 3 next to 2 evens first: the largest even sits next to 1
if (n <= 3) print -1 stress test: n = 1: -1, but brute found one one number has no neighbours -1 only for n = 2 and 3
Submitting the next_permutation brute force Time Limit Exceeded on n = 20 18! orders before an answer brute force only as a tool for n ≤ 9
Rewriting an answer because it differs from the sample a correct 2 4 1 3 5 "looks wrong" a checker accepts any valid output test with your own checker
A checker that only checks neighbours 1 3 5 2 2 would pass it is not a permutation also check each number appears once (the checker below prints BAD: not a permutation)

Mini project: a standalone checker

A checker reads n and an arrangement, and prints whether it is valid. This is what a judge's special judge does.

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

int main() {
    int n;
    cin >> n;
    vector<int> p(n);
    for (int &x : p) cin >> x;
    vector<int> s = p;
    sort(s.begin(), s.end());
    for (int i = 0; i < n; i++)
        if (s[i] != i + 1) {
            cout << "BAD: not a permutation\n";
            return 0;
        }
    for (int i = 0; i + 1 < n; i++)
        if (abs(p[i] - p[i + 1]) == 1) {
            cout << "BAD: " << p[i] << " next to " << p[i + 1] << '\n';
            return 0;
        }
    cout << "OK\n";
    return 0;
}
Input Output
5 2 4 1 3 5 OK
5 1 3 5 4 2 BAD: 5 next to 4
5 1 3 5 2 2 BAD: not a permutation
4 1 3 2 4 BAD: 3 next to 2

Extend it: read your solution's whole output for many test cases and check each line.

Practice

  1. Problem P. Build a permutation of 1..n with exactly k positions where p[i] > p[i+1] (0 ≤ k ≤ n − 1).

    Answer Print <code>k+1, k, ..., 1</code>, then <code>k+2, ..., n</code>. The reversed block has exactly k descents and the rest is increasing (and <code>1 < k+2</code> at the junction). Real output for <code>5 2</code>: <code>3 2 1 4 5</code>; for <code>4 0</code>: <code>1 2 3 4</code>; for <code>4 3</code>: <code>4 3 2 1</code>. Always possible, never -1.

  2. Write a checker and a stress test for Problem P.

    Answer The checker verifies a permutation (sort and compare with 1..n) and counts positions with <code>p[i] > p[i+1]</code>; it must equal k. Loop n from 1 to 500 and every k from 0 to n − 1.

  3. Change the rule to |p[i] − p[i+1]| ≥ 3. For which n is it impossible?

    Answer A brute force over all permutations for n = 1..9 finds answers for n = 1 and n ≥ 6, and none for n = 2, 3, 4, 5.

  4. Explain in one line why n = 3 is impossible.

    Answer The number 2 has at least one neighbour, and that neighbour is 1 or 3, both differing from 2 by 1.

  5. Why does evens-then-odds work for every n ≥ 4?

    Answer Inside each block the gap is 2. At the junction the largest even E (≥ 4) sits next to 1, a gap of E − 1 ≥ 3.

Quick quiz

Which one is not a valid answer for n = 5?

A. 2 4 1 3 5 · B. 1 3 5 4 2 · C. 3 5 1 4 2 · D. 5 3 1 4 2

Answer

B. 5 and 4 are neighbours. A, C and D are all valid, and none of them is the sample's answer.

Interview questions

  1. What makes a problem "constructive", and how is it judged? (Any valid output is accepted; a checker program tests the rules.)
  2. How do you find a construction when you don't see one? (Brute force tiny cases, print the answers, look for a pattern, then prove it.)
  3. Why is a sample that passes not enough here? (The sample is one or two cases; a pattern can break on a case you didn't look at, like n = 4.)
  4. How would you test a construction before submitting? (A checker plus a stress loop over many n, with the brute force confirming -1 cases.)
  5. How do you convince yourself that -1 is correct? (Prove impossibility by reasoning, and confirm with the brute force for small n.)

Glossary

Term Meaning Example
Constructive problem Build any object that satisfies the rules; any valid one is accepted Quiet Row
Permutation An arrangement of 1..n using each number exactly once 2 4 1 3 5
Checker / special judge A program the judge runs to test whether your output is valid checks neighbours and "each number once"
Brute force Try every possibility; slow but correct every order with next_permutation
next_permutation Rearranges a range into the next order in dictionary order; false after the last 1 2 3 → 1 3 2
Lexicographic (dictionary) order Order like words in a dictionary: compare the first differing position 1 3 2 before 2 1 3
iota Fills a range with consecutive values iota(p.begin(), p.end(), 1) → 1..n
Stress test Run your solution on many generated inputs and check each answer n = 1..2000
Junction The place where two blocks of a construction meet 4 next to 1 in 2 4 1 3
Impossible case (-1) An input with no valid answer; the problem asks you to print -1 n = 2, 3
Edge case A smallest or unusual input that breaks lazy code n = 1
Time Limit Exceeded (TLE) The program ran longer than allowed brute force on n = 20

Summary

  • A constructive problem asks you to build any valid answer; a checker grades it, so your output may differ from the sample.
  • Trying every order (next_permutation) is n!: TLE at n = 20.
  • On tiny n, the same brute force is a microscope: its answers suggested odds, then evens.
  • The sample passed, but a stress test with our own checker printed n = 4: BAD 1 3 2 4.
  • Evens, then odds works for every n ≥ 4 (largest even next to 1); -1 only for n = 2 and 3, and n = 1 is 1.
  • The recipe: brute force small → find a pattern → checker → stress test → prove the impossible cases.

Next episode: ad-hoc and observation problems.