2015 Dec Bronze Problem 1 Fence Painting

Official Problem Statement

Fence Painting

Problem

Farmer John is painting his fence. The fence is 1-dimensional, with positions along the fence denoted by integers. Two sections of the fence need to be painted, both described by two integers $a$ and $b$ ($a \le b$), and $c$ and $d$ ($c \le d$), indicating that the interval from $a$ to $b$ and from $c$ to $d$ need to be painted. It's possible that these intervals overlap.

Your task is to compute the total length of the fence that needs to be painted.

The input file, "paint.in", starts with two space-separated integers, $a$ and $b$ ($0 \le a < b \le 100$). The second line of the input contains another two space-separated integers, $c$ and $d$ ($0 \le c < d \le 100$).

The output file, "paint.out", should output one line with one integer – the total length of the fence that needs to be painted.

Solution

This problem can be solved by calculating the length of the intervals $a$ to $b$ and $c$ to $d$, and adding them. However, this might lead to counting the length of the overlapped region twice. To avoid this, we can calculate the length of the overlap (if any), and subtract it from the total.

To calculate the length of the overlap, we take the maximum of the lower bounds ($a$ and $c$) and the minimum of the upper bounds ($b$ and $d$). If the maximum lower bound is less than the minimum upper bound, there is an overlap, and its length can be calculated as the difference between these two values.

The total length of the fence that needs to be painted is then the sum of the lengths of the two intervals, minus the length of the overlap.

This solution has a time complexity of $O(1)$, since it only requires a few arithmetic operations.

Code

C++

#include <iostream>
#include <fstream>

using namespace std;

int main() {
    ifstream fin("paint.in");
    ofstream fout("paint.out");

    int segment1Start, segment1End;
    fin >> segment1Start >> segment1End;

    int segment2Start, segment2End;
    fin >> segment2Start >> segment2End;

    int paintedLength;

    if(segment2Start >= segment1End) {
        paintedLength = (segment1End - segment1Start) + (segment2End - segment2Start);
    } else if(segment2End > segment1End) {
        paintedLength = segment2End - segment1Start;
    } else {
        paintedLength = segment1End - segment1Start;
    }

    fout << paintedLength << endl;

    return 0;
}

Java

import java.io.*;
import java.util.*;

public class Paint {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new FileReader("paint.in"));
        PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("paint.out")));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int segment1Start = Integer.parseInt(st.nextToken());
        int segment1End = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int segment2Start = Integer.parseInt(st.nextToken());
        int segment2End = Integer.parseInt(st.nextToken());

        int paintedLength;

        // Checking overlap scenarios
        if(segment2Start >= segment1End) {
            // No overlap
            paintedLength = (segment1End - segment1Start) + (segment2End - segment2Start);
        }
        else if(segment2End > segment1End) {
            // Partial overlap with segment2 exceeding segment1
            paintedLength = segment2End - segment1Start;
        }
        else {
            // Full overlap where segment2 is completely inside segment1
            paintedLength = segment1End - segment1Start;
        }
        
        pw.println(paintedLength);
        pw.close();
    }
}

Python

with open('paint.in', 'r') as fin:
    a, b = map(int, fin.readline().strip().split())
    c, d = map(int, fin.readline().strip().split())

if c < a:
    a, c = c, a
    b, d = d, b

if c >= b:
    painted_length = (b - a) + (d - c)
elif d > b:
    painted_length = d - a
else:
    painted_length = b - a

with open('paint.out', 'w') as fout:
    fout.write(str(painted_length) + '\n')