Chapter 0 — Introduction

The purpose of this guide is to help you significantly boost your competitive programming (CP) performance by enhancing the efficiency of how you think, practice, and implement solutions. I’ve decided to share these insights anonymously through a friend’s account (definitely not an alt, no need to ban me). My actual CP rating is approximately 2100.

During my CP journey, I didn't just grind through countless problems—I actively studied the deeper patterns behind CP and formulated strategies to accelerate my progress. This guide is a synthesis of those insights, some of which I haven’t seen discussed elsewhere.

This blog post was created in part due to the Month of Blog Posts initiative, which offers a financial reward for the best blogs during the month.

It will be divided into three chapters. For now, only the first one is being released, with the others coming soon.

Chapter 1 — Optimizing the Thinking Process

Why Is Something There?

Problem-solving can be taught; it involves following a specific way of thinking, a particular chain of reasoning—a method of querying your brain to arrive at truths and solutions.

People often learn what works better by trial and error, simply by solving hundreds of problems and discovering which types of mental queries are effective.

Alternatively, I can just tell you.

What Does It Mean to Solve a Problem?

Definitions can vary, but in CP, solving a problem means finding a program and then implementing it in code.

But not just any program—we need a program that satisfies specific properties.

Defining Problems

Given our understanding of what it means to solve a problem, it's clear that we need to somehow store the problem definition in our brain to expect any results.

A problem definition must enable us to determine which programs are correct or incorrect.

While we might rely on our brain to parse the problem statement during the first read, the question is: Can we do better?

The answer is YES. This topic has also been touched on by Um_nik in this blog post.

It's beneficial to ensure the definition is good. Here are a few things to focus on:

Ambiguity

Definitions are often ambiguous, and our brains don't automatically enforce precision.

However, when solving CP problems, precise definitions are exactly what we need.

Bad: In a social network, identify the influencers who can spread a message to the entire community in the shortest time possible.

Good: Given a directed graph where nodes represent users and edges indicate that a user can directly send a message to another user, determine the smallest set of users from which a message can reach all other users in the fewest number of steps. Each step allows users who received the message to forward it to their direct connections.

Simplicity

Our brains have a limited capacity for context. Working with a definition that's five paragraphs long, is challenging.

Most of the time, the problem can be expressed in just a few sentences.

Bad:

Good: Given a graph with nodes representing castles and weighted edges representing open tunnels, find the shortest path between two specified nodes.

Query Potential

Consider this: any term used in our problem definition has associated techniques and lemmas.

Using consistent terms—for example, calling a "shuffle" a "permutation," or referring to a "city with roads" as an "undirected graph"—increases the likelihood of retrieving relevant information.

There are many ways to enhance query potential. Sometimes it depends on what our brains are good at, such as visualizing information in two dimensions.

Essentially, it's about taking different perspectives within the problem. You want a good "perspective" or simply a good problem definition you can work with.

Bad: You're given a 'magic list' of numbers. You need to find the 'twinkle point,' which is calculated by finding the largest possible total when adding up numbers in the list without picking any two numbers that are next to each other.

Good: Given an array of integers, find the maximum sum of non-adjacent elements.

Some Ways to Define a Problem

Naive Programs with a Time Complexity Target

Some problems have a slower, naive version that solves them.

These naive solutions already have good query potential because they are programs, as opposed to, say, mathematical constraints.

We can verify our program's correctness by checking its time complexity and functional equivalence to the naive program.

Mathematical Constraints

This is a more general approach that applies to all problems.

We can mathematically express the properties that our program's output must have relative to its inputs.

Verifying correctness involves checking whether the program's output satisfies these properties and whether it meets the time complexity requirements.

Lemmas

Many problems are simply about parsing the statement and translating it into code.

However, to solve a problem, one often must make a set of observations—or more formally, lemmas.

Just as we properly encode definitions, we can encode lemmas. The same focus points apply here.

Formal mathematics already provides an excellent encoding. We should use that. Knowing how to verbally express observations as descriptions of mathematical conjectures is important.

Structures and Functions

Sometimes, a part of our solution will require a certain data structure or function with specific properties. Once we construct them, they should be encoded in our memory so we can retrieve them later.

I usually encode them in C++ since I'm accustomed to visualizing C++ code. Obviously, you don't remember every single line—just having a rough idea is enough.

Search Progress

It's important to keep track of what we've already explored and from which perspectives, so we can strategically decide what to try next without repeating ourselves.

Mental Model—Putting It All Together

To find the program, we need to keep a few things compressed in our memory. By categorizing them, we can not only remember more but also improve in individual aspects later.

The simple mental model is as follows:

• The problem definition
• The set of relevant lemmas discovered
• The set of relevant structures and functions created or available
• Search progress

Utilizing This Mental Model

We don't have to store everything solely within our active memory. It can help to write it down. However, it's good practice to do it purely in the mind.

Fundamentally, our main problem definition is about constructing the main function. That's the program we need to find. To do so, we might need to find other programs (functions / structures). In this sense, it can be used recursively.

Intentions

The mental model is what we encode in our brain—it's how we store our progress toward finding a program.

Intentions are more fundamental; they are what our brain is built to follow. They are usually set subconsciously and cannot always be expressed verbally.

Our mental model provides a structured way to set intentions to find the program faster. Because of it, these intentions will then be categorized in a way that allows us to identify hurdles and consequently train much more efficiently.

Organize your intentions and be aware of them. Be able to express verbally what you are currently trying to do. Examples: "looking for a better problem definition", "looking for necessary lemmas", "checking whether I can apply DP", "strategically deciding on next intention".

The history of our intentions should form a tree. At the root should be the intention to solve the problem in the least amount of time. While utilizing our encoding scheme, we create sub-intentions (children nodes) based on the avenues we want to explore.

Search

How to Perform the Search

Suppose we have now defined the problem and are relatively satisfied with that part, yet we don't immediately see the solution. What now?

For any construction (program or proof), there are two fundamental ways to search:

Forward

• You have discovered a few lemmas, and now you try some techniques that might utilize them.

• You directly construct new things from what you have

• "The problem definition can be expressed as a functional equivalence to a recursive function with a small enough input space, let's try DP"

Backward

• You start from the goal.

• For instance, you consider a technique that might solve the problem but requires certain lemmas to be true, so you verify them.

• "I see that this problem is looking for an O(N^2) solution. Furthermore, it seems to behave like a knapsack. Let's try DP, and we have to check whether we can define it with a recursive function with a small enough input space"

• "I need to answer range queries quickly. One way to do that is segment tree. For that, I need to merge the result for contiguous ranges efficiently and in an associative way. Let's try to see whether I can do that."

Backward reasoning can help us save time by not focusing on irrelevant lemmas.

Forward reasoning can help us save time by not exploring techniques that fundamentally won't be possible to construct.

Generally, I first start with forward reasoning. Discover the most obvious lemmas by going through examples and definitions.

Once it becomes harder to make discoveries, it may be beneficial to limit the search space by guessing techniques, a.k.a. utilizing backward reasoning.

Remember to keep track of your progress and current intentions.

Knowing where and how to search comes with experience.

Miscellaneous

Learn Math Fundamentals

As you've seen, many aspects such as problem definitions and lemmas rely on having at least a basic understanding of math. By "basic," I don't mean formulas learned in high school.

Rather, I refer to the fundamental philosophy upon which math is built. Math allows us to arrive precisely at truths based on a few axioms. Understanding concepts like implications, equivalences, quantifiers, etc., is not just useful in CP but in life in general.

Avoid Unnecessary Emotions

Fundamentally, the main thing to focus on is making the right decisions. You shouldn't require yourself to be angry or sad to solve a problem.

Feelings of helplessness are also hardwired by evolution. If we can't solve a problem, we tend to give up and enter a mode where we expect others to help.

This doesn't mean you shouldn't feel bad when something you thought would work doesn't, or feel good when it does. Those are simply feedback mechanisms.

However, feeling bad shouldn't spiral into emotional circuits where we somehow solve the problem differently. The approach should remain the same—the one we consider most optimal.

Chapter 2 — Improvement from Experience

UNLOCKS AFTER 100 UPVOTES

Chapter 3 — Optimizing Implementation Process

UNLOCKS AFTER 200 UPVOTES

Other

I've also created a Discord community. The aim is to systematically get better by collaboratively discovering optimal approaches to CP, and perhaps even venture into other worthwhile areas. If you would like to join this collective effort, I'd love to have you on board.