Every Technique and Algorithm I Used to Become Grandmaster

Правка en13, от Noble_Mushtak, 2023-01-30 08:29:30

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

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en13 Английский Noble_Mushtak 2023-01-30 08:29:30 731 Tiny change: 's\n- Fast fourier tra' -> 's\n- Fast Fourier tra' (published)
en12 Английский Noble_Mushtak 2023-01-30 08:14:01 1453
en11 Английский Noble_Mushtak 2023-01-30 08:06:03 3071
en10 Английский Noble_Mushtak 2023-01-30 07:39:04 828
en9 Английский Noble_Mushtak 2023-01-30 07:28:17 2247
en8 Английский Noble_Mushtak 2023-01-30 06:58:02 627
en7 Английский Noble_Mushtak 2023-01-30 06:47:44 447
en6 Английский Noble_Mushtak 2023-01-30 06:43:04 495 Tiny change: ' [Problem B](https://' -> ' [Problem C](https://'
en5 Английский Noble_Mushtak 2023-01-30 06:28:19 797
en4 Английский Noble_Mushtak 2023-01-30 06:20:07 554
en3 Английский Noble_Mushtak 2023-01-30 06:10:43 3013 Tiny change: 'Div. 2):\n- [Probl' -> 'Div. 2):\n\n- [Probl'
en2 Английский Noble_Mushtak 2023-01-30 05:26:48 8
en1 Английский Noble_Mushtak 2023-01-30 05:26:35 976 Initial revision (saved to drafts)