International Collegiate Programming Contest

Divide and Conquer

This session focuses on binary search and divide and conquer. If you are not familiar with the relevant concepts and algorithms, or you need a refresher, you can use the resources below.

Problem Set (#3)

1. The Playboy Chimp
2. Dropping Balls
3. Copying Books
4. Solve It
5. Bit Maps
6. Bey Battle

Note: All problems expect I/O to be done using standard input and standard output. The solution to problems must be written in a single file. If you are programming in Java the application class should be called "Main" and should be in the default package.

Resources

Binary Search

Binary search is an efficient way of searching through an ordered set of objects to find one that you are interested in (or find that it doesn't exist). The classic example is searching through an ordered array, but there are many other ways to apply binary search: finding a value in the range of a nondecreasing function, for instance, or searching for the smallest "good" number in a range, where you know that if a number is "good", then so are all larger numbers.

The basic algorithm is this: you have a search space you are looking through. You take the midpoint of your search space, test it, and use that information to narrow your search space down to half the size; either on one side of the midpoint or the other. Check out the wikipedia page for more information here.

Divide and Conquer

Divide and Conquer is a name for a class of recursive methods for solving problems. Each recursive step looks something like the following:

1. Take your problem of size N and divide it into a number of subproblems of smaller size.
2. Solve each of the subproblems recursively.
3. Combine the solutions of the subproblems into a solution to the original problem.

Often, we break the problem into two subproblems of half the size each, and steps 1 and 3 take O(N) time. In this case, Divide and Conquer results in a running time of O(N log N). This isn't always the case; in general, you can use the master theorem or just analyze the recursion tree to find the running time of a Divide and Conquer algorithm. As recursive algorithms in general are diverse, there are many variants on Divide and Conquer. Keep an open mind while working!

Ternary Search

Ternary search is an extension of binary search and occasionally comes up in ICPC. If you are given a function that is not increasing or decreasing, but instead convex or concave, it is possible to find the maximum or minimum of the function via ternary search, in logarithmic complexity. The idea is instead of picking a single midpoint, we instead pick two. Based on the values of the function at these midpoints, either the leftmost or rightmost tri-section can be pruned. The details of ternary search can be found here.