Unwatched Border
National Olympiad — National round (2020 season)
Submission name: border.cpp
Problem summary
M observation posts lie one kilometre apart on a straight border, numbered 1 to M. Each of N guards occupies a listed post; duplicates are allowed. An occupied post watches the adjacent one-kilometre intervals. Find the total length of unwatched intervals between posts 1 and M.
Input
N M, followed by the N occupied-post numbers.
Output
The unwatched length in kilometres.
Constraints
All input integers are positive and less than 1,000,000; each post number is at most M.
Worked example
An independently prepared example for this explanation.
Input
9 13 8 3 6 8 13 3 8 3 12
Output
4
Solution analysis
- Mark each post that receives at least one guard. Multiple guards at one post have the same effect as a single guard.
- There are M−1 unit intervals. The interval between i and i+1 is unwatched precisely when neither endpoint is occupied, so scan the adjacent pairs of marks.
- In the sample, the uncovered intervals are 1–2, 4–5, 9–10 and 10–11. The final two form a longer gap, but still contribute two kilometres. Their total is 4.
Why it works
Each border interval is watched if either endpoint contains a guard, by the stated visibility rule. The scan counts the complementary case for every unit interval exactly once, giving the total unwatched length.
Watch out. Do not count territory outside posts 1 and M. Repeated post numbers must not increase coverage more than once.
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, m;
cin >> n >> m;
vector<bool> occupied(m + 1, false);
for (int i = 0; i < n; i++) {
int post;
cin >> post;
occupied[post] = true;
}
int answer = 0;
for (int post = 1; post < m; post++) {
// A unit interval is covered by either of its endpoints.
if (!occupied[post] && !occupied[post + 1]) {
answer++;
}
}
cout << answer << '\n';
}