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.
Lesson 1: Dissect the Problem Statement
As anyone who has tried competitive programming problems knows, the problem statements are often not models of clear writing. Some of that is due to a lack of writing skill on the part of the problem setter, but it’s also partly intentional: one of a problem setter’s goals is to evaluate a contestant’s ability to extract the essence of a problem from a complicated problem statement. In this way, competitive programming problems are more extreme versions of the math word problems that schoolchildren are familiar with. And as with word problems, competitive programming problems test your ability to solve a problem that is presented as a pseudo-real-world scenario rather than as a formal problem.
So one of the first steps in solving a programming puzzle is making sense of the problem statement. The best way to do that depends on your learning style. I prefer written notes, but diagrams might work better for some people.
The original problem statement for UVa 12192, not including the test data, has about 600 words. I reduced that to about 115 words of notes while I read the problem. After I solved the problem, I summarized it in a 59-word paragraph for last week’s post. The purpose of all of this reworking is to highlight the essential features of the problem, since those are what define the elements of the solution.
For UVa 12192, the essential features are:
- Rectangular grid of integers.
- Values nondecreasing in the Down and Right directions.
- Find largest square region in which all values are greater than or equal to an integer
Land less than or equal to an integerU.
Feature #1 describes the data that we’re working on. Using this feature, we can pick an appropriate data structure and get a high-level intuition about the problem.
Feature #3 describes the question that we’re being asked to answer. It narrows down what our algorithm will need to do (compare integers and maximize the size of a square region), but doesn’t give us all the information we need to select an algorithm.
Feature #2 provides the key information required to select an algorithm. Since the input data is sorted, we can use Binary Search within a row or column. An experienced puzzle solver may also notice the other key implication of this feature: If you start with a square area that meets the lower and upper bound criteria, you can move the bottom right corner of the square one grid cell to the right and one cell down, and quickly evaluate whether the new square still qualifies as a solution.
Lesson 2: Don’t Get Too Attached to Your Solution
In solving UVa 12192, it’s easy to settle on the binary search solution. The uHunt section where UVa 12192 is located provides the initial hint, and the sorted rows and columns of the grid define the scope of the search. Then, as I mentioned last week, it’s tempting to go binary search happy and use it to get all of the answers you need. But the problem isn’t set up to support that approach, so there’s a severe performance penalty for doing so. Instead, it’s best to take what you can get from binary search, and then move on to the expanding square technique.
As you’re solving a programming puzzle, you have to keep an open mind. You may find the perfect algorithm for one part of the problem, but then come across a sub-problem that requires a different approach. In the case of UVa 12192, that approach is the rather simple process of trying increasingly larger squares once binary search gives you a starting point.
Lesson 3: Strategically Use Other People’s Solutions
A few weeks ago I wrote When to Peek at the Solution, about looking at another solution once you finish your own, to see if you missed a better solution. But it’s more common for people to look for hints when they get stuck in the middle of a solution. There’s nothing wrong with that, but the the key is to do it at the right time. If you do it too early, you’ll miss some of the benefit of struggling with a problem. If you do it too late, you’ll spin your wheels on a problem past the point where you’re getting learning benefit from it.
If you’re unsure how much time to spend on a problem before peeking at a solution, it can help to measure your problem-solving sessions. For example, my measurements tell me that I have solved 22% of my attempted uHunt problems in less than one hour, and that four problems have taken me more than ten hours each. Along with a gut feeling about whether I’m still benefiting from the problem I’m currently working on, I can use these numbers to decide when it’s time to look for a hint.
Lesson 4: Competitive Programming Isn’t Just About Algorithms
uHunt problems are organized by category. This means that as you start one, you already have some idea of how to attack it. The categories refer to algorithms or techniques that are covered in the CP3 book or in a standard reference like CLRS or Sedgewick. Before tackling a list of categorized problems, you can learn the basics of the appropriate algorithm or technique from one of those sources.
Given this head start that you get for each uHunt problem, what challenges are left as you solve it? One challenge is customizing the algorithm for a specific purpose. UVa 12192 requires a type of binary search that uses an inequality, rather than the standard exact match binary search. To solve the problem, you either have to build that binary search algorithm yourself or, if you’re using C++, recognize that std::lower_bound is what you need. Problem setters often design problems that require contestants to customize their algorithms rather than just using generic versions.
So knowing algorithms and how to customize them is useful for competitive programming. But once you have a certain amount of algorithmic book knowledge, the rest of competitive programming is about problem-solving skills. These skills aren’t completely general. They focus on involve math and algorithmic thinking. But there’s only so much math and algorithms you need for competitive programming before you hit diminishing returns. Learning to find creative solutions to problems, in contrast, is something you can spend almost unlimited time on, and is likely to provide greater benefits in the long run.
(Image credit: John Morgan)