In the Divide and Conquer section of uHunt Chapter 3, one of the subsections is called Binary Search the Answer. Here’s how that technique works.

For a binary search problem like UVa 12192, the data to search is the input data. For that problem, you are given a rectangular grid of integers, and your goal is to find a square region that satisfies a particular property. One step in the process of finding that region efficiently is to run binary search on the data in a row.

Binary search problems like UVa 11413 and UVa 12032 require a different approach. Instead of binary searching the input data, you must search potential output values. The result of the search is the answer.

Competitive programming problem statements often specify the range of inputs that you are required to handle in your solution. For example, the description for UVa 12192 specifies that the grid cannot be larger than 500×500.

The input range is there for a few reasons. It lets you estimate the runtime of your solution before you submit, to avoid a Time Limit error. It also lets you choose an appropriate algorithm. If you determine that an $O(n^2)$ algorithm will run fast enough given the input size, then there’s no need to use an $O(n \log n)$ algorithm, which may take more time to implement. Finally, for search problems, the range tells you which values you have to search.

For binary search the input problems, you can directly plug the input range from the problem statement into the low and high values in your binary search function. For binary search the output problems, you may have to process the input first. Let’s look at a couple of examples.

« Continue »

We have arrived at that time of the year when students leave behind their regular academic schedules and take up summer activities like bike riding, taking long walks on the beach, and learning competitive programming. Last week, a reader sent me an email asking for advice on the best way to spend two months practicing algorithmic problem solving. Here are some ideas for others who may be interested in pursuing that as well.

« Continue »

Last week, I wrote an editorial for UVa 12192: Grapevine. I thought some more about the experience of solving it, and came up with four lessons that apply to competitive programming problem-solving.

« Continue »

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.

« Continue »

uHunt Chapter 3 has six starred problems, and many more problems in total, on the topic of binary search. If you want to solve them, it helps to have a firm grasp of how that algorithm works.

The binary search algorithm is conceptually simple. In ancient times, like the early 1990’s, people used it instinctively when looking up words in a paper dictionary or finding phone numbers in the thick book that arrived on their doorstep. The process:

• Open the book to the middle.
• If your target entry is alphabetically lower than the current entry, split the left half of the book. Otherwise, split the right half.
• Repeat until done.

« Continue »

When I’m solving competitive programming problems for practice, I follow a specific series of steps to help me get the most out of the process. My current process ends with submitting an accepted solution and recording my stop time (for measurement purposes). But there really should be another step: find someone else’s solution and compare it with mine.

« Continue »

When you’re solving competitive programming problems, it’s tempting to code as fast as possible. Once you have some idea about what the problem is asking for, just start coding and hack away until your solution passes. After all, these problems are written for timed contests, so why not solve them as if you’re racing the clock?

At some point in your competitive programming career, the “full speed ahead” approach might be the right one. If you want to do well in contests, you have to practice under contest-like conditions. But it may be a while before that’s the optimal practice strategy.

The problem with coding quickly is that you’ll end up with messy code that’s hard to debug. There’s nothing morally wrong with writing messy code that you’re going to throw away in an hour. If you’re getting correct solutions quickly, go for it. But if you’re spending a lot of time debugging code that’s incomprehensible a minute after you write it, maybe it would be more efficient to slow down.

Now, I’m not saying you should go to the other extreme and polish your code as if you were going to turn it into a product. Even if you have a lot of practice time, there’s a limit to how much learning benefit you can get out of one contest problem. Save your best coding style for code that you’re going to keep around.

« Continue »

[T]here are two things traditionally taught in universities as a part of a computer science curriculum which many people just never really fully comprehend: pointers and recursion. — Joel Spolsky

Let’s try to comprehend the basics of recursion using an example that comes up frequently in programming puzzles: generating all permutations of a set.

« Continue »

Last week I wrote about solving UVa 11085 using the recursive backtracking search technique. This week, I’m going to outline a more general approach to recursive backtracking problems. Then I’ll show how it can be adapted to solve UVa 574.

UVa 574 asks us to solve this problem:

Given a multiset $S$ of integers and a target sum $t$, find all subsets of $S$ that sum to $t$.

« Continue »