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

Official Problem Statement

Trapped in the Haybales (Bronze)

Problem

Bessie the cow is stuck in a field filled with haybales! The field is represented as a number line, and there are haybales at certain positions along this line. Bessie is currently at some position on this line.

Each haybale has a "size", which is a positive integer. If Bessie is at a point on the number line right next to a haybale of size S, then she can push her way past the haybale, but only if Bessie moves to a position that is exactly S units away.

Bessie wants to make her way from her current position to position 0, but she is wondering whether this is possible. Given the size and position of each haybale in the field, is it possible for Bessie to move to position 0?

Please write a program that solves this problem. You are given N (1 ≤ N ≤ 100), the number of haybales, followed by the position and size of each haybale. Bessie's current position will be given in the problem. All positions are given as integers (with Bessie's position and the haybale positions possibly being negative, because they can be anywhere on the number line).

Solution

The solution to this problem can be found by using a breadth-first search (BFS) algorithm on the number line. The key idea is to represent each possible position Bessie could be at as a node in a graph, with an edge between two nodes if Bessie can move between the corresponding positions by pushing a haybale. Then, using BFS starting from Bessie's initial position, we can determine whether there is a path to position 0.

Here is the pseudocode of the solution:

• Initialize a queue for the BFS and add Bessie's initial position to the queue.
• While the queue is not empty, repeat the following steps:
• Take a position from the front of the queue.
• For each haybale, if Bessie can move from the current position to a new position by pushing the haybale, and Bessie has not been at the new position before, then add the new position to the queue.
• If Bessie reaches position 0, then output "yes" and terminate the program.
• If the BFS finishes without reaching position 0, then output "no".

The time complexity of the solution is O(N^2), where N is the number of haybales. This is because in the worst case, Bessie may need to consider moving to every other haybale from each haybale, leading to a quadratic number of operations.

Code

C++

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

struct Haybale {
    int position;
    int size;

    bool operator<(const Haybale& other) const {
        return position < other.position;
    }
};

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

    int numHaybales;
    fin >> numHaybales;

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

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

    int totalTrappedArea = 0;
    for (int i = 0; i < numHaybales - 1; i++) {
        int interval = bales[i+1].position - bales[i].position;
        int leftBale = i;
        int rightBale = i+1;

        while (leftBale >= 0 && rightBale < numHaybales) {
            int currentDistance = bales[rightBale].position - bales[leftBale].position;
            bool escaped = false;

            if (currentDistance > bales[leftBale].size) {
                leftBale--;
                escaped = true;
            }
            if (currentDistance > bales[rightBale].size) {
                rightBale++;
                escaped = true;
            }

            if (!escaped) {
                break;
            }
        }

        if (leftBale >= 0 && rightBale < numHaybales) {
            totalTrappedArea += interval;
        }
    }

    fout << totalTrappedArea << endl;

    return 0;
}

Java

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

public class TrappedB {
  
  static class Haybale implements Comparable<Haybale> {
    int position, size;

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

    public int compareTo(Haybale other) {
      return Integer.compare(this.position, other.position);
    }
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new FileReader("trapped.in"));
    PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("trapped.out")));
    int numHaybales = Integer.parseInt(br.readLine());

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

    Arrays.sort(bales);

    int totalTrappedArea = 0;
    for(int i = 0; i < numHaybales-1; i++) {
      int interval = bales[i+1].position - bales[i].position;
      int leftBale = i;
      int rightBale = i+1;

      while(leftBale >= 0 && rightBale <= numHaybales-1) {
        int currentDistance = bales[rightBale].position - bales[leftBale].position;
        boolean escaped = false;

        if(currentDistance > bales[leftBale].size) {
          leftBale--;
          escaped = true;
        }
        if(currentDistance > bales[rightBale].size) {
          rightBale++;
          escaped = true;
        }

        if(!escaped) {
          break;
        }
      }

      if(leftBale >= 0 && rightBale <= numHaybales-1) {
        totalTrappedArea += interval;
      }
    }

    pw.println(totalTrappedArea);
    pw.close();
  }
}

Python

from operator import attrgetter

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

with open('trapped.in', 'r') as fin:
    num_haybales = int(fin.readline().strip())
    bales = []
    for _ in range(num_haybales):
        size, position = map(int, fin.readline().strip().split())
        bales.append(Haybale(size, position))

bales.sort(key=attrgetter('position'))

total_trapped_area = 0
for i in range(num_haybales - 1):
    interval = bales[i+1].position - bales[i].position
    left_bale = i
    right_bale = i+1

    while left_bale >= 0 and right_bale < num_haybales:
        current_distance = bales[right_bale].position - bales[left_bale].position
        escaped = False

        if current_distance > bales[left_bale].size:
            left_bale -= 1
            escaped = True
        if current_distance > bales[right_bale].size:
            right_bale += 1
            escaped = True

        if not escaped:
            break

    if left_bale >= 0 and right_bale < num_haybales:
        total_trapped_area += interval

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