Introduction

After receiving many messages asking how to solve problems, I've decided to create a blog post about it! Of course, as I am a CM (which has low edit distance to LGM), I am obviously very good at problemsolving.

Rephrasing the Problem

One of the most powerful strategies in problem solving is rephrasing the problem. Usually, when people talk about this, they often say things like "try to view the problem as a graph problem" or "rephrase as a geometry problem (yuck!)" However, to become a Legendary Candidate Master like me, you need to multiply these pieces of advice together and divide by their greatest common divisor to realize that it's not enough to simply rephrase the problem -- you need to rephrase problem solving itself.

Let's view problem solving as a graph, where one node represents the problem and another node represents the solution. In between, there are several edges (observations, algorithms, interesting data structures, bitset) which allow you to reach other nodes representing states containing ideas that you have.

Now, a naive competitive programmer would likely employ one of the follow three strategies:

• BFS from the source node and try to make as many observations / try as many algorithms as possible.

• DFS from the source node and tunnel towards the solution, backtracking if things fail.

• BFS until you've made sufficient observations and have a good idea of the general solution, then DFS to figure out the details.

A Better Strategy

However, these elementary techniques hold back the potential of competitors, because the number of nodes you visit can become quite large. Luckily, Legendary Grandmaster + 2 time IOI winner + CEO of competitive programming githubs Benq has shared his technique to his unparalleled success!

For some context, let's take a look at this problem. We're given a graph, generated randomly, and asked queries to compute the distance between two nodes. If we think back to the graph analogy, we observe that generally authors do not create problems with this analogy in mind; therefore, the graphs created are more or less generated randomly.

Looking at the editorial, running a BFS from both nodes visits $$$\sqrt{N}$$$ nodes on average, much less than running a BFS from the source! If we apply a similar technique to problem solving and start solving from both the solution and the problem statement, we can visit far less nodes, therefore drastically speeding up how long it takes to get AC!

Conclusion

Before LGMs lobby to get this post taken down (because their secrets have been revealed!), make sure to upvote this post. Of course, the average rating of users will massively increase after this, and competitive programming will cease to exist as it will be extremely difficult to write problems hard enough to challenge competitors.

Well, it was nice while it lasted.