Cut and Reorder the Strip
National Olympiad — Regional round (2021 season)
Submission name: cuts.cpp
Problem summary
A strip contains a permutation of 1 to N. Cut only between numbers and reorder the resulting pieces without reversing them to obtain increasing order. Find the minimum number of cuts and the largest piece length among those optimal cuts.
Input
N and the N numbers in strip order.
Output
The minimum cuts and the longest resulting piece length.
Constraints
0 < N < 1,000,000. The statement requires at most 1 MB memory.
Worked example
An independently prepared example for this explanation.
Input
12 12 1 2 4 5 6 7 10 11 3 8 9
Output
5 4
Solution analysis
- Inside a piece, adjacent numbers keep their order and must become adjacent in the final sorted strip. Therefore a pair can remain uncut exactly when the second number is the first plus one.
- Scan once, cutting whenever current != previous+1. Track the current run length and its maximum. There is no need to store the permutation, which respects the small memory limit.
- The sample splits into 12 | 1 2 | 4 5 6 7 | 10 11 | 3 | 8 9. Five mandatory boundaries produce six pieces; the longest has four numbers.
Why it works
Every nonconsecutive adjacent pair must be separated because an uncut piece would preserve that invalid adjacency. Keeping every consecutive pair intact forms increasing consecutive runs, which can be reordered by their starting values to recover 1 through N. Thus all and only mandatory cuts are used.
Watch out. A merely increasing pair such as 2,4 still needs a cut. For N = 1 output 0 1.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, previous;
cin >> n >> previous;
int cuts = 0;
int run = 1;
int longest = 1;
for (int i = 1; i < n; i++) {
int current;
cin >> current;
// Only consecutive increasing values can stay in one piece.
if (current == previous + 1) {
run++;
} else {
cuts++;
run = 1;
}
longest = max(longest, run);
previous = current;
}
cout << cuts << ' ' << longest << '\n';
}