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]| ≠ 1for everyi.Print any valid arrangement, or
-1if none exists. The input hasttest cases, each a singlen.
1 ≤ t ≤ 10^4,1 ≤ n ≤ 2·10^5, the sum ofnover all tests is at most2·10^5.
| Sample input | One valid output |
|---|---|
3521 |
1 3 5 2 4-11 |
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)fillspwith 1, 2, ..., n.next_permutationrearrangespinto the next order in dictionary (lexicographic) order and returnsfalseafter 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 2and2 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
- Brute force tiny n and print the answers. The slow code is a microscope, not a submission.
- Stare at the answers until a simple rule appears (odds/evens, a zigzag, a reversed block).
- Write a checker: is an output valid? Checking is easy even when building is hard.
- Stress test the rule on every n you can (here 1..2000), comparing -1 cases with the brute force for tiny n.
- 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
-
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. -
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. -
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. -
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. -
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
- What makes a problem "constructive", and how is it judged? (Any valid output is accepted; a checker program tests the rules.)
- 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.)
- 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.)
- How would you test a construction before submitting? (A checker plus a stress loop over many n, with the brute force confirming -1 cases.)
- 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);
-1only for n = 2 and 3, and n = 1 is1. - The recipe: brute force small → find a pattern → checker → stress test → prove the impossible cases.
Next episode: ad-hoc and observation problems.