Car Parking
Problem Statement A parking lot has N spaces. Cars are initially arranged in some configuration (a permutation with one empty space, denoted 0), and must be rearranged to a target configuration. Each move drives one c...
Problem Statement
Rendered from the "Problem Statement" section in the LaTeX write-up.
A parking lot has $N$ spaces. Cars are initially arranged in some configuration (a permutation with one empty space, denoted 0), and must be rearranged to a target configuration. Each move drives one car into the (unique) empty space. Find the minimum number of moves.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Solution Approach
Permutation Cycle Decomposition
The initial and target configurations define a permutation $\pi$: for each space $i$, the item currently at $i$ needs to move to some target position. Decompose $\pi$ into cycles.
A fixed point (cycle of length 1) costs 0 moves.
A cycle of length $k$ containing the empty space costs $k - 1$ moves. The empty space can rotate the cycle in $k - 1$ steps.
A cycle of length $k$ not containing the empty space costs $k + 1$ moves: 1 move to bring the empty space into the cycle, then $k$ moves to rotate all $k$ elements into place (the empty space ends up back outside the cycle).
Proof (Proof of the $k + 1$ bound).
To rotate a cycle of length $k$ that does not contain the empty space, we must first move the empty space to some position in the cycle (1 move), then perform $k$ moves to shift each element one position along the cycle. Total: $k + 1$. This is optimal because each of the $k$ misplaced elements must move at least once, and one additional move is needed to bring the empty space into the cycle.
Algorithm
Build the permutation from initial to target configuration.
Find all cycles using standard cycle-finding.
For each non-trivial cycle ($k \ge 2$): add $k - 1$ if it contains the empty space, or $k + 1$ otherwise.
C++ Solution
#include <cstdio>
#include <vector>
#include <map>
using namespace std;
int main() {
int N;
scanf("%d", &N);
vector<int> initial(N + 1), target(N + 1);
int emptyPos = -1;
for (int i = 1; i <= N; i++) {
scanf("%d", &initial[i]);
if (initial[i] == 0) emptyPos = i;
}
for (int i = 1; i <= N; i++)
scanf("%d", &target[i]);
// Map each car to its target position
map<int, int> targetPos;
int emptyTarget = -1;
for (int i = 1; i <= N; i++) {
if (target[i] == 0) emptyTarget = i;
else targetPos[target[i]] = i;
}
// Build permutation: perm[i] = where the item at position i should go
vector<int> perm(N + 1);
for (int i = 1; i <= N; i++) {
if (initial[i] == 0)
perm[i] = emptyTarget;
else
perm[i] = targetPos[initial[i]];
}
// Find cycles and compute total moves
vector<bool> visited(N + 1, false);
int totalMoves = 0;
for (int i = 1; i <= N; i++) {
if (visited[i]) continue;
int len = 0;
bool containsEmpty = false;
int cur = i;
while (!visited[cur]) {
visited[cur] = true;
if (cur == emptyPos) containsEmpty = true;
len++;
cur = perm[cur];
}
if (len <= 1) continue; // fixed point
if (containsEmpty)
totalMoves += len - 1;
else
totalMoves += len + 1;
}
printf("%d\n", totalMoves);
return 0;
}Complexity Analysis
Time complexity: $O(N)$. Each position is visited exactly once during cycle detection.
Space complexity: $O(N)$ for the permutation and visited arrays.
Code
C++ solution used for this page.
// IOI 2000 - Car Parking
// Rearrange cars from initial to target configuration using one empty space.
// Each move drives a car into the empty space.
// Uses permutation cycle decomposition to count minimum moves.
// Cycle containing empty: (len - 1) moves. Other cycles of len >= 2: (len + 1) moves.
// Complexity: O(N) time, O(N) space.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
// initial[i] = car in space i (0 = empty)
// target[i] = car that should be in space i
vector<int> initial(N + 1), target(N + 1);
int emptyPos = -1;
for (int i = 1; i <= N; i++) {
cin >> initial[i];
if (initial[i] == 0) emptyPos = i;
}
for (int i = 1; i <= N; i++) {
cin >> target[i];
}
// Build permutation: where should the item at position i go?
// targetPos[car] = position where car belongs in target
unordered_map<int, int> targetPos;
int emptyTarget = -1;
for (int i = 1; i <= N; i++) {
if (target[i] == 0)
emptyTarget = i;
else
targetPos[target[i]] = i;
}
// perm[i] = j means the item at position i should go to position j
vector<int> perm(N + 1);
for (int i = 1; i <= N; i++) {
if (initial[i] == 0)
perm[i] = emptyTarget;
else
perm[i] = targetPos[initial[i]];
}
// Find cycles and compute total moves
vector<bool> visited(N + 1, false);
int totalMoves = 0;
for (int i = 1; i <= N; i++) {
if (visited[i]) continue;
int len = 0;
bool containsEmpty = false;
int cur = i;
while (!visited[cur]) {
visited[cur] = true;
if (cur == emptyPos) containsEmpty = true;
len++;
cur = perm[cur];
}
if (len == 1) continue; // fixed point, no moves needed
if (containsEmpty)
totalMoves += len - 1;
else
totalMoves += len + 1;
}
cout << totalMoves << "\n";
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.