Блог пользователя caohash

Автор caohash, 4 года назад, По-английски

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!

Spoiler

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.

  • Проголосовать: нравится
  • +122
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

stefdasca i need you to write this but for day trading

»
4 года назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

Actually, you can BFS even faster! Maintain all nodes in BITSET, and transition with bitwise operations thus requiring only sqrt(n)/64 time to solve the problem. An LGM told me this trick and now I am sharing with you all at the threat of losing my friendship.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    Genius! Thanks for sharing. Actually, I think you can actually maintain the bitset using a bitset, and get $$$\frac{\sqrt{n}}{4096}$$$ operations.

»
4 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

caoash caohash

Which one is the main?

»
4 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

thanks for the advice! i'll take it into mind while practicing

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    hi tpabestboy, can you explain how you practiced to go from low spec to high expert in less than a week?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +17 Проголосовать: не нравится

      How about at least try to think before asking unrelated questions?

      Just looking at the contests tab for 5 seconds, it seems very likely their true skill is much higher than rating suggests, probably at least 2000, and that round #662 was just a fail.

      And probably this improvement took a longer time than "less than a week".

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +20 Проголосовать: не нравится

        How about at least try to think before giving unrelated answers?

        Just looking at the contests tab for 5 seconds, it seems very likely my true skill is much lower than my rating suggests, probably at most 1300, and that round #663 was just very lucky.

        And this "improvement" took a week.