Painting a Fence
Autumn Tournament (2018)
Submission name: painting.cpp
Problem summary
Paint every board from A to B inclusive, then every board from C to D inclusive. Either pass can go in either direction. Count the distinct painted boards.
Input
Four board numbers A, B, C, D.
Output
The number of boards painted at least once.
Constraints
1 ≤ A, B, C, D ≤ 1000000000.
Worked example
First official statement sample.
Input
1 2 6 4
Output
5
Solution analysis
- Normalize each pass by putting its smaller endpoint first. Its inclusive length is right − left + 1.
- Add the lengths of the two intervals, then subtract their intersection length. The intersection starts at the larger left endpoint and ends at the smaller right endpoint; its length is zero if these endpoints are reversed.
- For 1 2 6 4 the normalized intervals are [1, 2] and [4, 6]. They contain 2 and 3 boards and do not intersect, so the answer is 5.
Why it works
A board outside the intersection is counted once in the sum of interval lengths. A board inside it is counted twice. Subtracting the intersection counts each painted board exactly once.
Complexity: O(1) time and O(1) extra space.
Watch out. Normalize both pairs and include both endpoints. Use a zero overlap for disjoint intervals.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: A board outside the intersection is counted once in the sum of interval lengths. A board
// inside it is counted twice.
#include<algorithm>
#include<iostream>
using namespace std;
int main(){
long long a,b,c,d;
cin>>a>>b>>c>>d;
if(a>b){
swap(a,b);
}
if(c>d){
swap(c,d);
}
long long overlap=max(0LL,min(b,d)-max(a,c)+1);
cout<<(b-a+1)+(d-c+1)-overlap<<'\n';
}