To get better at programming or math, it’s not enough to read about a topic. You have to solve problems. And solving problems is a lot more beneficial if you have access to solutions, especially ones with detailed explanations. But as useful as solutions are, they also present another problem: when is the best time to look at them?

Solving a problem yourself improves your understanding of a concept more than reading someone else’s solution. If that wasn’t true, then it would be possible to learn a technical subject just by reading about it. That would be easier, but it doesn’t work. So you need to struggle with problems.

However, you can’t avoid looking at the solution forever. Problems in textbooks or online judges are intended to be solved in hours or days. They aren’t unsolved research problems that take months or years to solve. (Or if they are, they’re clearly marked as such — e.g., some of the problems in Knuth’s books).

So part of your job as a problem-solver is to settle on the best time to look at each solution.

« Continue »

When I came up with 12 Reasons to Study Competitive Programming, I picked the following for reason #3: Studying competitive programming gives you a way to practice solving hard problems.

(As I pointed out in the article, this is also a reason that some people give for not studying competitive programming. They claim that most software developers work only on trivial problems. So they don’t see any reason to practice solving hard problems. That has always seemed to me like a backwards argument).

What does it mean for a problem to be hard? To answer that, I’ll borrow part of the definition of deep work: a problem is hard if it requires specific training and experience to solve. While some ad-hoc competitive programming problems can be solved by any programmer willing to spend an hour or so thinking and coding, modern contests contain problems that only programmers who have spent considerable effort practicing can solve in a reasonable amount of time.

That’s the type of hard problem that I’m talking about. To be hard, a programming problem doesn’t have to involve an unsolved research question. But it does need to provide a challenge to people who spend a lot of time solving puzzles.

What makes competitive programming hard? Here are some factors.

« Continue »

If you have a question about competitive programming, Quora is a good place to find the answer. Quora’s Competitive Programming topic attracts experienced competitive programmers, and they have written answers to a variety of common questions that beginning and intermediate programmers have about the subject.

It has been a few years now since the Quora topic was created, and most questions about the fundamentals of competitive programming have been asked and answered. While there are still new questions about specific problems, and about current events, it’s rare to see a new question about fundamentals.

« Continue »

UVa 108 is rated as a Level 1 (easy) problem by uHunt, but its solution nevertheless contains some interesting techniques. Here’s a summary of the problem statement:

Given an $N \times N$ array $A$ of positive and negative integers, print the sum of the nonempty subarray of $A$ that has the maximum sum. The sum of a subarray is defined as the sum of its elements.

uHunt lists this problem in the section called Max 2D Range Sum, a subcategory of Dynamic Programming. But before we get into the dynamic programming solution, let’s examine the Complete Search approach.

« Continue »

Over the past couple of weeks, I have been writing about deliberate practice as described in Peak by Anders Ericsson and Robert Pool. The book describes three types of practice: Naïve practice, purposeful practice, and deliberate practice. The latter two types of practice are both effective, but there’s a key difference that makes deliberate practice the best choice. The difference is where your training plan comes from. Purposeful practice can be used with any reasonable plan. Deliberate practice requires that you practice using a plan that has been proven to work by an expert who has gone before you and achieved success in your target field.

How might we find an expert training plan for competitive programming? This type of programming is different from regular software development. So it won’t do to use a standard programming training plan, as provided by a university curriculum or a programming boot camp. Competitive programming is taught as a specialty in some universities, where coaches devise their own training plans to build winning teams each year. But that’s only useful if you’re a student at one of those universities. There are a couple of books specifically about competitive programming, including Competitive Programming 3, which I’m in the process of writing a chapter-by-chapter summary for.

But for today’s purposes, I’m going to cover training advice provided by competitive programming experts on Quora, specifically in answers to the question What is the best strategy to improve my skills in competitive programming in 2-3 months? Over time, that question has become a merge target for a number of similar questions, and quite a few experienced competitive programmers have weighed in with suggestions.

« Continue »

Last week, I wrote about the concept of mental representations, an important topic in Peak by Anders Ericsson and Robert Pool. According to the authors, learners seeking expertise should have as their goal a virtuous cycle between mental representations and deliberate practice: Deliberate practice should produce more effective mental representations, and more effective mental representations should drive better practice.

This week I’ll be covering the other half of that virtuous cycle, deliberate practice.

« Continue »

Two weeks ago, I introduced the concept of memoization for dynamic programming, using as an example UVa 787. That problem involves operations on a sequence of integers, a one-dimensional structure. UVa 10755: Garbage Heap increases the problem complexity by organizing its integer data into a three-dimensional shape, a rectangular parallelepiped. Nevertheless, we can use memoization in a similar way to solve this problem.

« Continue »

This week, there was a question on Meta Stack Overflow about the right way to ask Competitive Programming questions on Stack Overflow. To the uninitiated, Stack Overflow might seem like a good place to ask questions about Competitive Programming. It’s the standard place on the Web to ask programming questions, and competitive programming is about programming, right?

« Continue »

In programming contests, some algorithms and techniques get more emphasis than they do in school or in professional programming work. One such technique is dynamic programming. CP3 has this to say about dynamic programming:

This technique was not known before 1940s, nor frequently used in ICPCs or IOIs before mid 1990s, but it is considered a definite prerequisite today. As an illustration: There were ≥3 DP problems (out of 11) in the recent ICPC World Finals 2010.

As you might expect for such a popular competitive programming topic, uHunt has twenty-one starred problems, divided into seven sub-categories, for dynamic programming practice. As I make my way through that list, I’ll be writing about a selection of these problems. Today I’ll cover the first one, UVa 787: Maximum Sub-sequence Product.

« Continue »