Remove Repeated Rally Stages
National Olympiad — National round (2015 season)
Submission name: rally.cpp
Problem summary
A rally route is a sequence of stage lengths. If a length occurs more than twice in the original route, retain only its first occurrence. Lengths appearing once or twice keep all their occurrences. Preserve route order.
Input
n followed by n stage lengths.
Output
The retained lengths in input order, separated by spaces.
Constraints
10 ≤ n ≤ 1000; each stage length is 1–100.
Worked example
An independently prepared example for this explanation.
Input
10 20 10 20 30 5 20 5 50 5 50
Output
20 10 30 5 50 50
Solution analysis
- The decision depends on the total frequency in the original route, so count every length before producing output. A frequency array of size 101 is sufficient.
- Scan the stored route again. Output every occurrence of a length whose total frequency is at most two. For a higher frequency, output only its first encounter, tracked by a seen array.
- In the sample, 20 and 5 each occur three times, so only their first occurrences remain. Length 50 occurs exactly twice, so both 50s remain. The other lengths also stay in their original order.
Why it works
For every value occurring at most twice, the algorithm retains all occurrences as required. For every value occurring more often, the seen test retains exactly its first occurrence. Since output follows the original scan order, all retained stages have the required relative order.
Watch out. Do not keep two copies when frequency exceeds two: keep exactly one. Do not remove the second copy of a value occurring exactly twice.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> route(n);
int frequency[101] = {};
for (int &length : route) {
cin >> length;
++frequency[length];
}
bool seen[101] = {};
bool first = true;
for (int length : route) {
// Values occurring more than twice retain only their first occurrence.
if (frequency[length] <= 2 || !seen[length]) {
if (!first) {
cout << ' ';
}
cout << length;
first = false;
}
seen[length] = true;
}
cout << '\n';
return 0;
}