Lessons from uHunt Chapter One

This post is part of a series that considers what can be learned from the problems in each chapter of uHunt, a tool for competitive programming practice. You can find the rest of the posts in the series by visiting my uHunt post category.

This week, I submitted the solution to the last of the 39 starred problems in uHunt Chapter 1. This is part of a learning project that I’m calling Project 462, after the 462 uHunt starred problems.

The problems in uHunt Chapter 1 are introductory and ad-hoc problems. They help uHunt users get familiar with the UVa Online Judge system, and they don’t require any specific competitive programming techniques to solve. Nevertheless, there were quite a few challenging problems in this chapter.

How to Attack a Programming Puzzle contains six tips for using UVa OJ. This post contains my remaining thoughts on solving the types of problems found in Chapter 1.

Statistics

Since I’m in the habit of measuring my work time, I have some statistics about this first chapter:

• I spent a total of 142 hours working on solutions to the 39 problems. That’s about 3.6 hours per problem.
• I submitted the first problem on September 8, 2014, and the last one on April 18, 2015. That’s a total of 223 days of elapsed time, or about 5.7 days per problem.
• At $223/39$ days per problem, the remaining 423 starred problems would take about 2419 days to complete, or about 6.6 years.
• At $142/39$ hours per problem, the remaining 423 starred problems would take about 1540 hours to complete. If I allocate 10 hours per week to working on problems, this is only about 3 years.

If you’re working on a similar project, you may have more or less time per week to devote to it. The key idea is that keeping track of your time will give you a realistic idea of the scope of the project. In my case, I know that it will probably take me a few years at a minimum to get through all 462 problems. Since I want to write about the process, and I also have a full-time job, ten hours per week is probably the maximum I can allocate to solving programming puzzles. If the increasing difficulty of the problems is roughly balanced by increasing speed at solving them due to increased experience, then three years is a reasonable minimum. If I want to complete this project, I’ll have to be willing to devote ten hours per week for that duration.

Tips and Ideas

As I work through the uHunt problems, I’m recording the things I learn in a few different ways:

• Blog posts discussing general ideas about learning and programming puzzles.
• Notes on individual problems, which I plan to consolidate into blog posts like this one at the end of each chapter.
• A reference class of code snippets that can be re-used in future problems. Another way to look at this class is as the subset of Java that is required for programming contests.

While I could get through the problems faster by focusing exclusively on coding, the approach I’m using means I’ll end up with not only the experience of solving the 462 problems, but also with a roadmap to help others with similar projects. It’s also worth pointing out that teaching something to others is a key step in learning a topic well.

Don’t Trust the Input

It’s standard software engineering practice to not trust user input. When you’re using an online judge, you’re the user and your input is source code that the online judge host compiles and runs on its server. It’s basically a security consultant’s worst nightmare.

But from your point of view, the online judge is also providing input in an effort to trip up your program. You don’t get to see most of the input, but you do get a general description of the input that will be used, as well as some sample input. As a general rule, it’s best not to overthink the input rules in a problem description. So if the description says that there will be 110 test cases, you should take that statement at face value when estimating your program runtime. However, there are a few coding conventions that you can use to reduce the number of input issues that you have to debug.

Parsing Integers

Parsing integers from an input string is a very common pattern in programming puzzles. Consider a situation where you need to sum a list of integers. Let String line contain this line of input:

1 2 3 4 5 6 7 8 9 10


A basic way to sum these in Java would be:

String[] tokens = line.split(" ");
int sum = 0;
for (String s : tokens) sum += Integer.parseInt(s);


For normal programming puzzle input this works fine, but it wouldn’t work for this input:

1  2   3 4 5     6 7 8 9 10


Because of the way split works, parsing this line as shown above results in empty strings in the String array, which causes a NumberFormatException when you try to parse the first empty string. This can be avoided as follows:

for (String s : tokens) if (!s.equals("")) sum += Integer.parseInt(s);


But since split accepts a regular expression, a cleaner approach is just to skip over the extra whitespace:

String[] tokens = line.trim().split("\\s+");
int sum = 0;
for (String s : tokens) sum += Integer.parseInt(s);


This works fine if the input line only contains integers. If you need to ignore strings that can’t be converted to integers, then something like this is required:

String[] tokens = line.trim().split("\\s+");
int sum = 0;
for (String s : tokens) {
try {
sum += Integer.parseInt(s);
} catch (NumberFormatException nfe) {}
}


For most problems, the last example is overkill, so I don’t use it by default. But I did find it useful for UVa 161: Traffic Lights. I kept getting a Runtime Error, but once I handled the NumberFormatException, my submission was accepted without any other changes. A post on the discussion board indicates that other people have run into similar problems.

Integer Size

It’s common for UVa problem statements to specify the size of numbers in the input data, but sometimes they leave that detail out. For example, UVa 10812: Beat the Spread! is one of the easiest starred problems (it’s classified as Level 1) in uHunt Chapter 1. After getting a Wrong Answer, I switched my ints to longs and got an Accepted result.

It may be worth just using longs (or the equivalent 64-bit integer type in your language) by default, rather than spending time deciding on a case by case basis whether to use int or long. There may be some performance difference depending on what hardware/OS the online judge is running, but it’s unlikely to be the bottleneck in your solution.

Time Limit and Buffered Printing

The standard three-second UVa OJ time limit isn’t usually a concern for Chapter 1 problems, even if you’re using Java. The algorithms required for these problems just aren’t very time-sensitive. However, I did run into a problem with UVa 579 – Clock Hands. Once again, this is one of the easier starred problems in the chapter. However, the problem setter apparently decided to mix things up by providing an unusually large input set. I initially got a Time Limit error. I was able to resolve it, as suggested in the forum, by adding the solution output to a StringBuilder and printing it all out at the end, rather than printing each output line as I calculated it. BufferedWriter is another potential Java solution.

Problem Statement Quirks

UVa problem statements don’t contain intentional errors. The problems offer enough challenges on their own without having to second-guess literal statements of fact in the descriptions. However, the descriptions aren’t perfect. They can be verbose, unclear, and even incorrect in places. Fortunately, there are supplementary resources that can help.

HTML and PDF

Some UVa problems contain both an HTML description and a corresponding PDF. I always use the PDF if it is available, since the formatting tends to be better. For example, part of the HTML problem statement for UVa 403: Postscript is unreadable due to font spacing issues, but the corresponding PDF is correctly formatted. On the other hand, sometimes the HTML and the PDF have some critical differences. The PDF for UVa 893: Y3K Problem shows a 0 at the end of the sample output. The corresponding sample output in the HTML does not contain the 0, and that is what the online judge expects.

Whitespace

The UVa online judge can be picky about whitespace, even when the problem statement isn’t. For example, the problem statement for 12085: Mobile Cassanova (PDF only, apparently) says that the solution requires “a blank line after the output for each set of input.” However, the judge apparently is looking for two blank lines after the last case in the output. The sample output doesn’t provide any hints about this. In fact, the PDF shows zero blank lines after Case 2. Fortunately, uDebug saves the day for this problem. If you use the Copy Output button, it correctly shows the two blank lines in the output.

Ambiguous Descriptions

Convoluted problem statements are part of the competitive programming game. Partly this is due to the tradition of wrapping a “realistic” scenario around a standard coding problem. There’s also the international makeup of the competitive programming community, which means that problem setters may not be writing in their native language. (Teams even intentionally try to prevent teams from other countries from reading their problem statements). Finally, not spelling out every detail of the problem is one way to increase the difficulty of the problem. In uHunt Chapter 1, an example of an ambiguous problem statement is UVa 556 – Amazing, one of the harder problems in the chapter. The problem describes a robot that solves a maze using the standard “wall follower” approach — in this case, staying in contact with the right wall. However, the description also states that the robot should, when blocked, “turn left until it can proceed.” Even in the sample maze, this advice would seem to lead the robot in circles. As you can see, it is sometimes necessary to follow parts of the problem statement and ignore other parts.

Problem Difficulty

The uHunt starred problem sets contain problems of various difficulty levels. You can save time by modifying your strategy based on how difficult the problem is supposed to be:

• Very easy: jump right in and start coding.
• Easy: make a general plan and then start coding.
• Medium: use a full process, but don’t worry too much about program organization.
• Hard: in addition to the full process, think more about the program structure, including class and method organization.

uHunt provides a difficulty level for each problem. For the starred problems, the levels run from 1 to 5 for the first few chapters, with some Level 6 problems in later chapters. The level indicators are a reasonable starting point, but several factors make it difficult to select a rating that is accurate for everyone. Some of the Chapter 1 problems were written in the late 1990s, and programming language libraries have changed a lot since then. For example, two Chapter 1 calendar-related problems, UVa 893: Y3K Problem and UVa 11947: Cancer or Scorpio, are rated as Level 4. But using the Java GregorianCalendar class reduces their difficulty by at least one level. Whether you want to use a library class or solve these problems from scratch depends on your level of interest in calendar arcana.

In other cases, it’s not clear why the uHunt authors picked the level they did. For example, 12085: Mobile Cassanova is rated as Level 5, which means it should be one of the two most difficult starred problems in Chapter 1. But I found it considerably easier than the other Level 5 problem, UVa 1061 – Consanguine Calculations or even the Level 4 problems. At the other end of the scale, UVa 195 – Anagram is rated as Level 2, probably because it’s essentially identical to a common college assignment. But I found it impossible to solve in Java due to performance issues. (I submitted a simple C++ solution). So language and background can have a large effect on actual difficulty. One way to calibrate your own difficulty scale is by measuring how long it takes you to solve each problem. Reviewing these measurements can help you decide where to focus your practice time.

Programming Style

One of the reasons to look at the problem level indicators is to decide up front what kind of programming style to use when you start to implement a solution. Competitive programmers are well-known for using a programming style that would never work for code that has to be maintained over time by multiple developers. But for beginning competitive programmers, there isn’t much benefit to using techniques like short variable names and long functions. Unless a problem is very easy (maybe Levels 1 and 2), up-front planning time will pay for itself in reduced debugging time. And for problems with a tricky implementation — for example, UVa 403: Postscript — it may make sense to approach the problem the way one would approach a real programming project, even though you’re only going to use the code once. There will be plenty of time later to learn tricks to improve your implementation speed.

Chapter 1 in Review

uHunt Chapter 1 lived up to its description. With the exception of some outliers like the chess problems, the problems were generally solvable with at most a few hours of thinking, and some well-known Java collection classes. Chapter 2 promises to throw a few more data structures into the mix.

(Image credit: uHunt)