Adapting Binary Search for UVa 12192

Last week, I wrote about the benefits of carefully studying even simple algorithms like binary search, which provides a fast way to find an element in a sorted array. Once you understand how that algorithm works, you can adapt it to solve other problems. For example:

Given an array of integers and an integer L, find the position of the first element of the array that is greater than or equal to L.

The standard binary search algorithm looks for an exact match. If the target key is not in the array, the search fails (returns a “not found” value). So if we want to handle an inequality, we’ll have to make a few changes. Here are the key points of the revised algorithm.

Binary Search, Greater or Equal Version

• First, we can do a couple of checks to see if we can find the answer immediately:
  • Check 1: If the last element of the array is less than L, there is no solution.
  • Check 2: If the first element of the array is greater than or equal to L, then we immediately know that the answer is position 0.
• If neither of these is true, then we enter the same while loop as in regular binary search.
• In each iteration of the loop, we have the answer if both of these conditions are true:
  • Condition 1: The current element is greater than or equal to L.
  • Condition 2: The previous element is less than L, so we have the first element that is >= L. (Note: the special case that occurs when we’re at element 0, so there’s no previous element, has already been handled above).
• The expressions that reset the control variables lo, mid, and hi are almost the same as in regular binary search:
  • If the current element is greater than or equal to L but we haven’t returned yet, then we haven’t yet found the first (leftmost) target element. Search to the left.
  • If the current element is less than L, search to the right.

Here’s a pseudocode version of this revised algorithm:

binarySearchGe(sorted array a, int L)
    lo = first element of a
    hi = last element of a
    if a[hi] < L return -1  // no answer
    if a[lo] >= L return lo // immediate answer

    while (lo <= hi)
        mid = lo + (hi - lo)/2 // same as regular binary search
        if both of these conditions are true, return mid
            a[mid] >= L
            a[mid-1] < L

        // if we haven't returned,
        // update the control variables
        if a[mid] >= L, hi = mid - 1
        else if (a[mid] < L) lo = mid + 1

Now that we have this “greater or equal” version of binary search, we can tackle a problem that requires it, UVa 12192: Grapevine. Here’s what it asks:

You have a grid of integers with the following property: As you move down or to the right, the values are nondecreasing. Given a lower bound L and an upper bound U, find the size of the largest square region in which all grid cells are greater than or equal to L and less than or equal to U.

Grapevine, Attempt #1

Since the grid can be large (up to 500×500), we’ll need an efficient way to search it for the values that make up the square region we’re looking for. The problem statement specifies that each row is sorted in ascending order from left to right, and each column is sorted in ascending order from top to bottom. This makes it perfect for binary searching using the revised algorithm. Can we use binarySearchGe?

In my first attempt at this problem, I went binary search happy and implemented four different binary search functions to find a target segment for each row and each column using L and U. Given these target segments (whose values were all >= L and <=U), I used an overlap detection process to find the largest contiguous square region containing only cells in these segments.

My implementation found the accepted answer for the large random input on uDebug. But it exceeded the time limit on UVa OJ. For some hints, I studied a C++ implementation by Sai Cheemalapati that uses std::lower_bound, which has the same goal as the binary search algorithm shown above.

Grapevine, Attempt #2

Like binary search itself, UVa 12192 can be solved using an algorithm that is short, but contains a few tricky conditionals. The algorithm uses a set of two nested loops. The outer loop iterates over the rows in the grid. The inner loop checks increasingly larger square regions, looking for the largest one that meets the problem criteria. Once both loops exit, the result is the size of the largest valid square region.

The only thing the outer loop does is find the first grid cell in the current row whose value is >= L. Since each row is sorted, we can do this using binarySearchGe. Then, since every cell value is greater than or equal to the one to the left of it and the one above it, the inner loop can expand the square region down and to the right without worrying about L.

Here’s the algorithm in more detail:

bestSize = 0  // largest square found so far
for each row from 0 to N-1
    col = binarySearchGe(row, L)
    if no col was found in this row, continue with next row
    for size from bestSize to N-1
        endRow = row+size  // bottom of current square
        endCol = col+size  // right side of current square
        if any one of these conditions is true, break
            endRow >= N  // beyond bottom of grid
            endCol >= M  // beyond right edge of grid
            grid[endRow][endCol] > U  // beyond upper limit
        if size+1 > bestSize, set bestSize = size+1
print bestSize

The algorithm works as follows:

Starting with the first row in the grid, we look for the first valid column using binarySearchGe. If there isn’t a valid column in the current row, we process rows until we find one or get to the bottom of the grid. Then, starting with the largest square size found so far, we look for larger squares. At a loop index size, the square covers rows from row to endRow = row+size and columns col to endCol = col+size.

If any of the following conditions are true, we break out of the loop and don’t modify bestSize, the variable that tracks the size of the largest square found so far:

• endRow >= N: Grid rows are numbered from 0 to N-1, so this isn’t a valid ending row.
• endCol >= M: Grid columns are numbered from 0 to M-1, so this isn’t a valid ending column.
• grid[endRow][endCol] > U: Cells inside the target square must be <= U, so this isn’t a valid target cell.

If we make it through these checks and size exceeds the largest size found so far, we can increment bestSize. Once we have checked every row, we’re guaranteed to find the optimal size (which may be 0), and we print it to the output.

Thoughts on Solving UVa 12192

UVa 12192 is the third starred problem in the Binary Search section of uHunt Chapter 3, so adapting binary search to solve it was an easy decision. The trick is figuring out when to stop using binary search. It turns out that a little bit of binary search, plus some old-fashioned nested loops, led to a faster solution than binary searching all possible values. In other words: regardless of how many algorithms you know, solving competitive programming problems also requires general problem-solving skills and creative thinking.

(Image credit: Giorgio Galeotti, previously at https://www.flickr.com/photos/fotodispalle/6207515511)