The Finish Order
National Olympiad — National round (2014 season)
Submission name: competition.cpp
Problem summary
Four runners numbered 1–4 start in number order at fixed time intervals and run at constant speeds. For each runner you know how many later starters overtook that runner. Reconstruct their finish order; there are no simultaneous finishes.
Input
Four counts, for runners 1, 2, 3 and 4.
Output
The four runner numbers in finish order.
Constraints
Exactly four runners; the counts describe a valid race.
Worked example
An independently prepared example for this explanation.
Input
1 2 1 0
Output
4 1 3 2
Solution analysis
- An overtaking runner must have started later. With constant speeds it cannot then be overtaken back, so runner j overtakes runner i exactly when j > i and j finishes before i.
- Only 4! = 24 finish orders exist. Enumerate them, compute for each runner how many larger runner numbers appear before it, and compare all four computed counts with the input.
- For finish order 4, 1, 3, 2, runner 1 has larger predecessor 4; runner 2 has larger predecessors 4 and 3; runner 3 has larger predecessor 4; runner 4 has none. These are precisely 1, 2, 1, 0.
Why it works
The constant-speed condition gives the stated equivalence between overtaking and a larger-numbered predecessor. The enumeration tests every permutation using that equivalence and therefore accepts exactly the finish orders consistent with the input. The counts uniquely place runner i relative to the already ordered later starters, so the accepted order is the required one.
Watch out. Do not count earlier starters finishing ahead as overtakers. Runner 4 cannot have been overtaken by anyone.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
vector<int> wanted(4);
for (int &count : wanted) {
cin >> count;
}
vector<int> order = {1, 2, 3, 4};
do {
// A larger-numbered predecessor is a later starter who overtook this runner.
vector<int> counts(4, 0);
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < i; ++j) {
if (order[j] > order[i]) {
++counts[order[i] - 1];
}
}
}
if (counts == wanted) {
for (int i = 0; i < 4; ++i) {
cout << (i == 0 ? "" : " ") << order[i];
}
cout << '\n';
break;
}
} while (next_permutation(order.begin(), order.end()));
return 0;
}