Rotate the Apartments
National Olympiad — National round (2023 season)
Submission name: skyscraper.cpp
Problem summary
N rectangular apartments are stacked in floor order. Each upper rectangle must fit inside the rectangle directly below it, without changing the given floor order. You may swap a rectangle’s two dimensions at the cost of one conversation. Minimize conversations and report the rotated floors, or state that construction is impossible.
Source clarification. In the first official sample, the printed answer rotates floors 2 and 4 while its explanation names floors 1 and 4. Both sets are optimal and valid; the shorter second sample is reproduced here.
Input
N, then N pairs a[i],b[i] from the bottom floor upward.
Output
The minimum conversation count and a second line of rotated floor numbers, or Impossible!. Any optimal set is accepted.
Constraints
2 ≤ N ≤ 100000; 1 ≤ a[i],b[i] ≤ 1000000.
Worked example
An independently prepared example for this explanation.
Input
2 2 4 3 1
Output
1 2
Solution analysis
- Each floor has only two orientations: unchanged with cost zero, or swapped with cost one. Keep dp[i][orientation], the minimum cost for floors through i with that last orientation.
- For every previous and current orientation, check both dimensions of the upper floor against those below. If it fits, update the cost and remember which previous orientation produced it. No positions or offsets are needed: axis-aligned rectangles fit exactly when both dimension inequalities hold.
- In the sample, 3×1 does not fit in 2×4, but its rotated 1×3 orientation does, at cost one. After processing all floors, choose the cheaper reachable last orientation and follow stored parents backward to recover the rotated floors.
Why it works
For a fixed current orientation, the only constraint involving earlier floors is its fit with the previous floor. The recurrence tries every legal predecessor and adds exactly the current rotation cost. Induction gives optimal states, and backtracking recovers a construction attaining the best final state.
Watch out. Do not greedily choose one floor’s orientation: it can affect future feasibility. Print the exact Impossible! spelling when both final states are unreachable.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <vector>
#include <array>
using namespace std;
int main() {
int n;
cin >> n;
vector<array<int, 2>> side(n), parent(n);
for (auto &dimensions : side) {
cin >> dimensions[0] >> dimensions[1];
}
const int infinity = n + 1;
array<int, 2> dp = {0, 1};
for (int floor = 1; floor < n; floor++) {
array<int, 2> next = {infinity, infinity};
for (int current = 0; current < 2; current++) {
for (int previous = 0; previous < 2; previous++) {
bool fits = side[floor][current] <= side[floor - 1][previous]
&& side[floor][1 - current] <= side[floor - 1][1 - previous];
if (fits && dp[previous] + current < next[current]) {
next[current] = dp[previous] + current;
// Store the predecessor orientation for optimal reconstruction.
parent[floor][current] = previous;
}
}
}
dp = next;
}
int orientation = dp[0] < dp[1] ? 0 : 1;
if (dp[orientation] >= infinity) {
cout << "Impossible!\n";
return 0;
}
cout << dp[orientation] << '\n';
vector<int> rotated;
for (int floor = n - 1; floor >= 0; floor--) {
if (orientation == 1) {
rotated.push_back(floor + 1);
}
if (floor > 0) {
orientation = parent[floor][orientation];
}
}
for (int i = 0; i < static_cast<int>(rotated.size()); i++) {
if (i > 0) {
cout << ' ';
}
cout << rotated[i];
}
cout << '\n';
}