International Collegiate Programming Contest

Divide & Conquer and Search

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

Problem Set

1. Paintings
2. Peculiar Primes
3. Batmanacci
4. Careful Ascent
5. Arachnophobia
6. Closest Pair (Uniform)

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. This tutorial on Topcoder has a good discussion of binary search and its applications and implementation.

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! These slides have good information on Divide and Conquer algorithms.

Searching State Spaces

Imagine you are playing a game. At any point the game has some state, and some moves you could follow to go to one of a number of different states. You need to know whether, or how fast, you can get from a given start state to a given end state. How do you figure this out?

In general this is a difficult problem, and unless your game has some very nice properties that allow you to greatly simplify it, there is not much else you can do besides "brute force". The (intelligent) implementation of such a brute force tactic often takes the form of a breadth-first search on the space of states of the game.

You can imagine the states of the game being the vertices of a graph, with directed edges correponding to moves that take you from one state space to another. Often this graph will be very large -- so large that computing all the vertices and edges in the graph is prohibitively expensive -- but you are still interested in trying to find paths through the graph. The general approach is to search, breadth-first, along the edges of the graph, finding edges dynamically by computing how applying each move would change the current state. Since it is often too difficult to keep all possible states in memory, instead one can store encodings of all the previously-visited states in a self-balancing tree in order to relatively quickly check whether a state has been visited before, so as to avoid wasting time repeating already-completed searching.

This page discusses state space search, both depth-first and breadth-first style. It also has a (small) illustrated example.

Meet in the Middle

Meet in the middle is a classic trick to speed up brute force algorithms. The main idea is to split the state into two halves and efficiently combine the possibilities for the two halves, often through the use of appropriate data structures. You can find an example here with the corresponding problem here.