Review: How to Win Coding Competitions by ITMO University

ITMO

Last month, ITMO University launched an edX course called How to Win Coding Competitions: Secrets of Champions. With this first iteration of the course coming to an end, I thought I would discuss my experience with it.

What the Course is About

The idea behind How to Win Coding Competitions (HTWCC) is to take people with some amount of programming experience (maybe a little, maybe a lot) and, in seven weeks or so, teach them the basics of competitive programming.

You may already see a contradiction between this goal and the title of the course. The course is about getting started in competitive programming, not about winning competitions or advanced secrets. But for now, let’s take it at face value.

The course is divided into five sections, each lasting one week:

Week 1: Welcome to Competitive Programming

The first week consists mainly of basic contest information and easy problems that students can use to get familiar with the online judge used in the class. However, the instructors do throw in one challenging number theory problem this week, just to keep things interesting.

Week 2: Computational Complexity and Linear Data Structures

The Week 2 lectures review analysis of algorithms, big O notation, and basic linear data structures like stacks, queues, and lists. The problem set starts simply, but quickly becomes more challenging.

Week 3: Sorting and Searching

This week covers binary search, as well as standard sorting algorithms like Insertion Sort, Quicksort, and Mergesort. At this point, the easy problems are over. All of the problems for this week require some thinking about how apply sorting and searching concepts to programming puzzles.

Week 4: Algorithms on Graphs

The final lecture week covers graph data structures, and how to use them to implement algorithms like depth-first search, breadth-first search, and single-source shortest path. The problems require students to implement these algorithms for specific scenarios.

Week 5: Exam

There’s a week allocated for this, but the exam itself only lasts five hours.

Why Take This Course?

There are plenty of online judges where you can find practice problems. But solving random problems isn’t a very efficient way to learn until you have all of the basics down. The advantage of a course or a book is that it gives you information to study, followed by practice problems. There’s a reason why college math and science courses work this way. Problem sets are an efficient way to figure out what you do and don’t understand about the material. If you run into trouble with a problem, you can immediately head back to the appropriate resource (for HTWCC, that’s a lecture slide and associated video section) and figure out what you’re missing.

At some point, it becomes useful to practice problems that haven’t been pre-categorized. That style of practice forces you to figure out not only how to apply an algorithm or technique to a problem, but also which algorithm or technique to use. But participating in contests is probably the best way to get this type of practice. In the early days, you can find plenty of challenges even when you are given a general idea of what approach to take.

So the main reason to choose this course over the many other study options is to have a group of experts walk you through a set of resources, and then test yourself on a problem set that has been custom-written for those resources. The video lectures also make this feel like more of a real class compared to something like Stanford’s CS 97SI: Introduction to Programming Contests, where only the on-site students get the lectures. And if you take the course during one of the live sessions (like the one from October-December 2016), you get the added advantage of enforced deadlines and instructor participation in the forums.

HTWCC vs. Other Study Options

How does this course compare to other options for studying competitive programming? Let’s look at some characteristics.

Solutions

During the live course, editorials weren’t available until after each problem set was due. This is the standard approach for college courses and MOOCs. But it differs from many self-study options, where you can seek out solutions whenever you decide that you have spent enough time on a problem. So there’s a trade-off between flexibility and enforced discipline. It’s possible that once the course is archived, editorials will be available at any time.

The course does have a discussion section, and there the benefits are reversed: during the live course, the instructor offered hints while the problem set was active. After the course is archived, there may not be any instructor participation, though you may be able to view archived discussions.

Sharing

As with other college courses, collaboration is both encouraged and restricted. Instructors want students to help each other with problems. But they also want each student to submit their own work, so it’s important not to give too much away about the problems. In contrast, other competitive programming communities are usually happy to have people write editorials about problems. Even Project Euler, which doesn’t like people discussing its problems in public, provides editorials after you have solved a problem.

Since explaining things to others is a good way to learn, one benefit to using open collections of competitive programming problems is that you can talk about them all you want.

Online judge

The course uses an online judge that integrates into the edX environment. It has a few quirks:

Rather than reading from stdin and writing to stdout, solutions must read from files whose names change for each problem. That creates some template editing busy-work at the beginning of each solution.
Early in the course, the judge crashed on a few separate occasions and stopped accepting submissions. The instructor got it under control later in the course.
The input file only contains only one test case (which can include multiple lines). This can make testing less convenient compared to judges that support multiple tests cases per input file.
There’s no runtime output other than the judge verdict. For example, there’s no timer, so you can’t tell whether your solution barely came in under the time limit, or had plenty of extra time.
There’s no history of previous submissions other than a counter indicating how many submissions you have made for a problem.
There’s no leaderboard. Seeing how other students have done on the problems is not only helpful to gauge problem difficulty, but could also foster community among the participants. To avoid any privacy issues, students could opt in to appear on the leaderboard.

But other than those items, the judge was fine. It got the job done.

Lectures

HTWCC has no assigned textbook or other significant reading assignments. The information required to solve the programming problems is covered in a total of 34 short lectures, most of which are followed by one or two multiple choice questions. The lectures last about 4.25 hours in total, with about 90% of that time spent in weeks 3 and 4.

Since the programming problems appear to be written specifically for the class, they are closely related to the lecture content. So even if, like me, you have studied these topics before, it’s worthwhile to at least skim the lectures. I found it useful to watch the lectures at 2X speed, which works fine because they include a transcript that is synced to the video. So you don’t have to listen to the audio very carefully.

The lectures have some tips about techniques that are common in competitive programming, like using bitwise operations to speed up some algorithms. And the topics that the instructors choose to cover is based on what is most likely to be useful in programming contests. But for the most part, the lectures cover material that can be found in any standard algorithms textbook or course.

Since the lectures mainly cover standard algorithms topics, you could decide to assign yourself a textbook like CLRS or Sedgewick, and use that for a more detailed explanation of quicksort, depth-first search, or the other algorithms in the course.

Discussions

Each programming problem and lecture in the class has an associated discussion thread. The lead instructor was surprisingly active in the programming problem threads. Students would post questions like, “I got a wrong answer on test #9. What’s wrong with my code?” and the instructor would read their code and provide a detailed diagnosis. That won’t be scalable in the long run if the class gets bigger, but it does mean that the discussion thread is a good place to look for hints about problems that you’re stuck on.

Process

Here’s the study process that I used each week:

Look through the programming problems to see what topics they cover.
Watch the next lecture on 2X speed to get an overview of the material, using the transcript to keep up with the spoken words.
Solve the multiple-choice problem(s) for the lecture.
If the lecture seems relevant to the next programming problem, start the problem, returning to the lecture when necessary to get more detail on the appropriate algorithm.
Repeat until done for the week.

For the programming problems, I used the process that I already have in place for uHunt. I modified my template and command-line tools to match the style that the HTWCC judge requires. Although there’s no program submission API, the remainder of the tools (including my git workflow) worked fine.

In week 5 of the class, there are no lectures or quizzes, just a timed exam consisting of programming problems. For that week, my strategy was to read through all of the problems first and work on them in order of difficulty.

Debugging

For competitive programming practice, I usually use uHunt problems. Each of these problems has a corresponding uDebug page that provides accepted output for any input. That system allows you to use random input (or sample input that uDebug users upload to the site) to compare your program’s output with accepted output, and fix any bugs that cause your output to differ from the accepted version.

With HTWCC problems (and problems from many other sites), you don’t have that advantage. Nevertheless, random input still plays a critical role if you’re stuck on a problem. (Random input, by the way, is input produced by a program that generates data in the format specified by the problem statement. Such a program is generally much easier to write than a program that solves the programming puzzle).

With an unlimited supply of random input in hand, you can do the following:

If you get a Wrong Answer verdict, implement a more straightforward (but probably slower) version of your solution. Then compare its output with the output from the optimized version that you’re working on. You may not be able to get your slow solution accepted, but you can use it to debug your fast solution.
If you get a Runtime Error verdict, you can use random input as a brute-force strategy to find the input that causes your program to crash. Just keep generating and running until it happens.
If you get a Time Limit Exceeded verdict, you can generate enough random input to make your program run for a few seconds. That helps get useful results from a profiler, and also ensures that your output doesn’t change as you tweak your program to make it run faster.

Effort and Difficulty

Effort

According to the main HTWCC page on edX, the course lasts 5 weeks, and requires 4-6 hours per week of effort. That works out to a total of 20-30 hours of effort. The course site opened up on October 17, 2016, and the final exam for this offering of the course is due on December 4, 2016. Since the lectures and problem sets for each week were made available well before their due dates, I would count the full seven weeks as potential study time, for a total of 28-42 hours of effort. In my opinion, all of those numbers underestimate the actual level of effort required for a serious attempt at the course.

Here’s why I say that:

As I mentioned above, there are 4.25 hours of videos. Watching them at 2X speed would cut that in half, but the point of watching quickly is to skim through the easy parts to free up time for studying the hard parts. So let’s assume 5 hours total for a combination of 2X watching, slowing down when things get interesting, and answering the multiple choice quizzes.
The final exam is set at five hours, to simulate an ACM-ICPC competition. There are enough problems on the exam that there’s no reason not to use the full amount of time, unless you have a lot of contest experience. (In which case, why are you taking this introductory course?)
So before we even get to the problem sets, we’re at 10 hours of study time. Then there are eight problems per week, or 36 problems total. The first six problems in Week 1 don’t really count since they’re just warm-up problems. So let’s say 30 real problems plus some warm-up time. Getting to 20 hours (the low end of the effort range) would mean spending less than an hour per problem, plus the 10 hours already allocated. Even the high end (42 hours) would only provide about an hour per real problem. I would suggest allocating a couple of hours per problem on average, for a total of 60 hours of problem-solving time. That brings the whole class to 70 hours, or 10 hours per week.

In reality, you may still find that number to be on the low side if you’re serious about the class, haven’t done many competitions, and want to finish all of the problems. You could spend ten hours on one problem and consider it time well spent if it was ten hours of research and learning.

Difficulty

HTWCC is advertised as Introductory level on the edX Introductory – Intermediate – Advanced scale. That’s a reasonable categorization. It requires some programming skills, but nothing fancy. The lectures cover all of the algorithms, data structures, and techniques required to solve the problems. In theory any motivated programmer could jump right in.

But the course designers don’t hold back on problem difficulty. There are plenty of challenging problems for beginning and intermediate competitive programmers. On the uHunt scale, I would put them at L3 and L4 (except for the first few problems in Week 1, which are L1 difficulty).

Summing Up

There’s a lot of material online for learning and practicing competitive programming (see the Awesome List). So what’s special about HTWCC? Mainly the following: it’s the only real competitive programming MOOC out there. The Open Courses section of the List links to lecture slides, videos of in-person classes, tutorials, and other materials. But HTWCC is the closest thing to a university class on competitive programming that’s available to people who aren’t enrolled at a university that offers such a thing. It has instructors, lectures, homework, deadlines, and an exam all packaged into a course.

Given that the problems are good and the lectures are OK if you’re going to do the problems, HTWCC is worth looking into if you’re serious about learning competitive programming. It’s not a must-take course, but it’s a good use of study time. You won’t be winning any major competitions after finishing it, and there are no real secrets other than studying the right topics and thinking hard about the problems. But on your way to your first 1000 practice problems, you could do worse than these thirty.