EP Ethan Pham Project Euler, competitive programming, and notes on the things I keep studying.
ICPC 2014
ICPC 2014

A. Baggage

An airline has two flights leaving at about the same time from ICPCity, one to city B and one to city A. The airline also has n counters where passengers check their baggage. At each counter there is a pair of identical baggage bins, one for city B and one...

Updated May 21, 2026
Track ICPC
Year 2014
Statement Text + PDF
TeXC++Statement textStatement PDF
Problem statement

Problem Statement

Formatted from the contest statement text, with sample tests broken out into copyable blocks.

Statement text Statement PDF
Time limit 1 second

An airline has two flights leaving at about the same time from ICPCity, one to city B and one to city A. The airline also has n counters where passengers check their baggage. At each counter there is a pair of identical baggage bins, one for city B and one for city A. Just before the flights depart, each pair of baggage bins is moved by a motorized cart to a sorting area. The cart always moves two bins at a time, one for city B and one for city A. After all the bins have been moved, they line up in the sorting area like this:

B A B A B A ... B A

That is, there are 2n baggage bins in a row, starting with a bin for city B, then one for city A, and so forth. The task now is to reorder them so all the baggage bins for city A precede the baggage bins for city B. Then the bins can be loaded on the appropriate aircraft. The reordering is done by moving pairs of adjacent baggage bins (not necessarily B then A), again via the motorized cart. For proper balance, the cart must always carry two bins, never just one. A pair of bins must always be moved to an empty space that is at least two bins wide. On the left of the first bin are some empty spaces that can be used as needed during the reordering. When the reordering process begins, the bin locations are numbered from 1 (initially containing the leftmost B baggage bin) to 2n (initially containing the rightmost A baggage bin). There are 2n initially empty spaces to the left of the bins, numbered from 0 to −2n + 1, as shown in Figure A.1 for the case n = 4.

−7     −6     −5    −4    −3    −2     −1    0     1    2     3     4    5     6     7    8
Figure A.1: Initial configuration of bins and empty spaces for n = 4

Given n, find a shortest sequence of moves that will reorder the bins so that all the A bins are to the left of all the B bins. At the end of the process, it is possible that the leftmost A bin is at some location other than 1, but the bins must be adjacent in a sequence of 2n locations.

Input

The input consists of a single test case, which consists of the integer n (3 ≤ n ≤ 100).

Output

Display a shortest sequence of moves that will correctly reorder the bins. Each move is of the form “f to t”, where f and t are integers representing the movement of the bins in locations f and f + 1 to locations t and t + 1. If multiple solutions are possible, display any one of them.

Sample Tests

Sample 1
Sample Input 
5
Sample Output 
8   to   -1
3   to   8
6   to   3
0   to   6
9   to   0
Sample 2
Sample Input 
8
Sample Output 
10 to -1
3 to 10
14 to 3
7 to 14
0 to 7
11 to 0
4 to 11
15 to 4
Editorial

Editorial

The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.

Raw TeX

Key Observations

  • Write the structural observations that make the problem tractable.

  • State any useful invariant, monotonicity property, graph interpretation, or combinatorial reformulation.

  • If the constraints matter, explain exactly which part of the solution they enable.

Algorithm

  1. Describe the data structures and the state maintained by the algorithm.

  2. Explain the processing order and why it is sufficient.

  3. Mention corner cases explicitly if they affect the implementation.

Correctness Proof

We prove that the algorithm returns the correct answer.

Lemma 1.

State the first key claim.

Proof.

Provide a concise proof.

Lemma 2.

State the next claim if needed.

Proof.

Provide a concise proof.

Theorem.

The algorithm outputs the correct answer for every valid input.

Proof.

Combine the lemmas and finish the argument.

Complexity Analysis

State the running time and memory usage in terms of the input size.

Implementation Notes

  • Mention any non-obvious implementation detail that is easy to get wrong.

  • Mention numeric limits, indexing conventions, or tie-breaking rules if relevant.

Implementation

Code

C++ solution used for this page.

C++

Clean code view with a raw-file link when you want the original source.

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

namespace {

void solve() {
    // Fill in the full solution logic for the problem here.
}

}  // namespace

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
    return 0;
}
Resources

Source Files and Assets

Raw files are still available here when you want the original TeX, C++, or statement assets.

Show raw files
TeX write-upcompetitive_programming/icpc/2014/A-baggage/solution.texC++ implementationcompetitive_programming/icpc/2014/A-baggage/solution.cppStatement textcompetitive_programming/icpc/2014/A-baggage/statement.txtStatement PDFcompetitive_programming/icpc/2014/A-baggage/statement.pdfMetadatacompetitive_programming/icpc/2014/A-baggage/meta.jsonYear packetcompetitive_programming/icpc/2014/contest_problems.pdf