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.
I recently finished the last of the 37 starred problems in uHunt Chapter 2. I’m solving these problems as part of a learning project that I’m calling Project 462, after the 462 uHunt starred problems.
Chapter 2 highlights problems that require more specific data structures than the ad-hoc problems in Chapter 1. The chapter starts out with arrays, covers familiar data structures like stacks and queues, and ends with problems that use Segment Trees and Fenwick Trees, data structures that you may not have heard about in college.
The uHunt approach is to categorize problems by the algorithm, data structure or technique that the authors recommend using to solve them. In addition to the category, each problem has a level — generally 1 through 4 — indicating its difficulty level. The Chapter 2 problems mostly use the same range of levels as the Chapter 1 problems. But for each Chapter 2 problem, there is an extra step of learning or reviewing the appropriate data structure. Although they start with a data structure recommendation, most Chapter 2 problems still require problem-solving techniques and creative thinking.
In many competitive programming situations, you won’t know which data structure to use in advance. The goal of the uHunt style of practice is to get familiar with the range of problems that you’ll come across, so that you know which data structure, algorithm, or technique to use when you see a similar problem in the future.
Statistics
My goal is to finish all 462 starred problems in uHunt v3. In the interest of achieving that goal, I’m collecting some statistics along the way. Here are some numbers for Chapter 2 and for the problems so far:
- I spent just over 156 hours on the 37 problems in Chapter 2, or about 4.2 hours per problem. That’s a slighly slower pace compared to Chapter 1 due to problem 11402, which I found rather tricky and spent a lot of time on. The good news is I now have a reasonably complete understanding of how segment trees work.
- I submitted the last Chapter 1 problem on May 1 and the last Chapter 2 problem on October 30. That’s 194 days of elapsed time, or about 5.2 days per problem, roughly the same rate as for Chapter 1.
- Considering elapsed calendar time, my overall problem-solving rate for both chapters is now $418/76$ days per problem. At that rate, the remaining 386 problems will take 2024 days, or about 5.5 years.
- Considering only actual hours spent, my overall rate is $326.6/76$ hours per problem. If I spent 10 hours per week on them, the remaining 386 problems would take about 3.2 years.
As I mentioned in the Chapter 1 writeup, this is going to be a long-term project.
The Problems
If you’re interested in competitive programming practice, I would recommend trying the Chapter 2 problems before reading this section. Like the short problem hints in the Competitive Programming 3 book, these comments may give away some tips that you would prefer to discover yourself. But if you’re having trouble with a problem, you should definitely take a look at the appropriate section below. There’s only so much you can learn from struggling with a problem on your own, and a short tip can get you moving again without requiring that you look up the whole solution.
Here we go:
A basic Level 1 problem. Nothing more to say about this one.
Very tricky for a Level 2 problem. To get an accepted solution, I had to do some research into character sets and file input performance. You can read all of the details in Solving UVa 11340 in Java. The key points:
- In Java, when you’re dealing with characters beyond ASCII 127, you need to explicitly specify a character encoding for reading or writing.
- Use
BufferedReaderto read input data. It’s much faster thanScanner, and I haven’t found any downside to using it. You can find the syntax in my solution template.
Another problem that emphasized I/O performance. This time, output performance was also a consideration. I summarized my findings in Why is Java I/O Slow? and updated my solution template so I rarely have to worry about I/O performance anymore. (But see UVa 11402 near the end of this list for an exception).
A basic 2D array problem. I’m not sure why it was categorized as Level 4.
A simulation problem. This is a type of problem that can be solved by implementing rules — in this case, legal game moves around a grid — and running them until you arrive at a solution.
For this problem, my first simulation was too literal and therefore not fast enough. To speed it up, I had to implement a few shortcuts to allow the game piece to jump around the board (while not violating any rules) rather than moving from square to square. I’ve played board games with people who do that. You have to keep an eye on those people to make sure they’re not cheating.
Not a terribly difficult problem, once you work out what the math notation means. Most uHunt problems involve some kind of mathematical thinking, but they usually keep it out of the problem description, at least in Chapters 1 and 2. This problem is an exception.
A level 1 problem because it can be solved easily using next_permutation, a function in the C++ Standard Library. If you’re using Java, it’s worth spending the time to write your own version of next_permutation. Permutations come up periodically in puzzle solutions. For exampe, they were used in UVa 195 – Anagram from Chapter 1.
If you’re having trouble writing a good permutation function, check out this excellent tutorial from Project Nayuki.
UVa 10107 – What is the Median?
I would classify this as a Level 2 problem, rather than Level 1. How hard can it be to find the median of a list of integers? It turns out that it’s tricky to do it efficiently while new values are being added to the list. The CP3 book’s hint provides a suggestion for C++ programmers. In Java, this problem can be solved using two PriorityQueues, even though this problem isn’t in the priority queue section of the chapter.
UVa 10258 – Contest Scoreboard
Not too difficult, but you do have to read the instructions carefully. A sorting problem.
UVa 10264 – The Most Potent Corner
Given the uHunt hint that this is a bit manipulation problem, this didn’t strike me as a Level 4 problem. Using bitwise operators, there’s a simple and short solution.
This is a good problem to test your understanding of BitSet (bitset for C++). One quirk I found in this problem: it’s possible to arrive at the solution before you finish reading the input. Don’t forget to read the rest of the test case before moving to the next one. I forgot to do that and, not surprisingly, got some strange results.
A typical Level 3 problem: Short solution, but requires some thinking to get there. I’m starting to find that bit manipulation are shorter (less code) on average than other problem types. One thing I learned from this problem: A Runtime Error verdict will occur if you try to access an array element that is out of range. So that’s one thing to check if you get that verdict.
Obvious lesson of the day: When iterating through a linked list, using ListIterator is a lot faster than using a loop and the get method. This shouldn’t be a big shock, since linked lists don’t support direct access to internal nodes.
A standard Level 2 problem that can be solved using a stack. That’s about it.
A tough Level 4 performance challenge. Anagrams are a popular topic in UVa puzzles. As the number of characters in a string increases, the number of possible anagrams of that string increase exponentially. As a result, it’s not practical to look through all of them. In Implementing a Fast Solution to UVa 732, I go through various ideas for speeding up my solution to this problem by reducing the number of anagrams that need to be generated. The second-last of my attempts was quite fast, but only the last one was fast enough to get my Java solution accepted.
Much easier than a typical Level 4 problem. The problem description clearly identifies the data structure to be used (one or more Stacks). The solution requires finding a minimum, but there are only two possible answers, so you can easily solve the problem by picking the smaller of the two.
UVa 10172 – The Lonesome Cargo Distributor
A typical Level 4 problem. Required a moderate amount of code, and some debugging time.
A good Level 4 simulation challenge. I submitted some critical input to uDebug to test an ordering bug that the random input didn’t expose in my solution.
Reasonably easy Level 3 simulation problem. Be careful to use the correct unit of measurement.
An easy Level 2 problem to kick off a section of tree-related problems. This one also involves trees of the biological variety.
I ran into the two-second time limit on my first submission, but it wasn’t a lot of trouble to optimize.
This is categorized as a Level 3 problem, but I found it harder than even a typical Level 4 problem. Solving it required a couple of key insights to get an efficient solution, and then a further performance optimization to get it under the time limit. As part of that performance optimization, I decided to use arrays rather than the suggested TreeMap. I wrote up the full story at UVa 11572: Unique Snowflakes.
I found this one (categorized as Level 3) to be easier than the snowflake problem, so I would swap the level designations between these two. This problem doesn’t require any major conceptual breakthroughs, but there are some details to get right. If you’re using Java, it’s a good opportunity to learn about the differences between TreeMap and TreeSet, which I did. I also used this problem to try out the idea of using test-driven development (TDD) to solve programming puzzles. You can read about that experiment in Solving UVa 978 With Unit Tests.
A straightforward Level 3 simulation problem.
The algorithm is a tiny bit tricky (coordinating two TreeSets) for Level 3, but only requires about 35 lines of code for the solution.
Similar to the previous one, but with a bit more code.
This turned out to have a simple greedy solution, though my first attempt was more complex (trying all combinations — too slow). Once I fixed that, my solution still had a bug, which leads me to the following recommendation: when debugging, check values that the problem doesn’t ask for as well as ones that it does. The goal of this problem is to find the minimum cost value, but there’s also an intermediate sum value. If there’s a bug in the sum calculation, testing that value directly is easier than trying to track down why the cost is wrong. This is also the reasoning behind splitting your solution into multiple pieces and unit testing each one separately.
UVa 11995 – I Can Guess the Data Structure
Another straightforward Level 3 simulation problem.
UVa 599 – The Forrest for the Trees
This is the first problem in the “Data Structures with Our-Own Libraries” section, but I found it more convenient to solve using standard Java data structures (HashMap and TreeSet). I’m not claiming that mine is a better solution, but it wasn’t too painful. Here are the two lessons that came out of debugging my solution:
Watch out for duplicate input values. I often use randomly-generated test input in conjunction with uDebug. For this problem, I generated some of my own using a simple process with no checks for duplicate graph edges. The uDebug solution handled this correctly but my solution incorrectly double-counted. In most cases, it’s best to code your solution to handle messy input, rather than fixing the random input. You never know what kind of quirky input the online judge is going to throw at you.
Don’t forget that an edge can cause two trees to merge if it connects a vertex in one tree with a vertex in another. Handling a merge correctly is a basic part of graph algorithms, and of the solution to this problem.
An example of an implicit graph problem. I didn’t use any special data structures for this problem either, other than arrays and a custom Element class (like a graph node) to keep track of matrix elements.
UVa 11991 – Easy Problem from Rujia Liu?
Can confirm. Was easy. I would put it at Level 2.
Three problems into the section, and still no sign of custom libraries. I used nested HashMaps for this one.
Custom libraries! The CP3 companion site has a download page with downloadable code for each chapter. This problem can be solved using a simple application of the CP3 UnionFind class. One thing to note from the problem description: the input data is 1-based.
Easy enough without UnionFind. One comment on the problem description: when it says “if one slept area X of the brain is directly connected to at least three awake areas,” it really means directly. In graph terminology, X must be adjacent to at least three awake nodes (there must be edges beginning at X and ending at each of them).
With UnionFind available, this is a Level 1 problem. The problem-specific part of the solution is just a few lines of code.
The first of the SegmentTree problems. Besides the SegmentTree code, this one also requires some thinking, and a screen or two of solution code.
The ultimate SegmentTree problem. As far as I know, there is no standard library containing a full Segment Tree implementation for Java or C++, though a few custom implementations are publicly available. Regardless of the one you pick, you’ll need to make changes to meet this problem’s requirements. You can find all of the details at Solving UVa 11402 with Segment Trees.
After I updated my solution template for UVa 12356, this is the first problem where I ran into I/O performance issues. It turned out that the test input was very large, and my solution template was making an extra copy of it, which pushed the execution time over the limit.
The last problem in the chapter lends itself to Fenwick Trees. I used a few of them to solve it.
Thoughts on Chapter 2
The purpose of this chapter is to practice solving problems that are designed to use particular C++ or Java data structures. Since the data structure to use is specified in the uHunt section, the process for completing each section is:
- Learn general information about the data structure, from an algorithms textbook or similar resource.
- Learn about your target language’s implementation of the data structure, from the language documentation or another reference.
- Get practical experience using the data structure by solving the problems in the section.
You could learn algorithms for competitive programming by reading an algorithms book or website. But there’s a benefit to the feedback that you get by learning about a data structure or algorithm and then immediately solving related problems. The only missing part is selecting the appropriate data structure yourself. At some point you have to practice that as well.
In some ways, Chapter 2 is easier than Chapter 1, because the data structures are specified for you. Chapter 1 has categories like Game (Chess), Anagram, and Interesting Real Life Problems, Harder, which leave the choice of data structure open. The Chapter 2 categories are all data structures and libraries, so you always know where to start (or at least where the CP3 authors think you should start).
Coming Up Next
Next week, I’ll continue my review of Chapter 2 with a commentary on Competitive Programming 3, Chapter 2, the companion chapter to these uHunt problems.
(Image credit: uHunt)