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.
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.
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.
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.