Misplaced Number Cards
National Olympiad — Municipal round (2021 season)
Submission name: order.cpp
Problem summary
A permutation of 1 to N was originally in increasing order. Find the smallest and largest values on cards that are no longer in their original positions. If every card is correctly placed, print 0 0.
Input
N followed by the N values in their current order.
Output
The smallest and largest misplaced values, or 0 0.
Constraints
2 < N < 1000. The values form a permutation of 1 to N.
Worked example
An independently prepared example for this explanation.
Input
5 1 5 3 4 2
Output
2 5
Solution analysis
- A card with value v belongs at one-based position v. While reading position i, it is misplaced exactly when v != i.
- Update a running minimum and maximum only for misplaced values. Use a maximum of zero as the sentinel that no misplaced card has been found.
- For 1,5,3,4,2, the misplaced cards carry 5 and 2, so the extremes are 2 and 5. In a fully sorted permutation no update occurs, and the required pair is 0 0.
Why it works
The comparison selects exactly the cards whose current positions differ from their prescribed positions. The running extremes over those selected values are therefore the requested minimum and maximum; the sentinel handles the empty selection.
Watch out. Use one-based positions for the comparison. Report values, not the number of misplaced cards.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
int minimum = n + 1;
int maximum = 0;
for (int position = 1; position <= n; position++) {
int value;
cin >> value;
// Value v belongs at the one-based position v.
if (value != position) {
minimum = min(minimum, value);
maximum = max(maximum, value);
}
}
if (maximum == 0) {
minimum = 0;
}
cout << minimum << ' ' << maximum << '\n';
}