Stacking Cards
National Olympiad — Regional round (2017 season)
Submission name: cards.cpp
Problem summary
Cards appear in a fixed row. Each has two side lengths. A card may be rotated and placed on the preceding card if both its sides fit within that card. Find the longest contiguous section in which every card after the first fits on its predecessor.
Input
N, followed by N pairs of side lengths.
Output
The maximum number of cards in a valid contiguous section.
Constraints
1 < N < 100000; each side is between 1 and 1000000.
Worked example
An independently prepared example for this explanation.
Input
6 3 4 5 3 3 3 2 3 3 2 7 7
Output
4
Solution analysis
- Normalize every card: store its shorter side first and longer side second. Rotation then disappears from the test: the next card fits exactly when both normalized dimensions are no larger than the previous dimensions.
- Track the length of the valid section ending at the current card. Extend it when the new card fits; otherwise reset it to 1. Remember the largest length seen. Only the preceding card is needed.
- In the sample, (3,4) cannot support (3,5), so a new section begins at card 2. Cards (3,3), (2,3), and (2,3) fit consecutively, giving length 4. The final (7,7) breaks the section.
Why it works
For two rectangles with parallel sides, sorting their dimensions makes componentwise comparison necessary and sufficient for a fitting orientation. Any valid section ending at the current card extends the previous valid ending section if the pair fits; otherwise it can contain only the current card. The recurrence therefore computes every longest ending section, and their maximum is the answer.
Watch out. The section must be contiguous. Equality is allowed, and a rotation can make a card fit.
Commented C++17 solution
An independently written complete program with standard headers.
#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
int previousShort, previousLong;
cin >> previousShort >> previousLong;
if (previousShort > previousLong) {
swap(previousShort, previousLong);
}
int current = 1;
int best = 1;
for (int i = 1; i < n; ++i) {
int a, b;
cin >> a >> b;
if (a > b) {
swap(a, b);
}
// Sorted side pairs make rotation-independent fitting a componentwise test.
if (a <= previousShort && b <= previousLong) {
++current;
} else {
current = 1;
}
best = max(best, current);
previousShort = a;
previousLong = b;
}
cout << best << '\n';
}