2015 Open Silver Problem 2 Trapped in the Haybales (Silver)

Official Problem Statement

Trapped in the Haybales (Silver)

Problem

In this problem, Bessie the cow is stuck between a series of haybales. There are 'N' (1 <= N <= 50,000) haybales each with a size 'Si' (1 <= Si <= 1,000,000,000) and a position 'Pi' (-1,000,000,000 <= Pi <= 1,000,000,000) on the number line. Bessie can only remove a haybale if it is next to her and its size is smaller than the total distance Bessie has walked. Bessie's goal is to escape from the haybales, and she can choose to initially be between any two haybales.

The task is to find and print the minimum distance Bessie has to walk to escape from the haybales.

Solution

The problem can be solved using a greedy approach and two-pointers.

• Sort the haybales based on their positions.
• Use two pointers, 'left' and 'right', initially pointing to the two haybales Bessie is between.
• Keep a 'best' variable to store the minimum distance Bessie needs to escape.
• If the size of the left haybale is smaller than the distance between the two haybales, move the 'left' pointer to the left and update 'best'. Similarly, if the size of the right haybale is smaller than the distance between the two haybales, move the 'right' pointer to the right and update 'best'.
• Keep repeating step 4 until Bessie can escape.

Time complexity is O(N log N) due to sorting, which is acceptable given the constraints.

The solution is greedy because at each step we're trying to move Bessie in the direction that minimizes the total distance she needs to walk to escape.

Code

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>

using namespace std;

const int INF = 1e9+10;

int main() {
  freopen("trapped.in", "r", stdin);
  freopen("trapped.out", "w", stdout);

  int totalHaybales, startPosition;
  cin >> totalHaybales >> startPosition;
  
  vector<pair<int, int>> haybales(totalHaybales);
  
  for (int i = 0; i < totalHaybales; i++) {
    cin >> haybales[i].second >> haybales[i].first;
  }
  
  sort(haybales.begin(), haybales.end());

  int minimumDistance = INF;
  int index = lower_bound(haybales.begin(), haybales.end(), make_pair(startPosition, 0)) - haybales.begin();

  int upperIndex = index;
  for (int lowerIndex = index - 1; lowerIndex >= 0; lowerIndex--) {
    while (upperIndex < totalHaybales && haybales[upperIndex].first <= haybales[lowerIndex].first + haybales[lowerIndex].second) {
      minimumDistance = min(minimumDistance, haybales[upperIndex].first - haybales[lowerIndex].first - haybales[upperIndex].second);
      upperIndex++;
    }
  }

  int lowerIndex = index - 1;
  for (int upperIndex = index; upperIndex < totalHaybales; upperIndex++) {
    while (lowerIndex >= 0 && haybales[upperIndex].first - haybales[upperIndex].second <= haybales[lowerIndex].first) {
      minimumDistance = min(minimumDistance, haybales[upperIndex].first - haybales[lowerIndex].first - haybales[lowerIndex].second);
      lowerIndex--;
    }
  }

  if (minimumDistance == INF) {
    cout << -1 << endl;
  } else {
    cout << max(minimumDistance, 0) << endl;
  }

  return 0;
}

Java

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

public class Main {
    static final int INF = (int) 1e9 + 10;

    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")));

        StringTokenizer st = new StringTokenizer(reader.readLine());
        int totalHaybales = Integer.parseInt(st.nextToken());
        int startPosition = Integer.parseInt(st.nextToken());

        Pair[] haybales = new Pair[totalHaybales];
        for (int i = 0; i < totalHaybales; i++) {
            st = new StringTokenizer(reader.readLine());
            int size = Integer.parseInt(st.nextToken());
            int position = Integer.parseInt(st.nextToken());
            haybales[i] = new Pair(position, size);
        }

        Arrays.sort(haybales);

        int minimumDistance = INF;
        int index = Arrays.binarySearch(haybales, new Pair(startPosition, 0));
        index = index < 0 ? -(index + 1) : index;

        int upperIndex = index;
        for (int lowerIndex = index - 1; lowerIndex >= 0; lowerIndex--) {
            while (upperIndex < totalHaybales &&
                    haybales[upperIndex].position <= haybales[lowerIndex].position + haybales[lowerIndex].size) {
                minimumDistance = Math.min(minimumDistance, haybales[upperIndex].position - haybales[lowerIndex].position - haybales[upperIndex].size);
                upperIndex++;
            }
        }

        int lowerIndex = index - 1;
        for (int upperIndex = index; upperIndex < totalHaybales; upperIndex++) {
            while (lowerIndex >= 0 &&
                    haybales[upperIndex].position - haybales[upperIndex].size <= haybales[lowerIndex].position) {
                minimumDistance = Math.min(minimumDistance, haybales[upperIndex].position - haybales[lowerIndex].position - haybales[lowerIndex].size);
                lowerIndex--;
            }
        }

        if (minimumDistance == INF) {
            writer.println(-1);
        } else {
            writer.println(Math.max(minimumDistance, 0));
        }

        writer.close();
    }

    static class Pair implements Comparable<Pair> {
        int position;
        int size;

        Pair(int position, int size) {
            this.position = position;
            this.size = size;
        }

        @Override
        public int compareTo(Pair o) {
            return Integer.compare(this.position, o.position);
        }
    }
}

Python

import sys
from bisect import bisect_left

INF = 10**9 + 10

def main():
    with open('trapped.in', 'r') as f:
        N, B = map(int, f.readline().split())
        haybales = sorted([list(map(int, line.split()))[::-1] for line in f.readlines()])

    result = INF
    sp = bisect_left(haybales, [B, 0])

    j = sp
    for i in range(sp - 1, -1, -1):
        while j < N and haybales[j][0] <= haybales[i][0] + haybales[i][1]:
            result = min(result, haybales[j][0] - haybales[i][0] - haybales[j][1])
            j += 1

    j = sp - 1
    for i in range(sp, N):
        while j >= 0 and haybales[i][0] - haybales[i][1] <= haybales[j][0]:
            result = min(result, haybales[i][0] - haybales[j][0] - haybales[j][1])
            j -= 1

    with open('trapped.out', 'w') as f:
        if result == INF:
            f.write("-1\n")
        else:
            f.write(f"{max(result, 0)}\n")


if __name__ == "__main__":
    main()