PROBLEM LINK:
Author: Adabelle Xie
DIFFICULTY:
MEDIUM
PREREQUISITES:
PROBLEM:
Given a string of ‘X’ and ‘O’ characters, ‘X’ representing a closed building and ‘O’ representing an open building, N boards that can cover any number of consecutive buildings, and a maximum K closed buildings that can be covered by the N boards, find whether or not it is possible to cover all open buildings using N boards, only covering a K closed buildings or fewer.
QUICK EXPLANATION:
For each board, remove the largest contiguous section of closed buildings you can. If after removing N sections, there are more than K closed buildings left, than it is impossible to use N boards to cover all the open buildings only covering K closed buildings. If there are K or fewer buildings left, then it is possible.
EXPLANATION:
This problem is heavily inspired by a problem from the 1999 USACO Spring Open, and USACO has a good explanation on their training site. This problem is optimally solved using a greedy approach. We assume that the best solution only using 2 boards can be modified to yield the best solution for 3 boards. Taking out one contiguous section of buildings from a 2-board solution will yield a 3-board solution. And we always want to remove the largest section of closed buildings possible, as we want to minimize the number of closed stalls covered by the boards. Using one pass through the string, we can find both the number of closed buildings and add the lengths of the contiguous sections of buildings to a max priority queue (in java, a priority queue dequeues smaller integers first, therefore I add the negatives of the lengths then multiply by -1 after the poll operation to reverse the order of removal). Then for the N boards, do N dequeue operations, subtracting each result from the total number of closed stalls we already found. If what is left is less than or equal to K, return “Possible”. Else, return “Impossible”.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.