Last week, I wrote about ways to improve runtime performance for a Java solution to UVa 732. This week I’m going to cover a process for analyzing Java program performance using the profiling features of the VisualVM Java troubleshooting tool. But first, a note about profiling. As I mentioned last week, even a highly optimized program can fail to be accepted by an online judge if it uses the wrong algorithm. In other words, you generally can’t profile your way out of a slow design. Nevertheless, looking at a VisualVM snapshot of your implementation can provide some useful performance insights. Just don’t spin your wheels for too long making tiny adjustments to your implementation. You may need to go with a different design instead.
Programming puzzles are often designed in such a way that getting your solution to complete under the time limit is at least as challenging as getting the correct result. To create such a challenge, a problem setter can adjust the size of the input until sub-optimal solutions no longer run in under the time limit.
Many puzzles can be solved using both a slower but easier approach and a more sophisticated method that runs within the required time limit. Among the uHunt starred problems, 732: Anagrams by Stack is one in which people have found performance particularly challenging, at least based on the forum threads. As with previous anagram problems, and performance-sensitive problems in general, getting Java to perform at the required level can be especially difficult. While some online judges provide wiggle room for languages with more overhead than C/C++, UVa Online Judge doesn’t seem to use that policy.
You can read a lot on Quora about the best language to use for competitive programming. Here are some of the points covered by those questions:
- C and C++ execute quickly, and their macro support can reduce the amount of code that you end up typing in your solution.
- A language like Java can be useful for problems with some specific requirements (such as integers that don’t fit in 64 bits, or calendar problems).
- The main contributor to execution speed is the algorithm that you use, not the language that you choose to implement it. But the language can provide a performance edge at the margins.
- Choice of language is less important for more recent contests, since problem setters have made an effort to level the playing field (e.g., by testing Java solutions to ensure that the time limit is sufficient).
I decided to use Java for Project 462, mainly because it’s similar to my primary language (C#), and I’m more interested in learning about problem solving and algorithms than learning a new language that I’m unlikely to use much outside of competitive programming.
One thing about the uHunt problems that I’m working through is that they draw from a database of contest problems going back to the 1990s. Competitive programming and programming languages have changed a lot since then, so what the problem setters were going for in the original contest may not match up with how a contestant sees the problem today. Modern contests tend to be more forgiving of the slower execution time of languages that aren’t C or C++, and they know about the fancy libraries that programmers have access to.
Last week I wrote about Solving UVa 11340 in Java, and covered some performance tips related to reading files that are larger than those typically found in programming puzzles. It turns out that the very next starred problem, UVa 12356: Army Buddies, is an even stricter test of I/O performance. And for this one, there is no particular hint in the problem statement that I/O will be an issue.
Once I came up with an Accepted solution for UVa 12356 in Java, I decided to do some more benchmarking, and use the results to update my solution template. Figuring all of this out once is educational, but I’d rather not be fiddling with I/O issues for every problem that happens to have large input or output requirements.
UVa 11340: Newspaper, despite being ranked at only Level 2 difficulty on uHunt, turned out to be rather tricky. Apparently others thought so too, judging by the 11 pages (151+ posts) of discussion on the UVa OJ message board. Many of the message board posts focus on the characters used in the test input. The consensus is that they are 8-bit characters (with values from 0 to 255). At a minimum, these characters need to be stored in an
unsigned char data type in C++. Nevertheless, people seemed to run into problems even after getting that hint. I solved the problem in Java, which doesn’t have an unsigned char data type, but it has its own set of difficulties. I’ll cover the two issues that I ran into when solving this problem.
This post is part of a series of commentaries covering each chapter of Competitive Programming 3 by Steven and Felix Halim. You can find the rest of the posts in the series by visiting my CP3 post category.
Many of the problems in the UVa Online Judge are taken directly from past ACM-ICPC contest problems. If you’re preparing for this contest or the IOI (which targets a subset of ICPC content), it makes sense to be familiar with these problems. But even if you’re planning to compete on platforms like TopCoder and CodeForces, it can be useful to train using UVa OJ problems, despite the platform’s quirks. Competitive programming problems tend to cover similar topics regardless of the contest platform, especially when it comes to easy and medium problems. The difference is mainly about which topics are emphasized more.
Because UVa OJ has been around for a while, several books use its problems as exercises. One of these is Competitive Programming 3 (CP3), the companion book to the uHunt site. Last week I wrote about the Chapter 1 uHunt starred problems. This week I’m going to cover some highlights from the corresponding chapter in the CP3 book. I’m using the 3rd edition, but you can find similar (but older) content in the free 1st edition ebook.
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.
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.
When you start solving programming puzzles like those on uHunt Chapter 1, what are you learning about? The obvious answer is that you’re learning about competitive programming. After all, uHunt has a companion textbook called Competitive Programming, and many programming puzzle sites are associated with the competitive programming community, or even run their own contests. But I don’t think that’s the right way to look at it. First of all, there’s not much competition happening when you’re first getting started. You may be using a site where the only rating is the number of problems submitted. Or if you are participating in real-time contests, you may not be making it through many problems before time runs out.
If you want to get a lot better at a skill, you need a process for practicing it. When you follow a process, it encourages you to practice in a consistent way, rather than using whatever practice technique you happen to feel like using on a given day. As you get experience using your process, you can look for ways to improve it. In fact, improving your process should be a step in your process, since improvements makes your practice more effective every time you use the process. In this way, you can set up a virtuous cycle where your practice helps you improve your process, which in turn improves your practice. Here on Red-Green-Code, I’m working on a process for getting better at programming.
As I mentioned in my post introducing Project 462, I have spent some time in the past working on historical CodeForces problems to get some idea of what their programming competitions are like. I thought it would be interesting to go through one of those problems, Hot Bath, from the perspective of a CodeForces beginner. In CodeForces Beta Round #93, Hot Bath was Problem C in the Division 2 contest, and Problem A in the Division 1 contest. In the CodeForces system, that means the problem is targeted at Division 1 (more experienced) contestants who are just getting their fingers warmed up at the beginning of a contest, and at Division 2 (less experienced) contestants who have finished a couple of easier problems, and are ready for something that requires more thinking. Based on the information in the standings report for that round, several top Division 1 contestants submitted an accepted solution in about ten minutes, so we can take that as a reasonable lower bound.
The Story So Far
Long ago (2008), I read a post on the “xkcd blag” (yes, Randall Munroe occasionally just writes regular blog posts) about “a site with a lot of math-oriented programming problems that you can solve in any language.” I like math and programming, so that seemed like fun. I spent a few years on and off working through the first 76 problems on Project Euler, at which point the problems started to require more math than I had at my disposal. Around that time (2011), I heard about a site called CodeEval that was coming out of beta. CodeEval also has programming puzzles, but with less of a math emphasis. As I’m writing this post (early 2015), I have finished 107 puzzles on CodeEval. Back in 2011, a site called CoderCharts (no longer online) was briefly popular. CoderCharts hosted contests that ran over several days, like the long contests on CodeChef. That was my first experience with contests that allowed participants to compete against each other during an event. However, the schedule allowed a day or so for each problem, so there was plenty of time to think.