Noble_Mushtak's blog

Every Technique and Algorithm I Used to Become Grandmaster
By Noble_Mushtak, history, 23 months ago, In English

Hi everyone, I became grandmaster today so I decided to go down memory lane and review every problem I have ever done in a CodeForces contest to look back and see every technique and algorithm I had to use to become a grandmaster. I am not sure how useful this is, I mostly think it's fun to look at all the old solutions I wrote and how different it was from how I write code now. The main takeaway is that, as many people have said before, you don't need to know or memorize a bunch of advanced algorithms to become grandmaster. As you will see, there are many problems where I just used "ad hoc reasoning," meaning there's not a standard technique I used to solve the problem and you just need to make some clever mathematical observations to solve the problem. Also, there are many popular algorithms that I have never needed in a CodeForces contest despite being a grandmaster:

  • Sparse tables, Fenwick trees, and segment trees
  • String algos, like rolling hashes, Knuth-Morris-Pratt, suffix arrays, and Aho-Corasick
  • Shortest path algos, like Dijkstra's algorithm, Bellman-Ford, and Floyd-Warshall
  • Flow algos, like Edmonds-Karp, Dinic's, and push-relabel
  • Convex hull trick
  • Fast Fourier transform and number theoretic transform

This isn't to say that learning algorithms is bad—I love reading cp-algorithms.com and learning new algorithms—and I have used many of these algorithms in other contests, like CodeChef, ICPC, and Google Code Jam, but practicing consistently and getting better at ad hoc reasoning and your general problem-solving abilities matter much more.

CodeForces Round #362 (Div. 2): Rating went from 1500 to 1504 (back then, default rating was 1500 instead of 0)

Codeforces Round #363 (Div. 2): Rating went from 1504 to 1536 (+36)

  • Problem A: Brute force
  • Problem B: Brute force
  • Problem C: Ad hoc reasoning and basic bitmasks (there is a dynamic programming solution, but that's not how I solved it)

Codeforces Round #553 (Div. 2): Rating went from 1540 to 1566 (+26)

Codeforces Round #570 (Div. 3): Rating went from 1566 to 1732 (+166)

Educational CodeForces Round 68: Rating went from 1732 to 1766 (+44)

CodeForces Global Round 4: Rating went from 1776 to 1807 (+31)

Educational Codeforces Round 74: Rating went from 1807 to 1920 (+113)

Codeforces Round #600 (Div. 2): Rating went from 1920 to 1877 (-43)

  • Problem A: Ad hoc reasoning and math
  • Problem C: Sorting, prefix sums, and dynamic programming
  • Problem D: Depth-first search and connected components

Codeforces Round #601 (Div. 2): Rating went from 1877 to 2005 (+128)

Codeforces Global Round 14: Rating went from 2005 to 1877 (-128)

Deltix Round, Spring 2021: Rating went from 1877 to 1975 (+98)

CodeForces LATOKEN Round 1: Rating went from 1975 to 1974 (-1)

Codeforces Round #729 (Div. 2): Rating went from 1974 to 2132 (+158)

Hello 2022: Rating went from 2132 to 2085 (-47)

Codeforces Round #765 (Div. 2): Rating went from 2085 to 2092 (+7)

Educational Codeforces Round 122: Rating went from 2092 to 2168 (+76)

Codeforces Round #808 (Div. 1): Rating went from 2168 to 2138 (-30)

Codeforces Global Round 23: Rating went from 2138 to 2239 (+101)

Codeforces Global Round 24: Rating went from 2239 to 2291 (+52)

  • Problem A: Ad hoc reasoning and math
  • Problem B: Ad hoc reasoning with number theory
  • Problem C: Prefix sums and maps
  • Problem D: Modular arithmetic, extended Euclidean algorithm, and combinatorics
  • Problem E: Greedy, sorting, and binary search tree sets

Good Bye 2022: 2023 is NEAR: Rating went from 2291 to 2358 (+67)

  • Problem A: Greedy and binary search tree sets
  • Problem B: Ad hoc reasoning with permutations
  • Problem C: Ad hoc reasoning with number theory (I did use Miller-Rabin, but only to generate the primes <100, which could have been hardcoded instead)
  • Problem D: Disjoint set union, and I also used DFS trees for the intuition behind this solution
  • Problem E: Tree DP and extended Euclidean algorithm

Hello 2023: Rating went from 2358 to 2331 (-27)

TypeDB Forces 2023: Rating went from 2331 to 2416 (+85)

  • Problem A: Ad hoc reasoning and math
  • Problem B: Miller-Rabin, Pollard's rho algorithm, and number theory
  • Problem C: Dynamic programming
  • Problem D: Tarjan's SCC algorithm and DP over directed acylic graphs
  • Problem E: Greedy and bitwise operations
  • Problem F: Binary exponentiation, extended Euclidean algorithm, and cycle decomposition
  • Vote: I like it
  • +213
  • Vote: I do not like it

Comments Comments (19)
| Write comment?
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Noble_Mushtak (previous revision, new revision, compare).

→ Reply
»
23 months ago, # |
  Vote: I like it +1 Vote: I do not like it

So most of time it was about reasoning,adhoc,greedy and some data structures, medium dp , until you reached candidate master?

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Yeah to reach candidate master, it was mostly ad hoc reasoning, brute force, greedy, dynamic programming, basic data structures from the C++ STL, math (including combinatorics, like nCr and nPr), and modular arithmetic (including binary exponentiation). I think bitmasks, depth-first search, breadth-first search, disjoint set union, and connected components in undirected graphs can also be helpful for reaching candidate master, but I ended up not needing these techniques until after I had reached candidate master.

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      so if i cant reach cm just by these techniques what should i do, will practise be enough for me, my maths is bad, and my iq is low i believe

      → Reply
»
23 months ago, # |
  Vote: I like it +1 Vote: I do not like it

In earlier rounds, Div.2 D used to be a lot easier.

→ Reply
»
23 months ago, # |
  Vote: I like it +214 Vote: I do not like it

This is an interesting blog post but let's not ignore that you have a small sample of div1 rounds. You should know segment trees, hashes, and shortest paths — those do appear in CF low-div1.

→ Reply
»
23 months ago, # |
  Vote: I like it +17 Vote: I do not like it

Problem B: Miller-Rabin, Pollard's rho algorithm

whaaaaat?

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Ironic considering his initial takeaway 😂

    → Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah my solution is definitely overcomplicated, but Miller-Rabin and Pollard's rho algorithm are needed for the factorization algorithm from kactl. A simpler $$$O(\sqrt{n})$$$ factorization algorithm was fast enough, but the kactl factorization algorithm is part of my competitive programming templates so I just pasted this factorization algorithm into my solution instead.

    → Reply
»
23 months ago, # |
  Vote: I like it +22 Vote: I do not like it

thanks i wanted to post the same list "how i became a master" but forgot

→ Reply
»
23 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Btw you overkilled last contest's D, you can solve it with something like a topological sorting algorithm and nothing more.

→ Reply
»
23 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Nice blog and congrats on GM. You made a valid point, most of the time you don't need any advanced algorithms to do good, you just need programming skills (to know how to use what you know) which can be obtained only through practice.

I find it funny how there are many people under cyan who want to know some advanced algorithms and data structures. And that is fine, but they need to realize that if such thing were to show up on non educational round, it will require also some hard observations and not just the algorithm/data structure itself.

→ Reply
  • »
    »
    23 months ago, # ^ |
    ← Rev. 2   Vote: I like it +13 Vote: I do not like it

    sometimes you must step to the big mountain to stop feel small rocks under your feet...

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Sometimes you get lost and can't move forward

      → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      sometimes you must feel small rocks under your feet to step to the big mountain...

      → Reply
»
23 months ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

ْDo you mean by your words that this field depends only on intelligence and talent?

→ Reply
  • »
    »
    23 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    As a very average and unintelligent person who is slightly versed in the field, it depends on time and enjoyment :), not talent or intelligence

    → Reply
  • »
    »
    23 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    No definitely not, talent can help you get to red faster and there are many talented people who make red very quickly in a few years, but for me, this has been an almost seven-year long journey so I am definitely below-average in terms of talent compared to other grandmasters. I think the most important thing in competitive programming is to practice effectively and learn from your mistakes, there is a much better blog by Um_nik explaining how to practice competitive programming effectively.

    → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to improve ad-hoc reasoning? I am sorry to necropost but I really need to ask this!

→ Reply