2015 Open Gold Problem 3 Trapped in the Haybales (Gold)

Official Problem Statement

Trapped in the Haybales (Gold)

Problem

Farmer John's N (1 ≤ N ≤ 100,000) haybales are scattered around the field at distinct locations xi (0 ≤ xi ≤ 1,000,000,000). Each haybale has a size si (1 ≤ si ≤ 1,000,000,000). Bessie starts at a particular haybale and wants to walk to another haybale, but she might be trapped due to the large sizes of the haybales!

More specifically, if Bessie is at location x and wants to move to location x', she can only do this if the haybale at location x' is strictly larger than the distance between x and x'. Otherwise, the haybale at x' "traps" her and prevents her from moving to x'. Bessie can initially be placed at any haybale and she can also stop at any haybale, but she can only move between haybales as described above.

Determine the maximum distance Bessie can travel. Output -1 if Bessie can travel an arbitrarily large distance.

Solution

The haybales can be seen as nodes of a directed graph, with an edge from haybale A to haybale B if B's size is strictly greater than the distance between A and B. This can be computed in O(N log N) time by sorting the haybales by position and comparing each pair of adjacent haybales.

Once the graph is constructed, determine whether there is a cycle in the graph. If there is a cycle, then Bessie can travel an arbitrarily large distance and the answer is -1.

Otherwise, for each connected component of the graph, compute the maximum and minimum positions of the haybales within the component. Then, for each component, add to the answer the difference between the maximum position in the component and the minimum position in the next component, as well as the difference between the maximum position in the previous component and the minimum position in the component. This will give the maximum distance Bessie can travel.

Code

C++

#include <bits/stdc++.h>
using namespace std;

struct Haybale {
    int position, size;
    Haybale(int sizeIn, int positionIn) : size(sizeIn), position(positionIn) {}
};

bool PositionCompare(const Haybale &a, const Haybale &b) {
    return a.position < b.position;
}

bool SizeCompare(const Haybale &a, const Haybale &b) {
    return a.size > b.size;
}

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

    int n;
    fin >> n;
    vector<Haybale> bales(n);

    for (int i = 0; i < n; i++) {
        int size, position;
        fin >> size >> position;
        bales[i] = Haybale(size, position);
    }

    sort(bales.begin(), bales.end(), PositionCompare);

    vector<int> locations(n);
    map<int, int> indexMap, sizeMap;

    for (int i = 0; i < n; i++) {
        locations[i] = bales[i].position;
        indexMap[locations[i]] = i;
        sizeMap[bales[i].position] = bales[i].size;
    }

    sort(bales.begin(), bales.end(), SizeCompare);

    set<int> seenIndices;
    int totalCoveredDistance = 0;
    vector<bool> coveredSegments(n - 1, false);

    for (Haybale &current : bales) {
        int currentIndex = indexMap[current.position];

        auto nextIter = seenIndices.upper_bound(currentIndex);
        if (nextIter != seenIndices.end()) {
            int nextIndex = *nextIter;
            int distance = locations[nextIndex] - locations[currentIndex];
            if (distance <= sizeMap[locations[nextIndex]] && distance <= current.size) {
                fill(coveredSegments.begin() + currentIndex, coveredSegments.begin() + nextIndex, true);
            }
        }

        auto prevIter = seenIndices.lower_bound(currentIndex);
        if (prevIter != seenIndices.begin()) {
            int prevIndex = *prev(prevIter);
            int distance = locations[currentIndex] - locations[prevIndex];
            if (distance <= sizeMap[locations[prevIndex]] && distance <= current.size) {
                fill(coveredSegments.begin() + prevIndex, coveredSegments.begin() + currentIndex, true);
            }
        }

        seenIndices.insert(currentIndex);
    }

    for (int i = 0; i < coveredSegments.size(); i++) {
        if (coveredSegments[i]) {
            totalCoveredDistance += locations[i + 1] - locations[i];
        }
    }

    fout << totalCoveredDistance << '\n';

    return 0;
}

Java

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

public class TrappedInHaybales {
    static class Haybale {
        public int position, size;
        public Haybale(int sizeIn, int positionIn) {
            size = sizeIn;
            position = positionIn;
        }
    }

    static class PositionComparator implements Comparator<Haybale> {
        public int compare(Haybale a, Haybale b) {
            return Integer.compare(a.position, b.position);
        }
    }

    static class SizeComparator implements Comparator<Haybale> {
        public int compare(Haybale a, Haybale b) {
            return Integer.compare(b.size, a.size);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new FileReader("trapped.in"));
        PrintWriter writer = new PrintWriter(new BufferedWriter(new FileWriter("trapped.out")));
        int n = Integer.parseInt(reader.readLine());
        Haybale[] bales = new Haybale[n];

        for (int i = 0; i < n; i++) {
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            int size = Integer.parseInt(tokenizer.nextToken());
            int position = Integer.parseInt(tokenizer.nextToken());
            bales[i] = new Haybale(size, position);
        }

        Arrays.sort(bales, new PositionComparator());

        int[] locations = new int[n];
        Map<Integer, Integer> indexMap = new HashMap<>();
        Map<Integer, Integer> sizeMap = new HashMap<>();

        for(int i = 0; i < n; i++) {
            locations[i] = bales[i].position;
            indexMap.put(locations[i], i);
            sizeMap.put(bales[i].position, bales[i].size);
        }

        Arrays.sort(bales, new SizeComparator());

        TreeSet<Integer> seenIndices = new TreeSet<>();
        int totalCoveredDistance = 0;
        boolean[] coveredSegments = new boolean[n-1];

        for(Haybale current: bales) {
            int currentIndex = indexMap.get(current.position);

            // If there are indices to the right of currentIndex
            if(seenIndices.size() > 0 && seenIndices.last() > currentIndex) {
                int nextIndex = seenIndices.higher(currentIndex);
                int distance = locations[nextIndex] - locations[currentIndex];
                if(distance <= sizeMap.get(locations[nextIndex]) && distance <= current.size) {
                    if(!coveredSegments[currentIndex]) {
                        Arrays.fill(coveredSegments, currentIndex, nextIndex, true);
                    }
                }
            }

            // If there are indices to the left of currentIndex
            if(seenIndices.size() > 0 && seenIndices.first() < currentIndex) {
                int previousIndex = seenIndices.lower(currentIndex);
                int distance = locations[currentIndex] - locations[previousIndex];
                if(distance <= sizeMap.get(locations[previousIndex]) && distance <= current.size) {
                    if(!coveredSegments[previousIndex]) {
                        Arrays.fill(coveredSegments, previousIndex, currentIndex, true);
                    }
                }
            }

            seenIndices.add(currentIndex);
        }

        for(int i = 0; i < coveredSegments.length; i++) {
            if(coveredSegments[i]) {
                totalCoveredDistance += locations[i+1] - locations[i];
            }
        }

        writer.println(totalCoveredDistance);
        writer.close();
    }
}

Python

from operator import attrgetter
from bisect import bisect_right, bisect_left
from collections import deque

class Haybale:
    def __init__(self, size, position):
        self.size = size
        self.position = position

def main():
    with open("trapped.in", "r") as fin, open("trapped.out", "w") as fout:
        n = int(fin.readline().strip())
        bales = []

        for _ in range(n):
            size, position = map(int, fin.readline().split())
            bales.append(Haybale(size, position))

        bales.sort(key=attrgetter('position'))
        locations = [bale.position for bale in bales]
        index_map = {bale.position: i for i, bale in enumerate(bales)}
        size_map = {bale.position: bale.size for bale in bales}

        bales.sort(key=attrgetter('size'), reverse=True)

        seen_indices = deque()
        total_covered_distance = 0
        covered_segments = [False] * (n - 1)

        for current in bales:
            current_index = index_map[current.position]

            if seen_indices:
                next_index = bisect_right(seen_indices, current_index)
                if next_index != len(seen_indices):
                    distance = locations[seen_indices[next_index]] - locations[current_index]
                    if distance <= size_map[locations[seen_indices[next_index]]] and distance <= current.size:
                        for i in range(current_index, seen_indices[next_index]):
                            covered_segments[i] = True

                prev_index = bisect_left(seen_indices, current_index) - 1
                if prev_index >= 0:
                    distance = locations[current_index] - locations[seen_indices[prev_index]]
                    if distance <= size_map[locations[seen_indices[prev_index]]] and distance <= current.size:
                        for i in range(seen_indices[prev_index], current_index):
                            covered_segments[i] = True

            seen_indices.append(current_index)
            seen_indices = deque(sorted(seen_indices))

        for i, covered in enumerate(covered_segments):
            if covered:
                total_covered_distance += locations[i + 1] - locations[i]

        fout.write(str(total_covered_distance) + '\n')

if __name__ == "__main__":
    main()