Mental Representations for Competitive Programming Practice

Brains

Psychologist and deliberate practice pioneer K. Anders Ericsson has been studying and writing about deliberate practice for decades, and his landmark 1993 paper provides an accessible introduction to the topic. This year, he published his first book-length exploration of deliberate practice for a general audience. Peak: Secrets from the New Science of Expertise explains the idea of deliberate practice from the ground up, and provides examples of how people have used it in different fields. I started this blog with the goal of studying and explaining deliberate practice techniques for software developers. This week and next, I’ll be applying the ideas from the book to that end. As usual, I’ll be drawing my examples from competitive programming practice.

The topic for this week: Mental representations.

Mental Representations

When you’re working on a programming problem, even an artificial one like a contest puzzle, you can’t just upload the problem statement directly into your brain and start manipulating it. You first have to read the problem, understand it, and convert it into a form that you’re familiar with. The exact form that you use will depend on the mental representations that you have available.

Here’s the definition of a mental representation, from Peak:

A mental representation is a mental structure that corresponds to an object, an idea, a collection of information, or anything else, concrete or abstract, that the brain is thinking about.

The book provides numerous examples of mental representations, including these:

  • Words are often associated with mental representations. Hearing the word dog prompts you to access a mental representation that consists of things you know about that animal.
  • Mnemonists use mental representations to encode the data, like long lists of numbers, that they want to memorize. These representations turn random data into a meaningful form, allowing it to be retained in long-term memory.
  • Chess masters see a chessboard in terms of positions and opportunities for future moves, not just individual pieces on squares.
  • Musicians form a mental representation as they practice a piece. The representation includes information they will need for a performance, like what fingering to use and the locations of important passages.

As Ericsson and his co-author Robert Pool worked on Peak, they became convinced of the importance of mental representations to the development of expertise. In particular, a self-reinforcing relationship exists between deliberate practice and mental representations:

  • The process of deliberate practice helps an expert develop better mental representations for the skill they’re working on.
  • Better mental representations make it possible for an expert to practice their skill at a higher level, which leads them to build even better mental representations.

Since mental representations are so intertwined with deliberate practice, it’s important to consider the representations you’re using, and how you can improve them.

Examples from Competitive Programming

Peak is a book about a general process for building expertise, but the authors point out that mental representations “are very ‘domain specific,’ that is, they apply only to the skill for which they were developed.” Books like this one can provide general guidance, but practitioners have to find their own specific techniques.

With that in mind, here are some key areas in which students of competitive programming need to build mental representations.

Problem types

A major goal in early competitive programming training is to become familiar with common problem types. The uHunt practice site is organized to facilitate this process: It collects UVa Online Judge problems into multiple chapters, each of which is divided into multiple sections. Each section contains multiple subsections, which each contain multiple problems that students can solve to learn a problem type.

For example: I’m currently working on Chapter 3: Problem Solving Paradigms. I’m in the section on Dynamic Programming, and the subsection called Max 1D Range Sum. This subsection contains three starred problems, including UVa 787: Maximum Sub-sequence Product and UVa 10755: Garbage Heap.

One of the outcomes of solving uHunt problems is developing a mental representation of the steps required to solve each problem type. Just as a chess master who looks at a board can come up with options for moves that make their position stronger, a proficient competitive programmer should be able to read a problem like UVa 787, decide that it sounds like a dynamic programming/memoization problem, and recall the process for setting up and using a memo table.

The mental representation for a problem type is more than just an algorithm description, as one might find in a textbook. It includes everything required to get from a problem statement to a solution, including key words and phrases to look for in the problem statement, how to modify a base algorithm to accommodate problem variations, and the specifics of how to implement the solution.

As a student practices more problems, their mental representations for problem types become more sophisticated: their mental catalog of possible types becomes larger; each type can be successfully used on more problem variations; and the implementation takes a more direct route to an accepted solution.

Mathematical thinking

It’s hard to write a programming puzzle that doesn’t also test mathematical thinking skills at some level. Even a problem with no explicit math content require keeping track of array indices and other quantitative aspects of programming. Other problem statements involve a lot of math notation. And uHunt has a whole chapter dedicated to problems that test more specific math topics like number theory or probability.

Students of mathematics have their own set of mental representations that help when solving math problems. Like the representations used for programming problems, these math-oriented representations help in identifying a problem type, selecting a solution approach, and adapting a known solution for the specifics of a new problem.

One of the principles of deliberate practice is that it’s useful to isolate aspects of a skill so they can be targeted for specific practice. Given the relationship between math problems and programming problems, it makes sense to target math skills independently of programming skills. Working on math problems, such as those in a textbook, can allow you to develop mental representations that you can use when math appears in a programming problem. It’s more efficient to go after math on its own than to wait until the math you want to learn happens to show up in a programming problem.

Program logic

What distinguishes a programming problem from a math problem is the presence of program logic, like conditionals and loops. In my problem-solving process, I include the process of writing the program logic in its own step, separate from coding the solution in a programming language. In other words, the mental representations that facilitate a conceptual solution are separate from those used to implement the solution.

Language fluency

One of the benefits of solving programming problems is increased fluency in a programming language. As with learning a natural language, the process of learning a programming language can be seen as a process of building mental representations for expressing various concepts. This is where it helps to consider program logic as a separate area.

For program logic, mental representations need to focus on the abstract operations that computers are capable of. For example, they can store data in various ways, iterate over it, and compare one value with another. Having separated those representations out, the mental representations for language fluency can focus just on syntax. Once you know that you have to iterate over a set of data, you just need to remember how to express that in a particular language.

Benefits of the Mental Representation Concept

Having effective mental representations is a key part of a successful deliberate practice process. That fact can help you select targeted areas for improvement. If you’re having trouble making progress in programming practice, consider whether a better mental representation might help. For example, if you get stuck during the implementation phase, it’s possible that a better plan for your program logic is the real culprit.

(Image credit: Neil Conway)