Boats

Boats

📝 Problem Description

The problem asks for the maximum number of boats that can be tied to a series of rings along a river bank without any boats overlapping.

There are $N$ boats. For each boat $i$, its length, $l_i$, and the position of its assigned ring, $p_i$ are given. A boat must be tied such that the ring is located somewhere along the boat's length, inclusive of its endpoints. This means if a boat of length $l_i$ is placed occupying the interval of coordinates $[s, s+l_i]$, its ring at position $p_i$ must satisfy $s \le p_i \le s+l_i$.

The key constraint is that no two boats can overlap. Their occupied intervals must be disjoint, although their endpoints are allowed to touch. The objective is to select the largest possible subset of boats and a valid, non-overlapping placement for each, then output the size of this subset.

💡 Hints

Hint #1

When dealing with problems involving intervals or objects positioned along a line, it's often beneficial to process them in a specific order rather than randomly. What property of the boats could we sort by to create a more structured approach to the problem?

Hint #2

Sorting the boats by their ring positions ($p_i$) from smallest to largest is a very effective strategy. This allows you to process the boats in a natural "left-to-right" order along the river bank. Now, as you iterate through the sorted boats, what greedy decision can you make at each step?

Hint #3

The core of a greedy strategy is to make a locally optimal choice that hopefully leads to a globally optimal solution. As you process boats sorted by their ring positions, your goal should be to place them in a way that leaves the most possible space for subsequent boats. This means you should always try to make the rightmost endpoint of your placed boats as far to the left as possible.

Hint #4

What happens if a boat doesn't fit? Perhaps it can replace a previously placed boat if doing so results in a better (i.e., smaller) rightmost endpoint for your set of chosen boats.

✨ Solutions

Final Solution

This problem can be solved efficiently using a greedy algorithm. The main idea is to process the boats in a specific order and make a locally optimal choice at each step. The choice should be guided by the heuristic of keeping the rightmost endpoint of all placed boats as far to the left as possible, thereby maximizing the available space for future boats.

Algorithm Breakdown

1. Sorting: First, we sort all the boats based on their ring position, $p$, in ascending order. This creates a natural left-to-right processing order.

2. Greedy Iteration: We iterate through the sorted boats, maintaining a count of placed boats (n_boats) and the coordinates of the two most recent boat endpoints: right_end (the rightmost endpoint of the last placed boat) and prev_right_end (the rightmost endpoint of the second-to-last placed boat).

3. Decision Logic: For each boat with length $l$ and ring position $p$, we have two main cases:

   • Case 1: The boat can be added. This occurs if the boat's ring is not covered by the last boat we placed, i.e., p >= right_end. If so, we can add this boat to our set. We increment n_boats. To maintain our greedy strategy, we must place this new boat as far to the left as possible. Its starting position s must be at least right_end (to avoid collision) and also at least p - l (to reach its ring). Thus, the optimal start is s = max(right_end, p - l). The new right_end becomes s + l. We also update prev_right_end to the old right_end.

   • Case 2: The boat cannot be added directly. This occurs if p < right_end, meaning the current boat's ring is blocked by the last boat we placed. We cannot simply add it. However, we can check if it's beneficial to replace the last boat with the current one. A replacement is beneficial if the resulting arrangement has a rightmost endpoint that is smaller than the current right_end. If we swap out the last boat, the available space starts after prev_right_end. The new boat would be placed with a start position s = max(prev_right_end, p - l), leading to a new endpoint e_new = s + l. If e_new < right_end, we perform the replacement by updating right_end to e_new. The number of boats, n_boats, remains unchanged in a replacement.

By following this strategy, we ensure that at each step, we maintain an optimal configuration for the number of boats chosen so far, characterized by the smallest possible rightmost endpoint. This greedy approach is guaranteed to find the maximal number of boats.

Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>

void solve() {
  // ===== READ INPUT =====
  int n; std::cin >> n;
  
  std::vector<std::pair<int, int>> boats; boats.reserve(n);
  for(int i = 0; i < n; ++i) {
    int l, p; std::cin >> l >> p;
    boats.emplace_back(l, p);
  }
  
  // ===== SOLVE =====
  std::sort(boats.begin(), boats.end(), [](const std::pair<int, int> &a, const std::pair<int, int> &b){
    return a.second < b.second;
  });
  
  int n_boats = 0;
  int right_end = std::numeric_limits<int>::min();
  int prev_right_end = std::numeric_limits<int>::min();
  
  for(const std::pair<int, int> boat : boats) {
    int length = boat.first;
    int ring_pos = boat.second;
    
    if(ring_pos >= right_end) {
      // Boat can be placed
      prev_right_end = right_end;
      
      // Determine where the next right end is going to be
      if(right_end + length >= ring_pos) { right_end = right_end + length; }
      else { right_end = ring_pos; }
      
      n_boats++;
    } else {
      // Boat can not be placed, Check if we should replace the current right most boat
      if(prev_right_end + length < right_end) {
        // Current Boat is a better fit -> Replace
        if(prev_right_end + length >= ring_pos) { right_end = prev_right_end + length; }
        else { right_end = ring_pos; }
      }
    }
  }
  
  // ===== OUTPUT =====
  std::cout << n_boats << std::endl;
}

int main() {
  std::ios_base::sync_with_stdio(false);
  
  int n_tests; std::cin >> n_tests;
  while(n_tests--) { solve(); }
}

⚡ Result

Compiling: successful

Judging solution >>>>
   Test set 1 (30 pts / 2 s) : Correct answer      (0.002s)
   Test set 2 (30 pts / 2 s) : Correct answer      (0.005s)
   Test set 3 (40 pts / 2 s) : Correct answer      (0.674s)

Total score: 100