Every Technique and Algorithm I Used to Become Grandmaster
Разница между en12 и en13, 731 символ(ов) изменены
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. There :↵

- Sp
arsalso 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.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](https://cp-algorithms.com/) and learning new algorithms—
but for the purpose of getting better at competitive programming, at least on CodeForces,and I have used many of these algorithms in other contests, like CodeChef, ICPC, and Google Code Jam, but practicing consistently and getting better and better att ad hoc reasoning and your general problem-solving abilities matters much more.↵

[CodeForces Round #362 (Div. 2)](https://mirror.codeforces.com/contest/697): Rating went from 1500 to 1504 (back then, default rating was 1500 instead of 0)↵

- [Problem A](https://mirror.codeforces.com/contest/697/submission/19115278): Ad hoc reasoning and math↵
- [Problem B](https://mirror.codeforces.com/contest/697/submission/19123476): Basic string manipulation↵

[Codeforces Round #363 (Div. 2)](https://mirror.codeforces.com/contest/699): Rating went from 1504 to 1536 (+36)↵

- [Problem A](https://mirror.codeforces.com/contest/699/submission/19235692): Brute force↵
- [Problem B](https://mirror.codeforces.com/contest/699/submission/19243705): Brute force↵
- [Problem C](https://mirror.codeforces.com/contest/699/submission/19246509): 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)](https://mirror.codeforces.com/contest/1151): Rating went from 1540 to 1566 (+26)↵

- [Problem A](https://mirror.codeforces.com/contest/1151/submission/52961256): Brute force↵
- [Problem B](https://mirror.codeforces.com/contest/1151/submission/52964803): Brute force and bitwise operations↵
- [Problem C](https://mirror.codeforces.com/contest/1151/submission/52974813): Ad hoc reasoning and math↵

[Codeforces Round #570 (Div. 3)](https://mirror.codeforces.com/contest/1183): Rating went from 1566 to 1732 (+166)↵

- [Problem A](https://mirror.codeforces.com/contest/1183/submission/56080739): Basic number theory↵
- [Problem B](https://mirror.codeforces.com/contest/1183/submission/56084184): Ad hoc reasoning and math↵
- [Problem C](https://mirror.codeforces.com/contest/1183/submission/56088132): Ad hoc reasoning and math↵
- [Problem D](https://mirror.codeforces.com/contest/1183/submission/56094565): Greedy and priority queue↵
- [Problem E](https://mirror.codeforces.com/contest/1183/submission/56103177): Ad hoc reasoning with strings (there is a BFS solution, but that's not how I solved it)↵
- [Problem H](https://mirror.codeforces.com/contest/1183/submission/56114287): Dynamic programming (I used the [count unique subsequences of a given length](https://www.geeksforgeeks.org/count-unique-subsequences-of-length-k/) algorithm)↵

[Educational CodeForces Round 68](https://mirror.codeforces.com/contest/1194): Rating went from 1732 to 1766 (+44)↵

- [Problem A](https://mirror.codeforces.com/contest/1194/submission/57023277): Ad hoc reasoning and math↵
- [Problem B](https://mirror.codeforces.com/contest/1194/submission/57028169): Brute force and row/column sums↵
- [Problem C](https://mirror.codeforces.com/contest/1194/submission/57031239): Ad hoc reasoning with strings and subsequences↵
- [Problem D](https://mirror.codeforces.com/contest/1194/submission/57046656): Game theory↵

[CodeForces Global Round 4](https://mirror.codeforces.com/contest/1178): Rating went from 1776 to 1807 (+31)↵

- [Problem A](https://mirror.codeforces.com/contest/1178/submission/57390984): Greedy↵
- [Problem B](https://mirror.codeforces.com/contest/1178/submission/57395166): Dynamic programming↵
- [Problem C](https://mirror.codeforces.com/contest/1178/submission/57396863): Binary exponentiation↵
- [Problem D](https://mirror.codeforces.com/contest/1178/submission/57406587): Ad hoc reasoning with graphs↵
- [Problem E](https://mirror.codeforces.com/contest/1178/submission/57416933): Deques↵

[Educational Codeforces Round 74](https://mirror.codeforces.com/contest/1238): Rating went from 1807 to 1920 (+113)↵

- [Problem A](https://mirror.codeforces.com/contest/1238/submission/62121449): Ad hoc reasoning and math↵
- [Problem B](https://mirror.codeforces.com/contest/1238/submission/62126202): Greedy and sorting↵
- [Problem C](https://mirror.codeforces.com/contest/1238/submission/62131801): Greedy↵
- [Problem D](https://mirror.codeforces.com/contest/1238/submission/62136926): Ad hoc reasoning and combinatorics↵

[Codeforces Round #600 (Div. 2)](https://mirror.codeforces.com/contest/1253): Rating went from 1920 to 1877 (-43)↵

- [Problem A](https://mirror.codeforces.com/contest/1253/submission/65170209): Ad hoc reasoning and math↵
- [Problem C](https://mirror.codeforces.com/contest/1253/submission/65182125): Sorting, prefix sums, and dynamic programming↵
- [Problem D](https://mirror.codeforces.com/contest/1253/submission/65193697): Depth-first search and connected components↵

[Codeforces Round #601 (Div. 2)](https://mirror.codeforces.com/contest/1255): Rating went from 1877 to 2005 (+128)↵

- [Problem A](https://mirror.codeforces.com/contest/1255/submission/65354001): Ad hoc reasoning and math↵
- [Problem B](https://mirror.codeforces.com/contest/1255/submission/65359301): Ad hoc reasoning with graphs and sorting↵
- [Problem C](https://mirror.codeforces.com/contest/1255/submission/65366944): Ad hoc reasoning with graphs and permutations↵
- [Problem D](https://mirror.codeforces.com/contest/1255/submission/65380985): Ad hoc reasoning with grids↵
- [Problem E1](https://mirror.codeforces.com/contest/1255/submission/65372961): Greedy↵

[Codeforces Global Round 14](https://mirror.codeforces.com/contest/1515): Rating went from 2005 to 1877 (-128)↵

- [Problem A](https://mirror.codeforces.com/contest/1515/submission/114872082): Ad hoc reasoning with sorting↵
- [Problem B](https://mirror.codeforces.com/contest/1515/submission/114888749): Ad hoc reasoning with number theory↵
- [Problem C](https://mirror.codeforces.com/contest/1515/submission/114915969): Greedy and priority queue↵

[Deltix Round, Spring 2021](https://mirror.codeforces.com/contest/1523): Rating went from 1877 to 1975 (+98)↵

- [Problem A](https://mirror.codeforces.com/contest/1523/submission/117877005): Ad hoc reasoning with simulations↵
- [Problem B](https://mirror.codeforces.com/contest/1523/submission/117881041): Ad hoc reasoning and math↵
- [Problem C](https://mirror.codeforces.com/contest/1523/submission/117887018): Stacks↵

[CodeForces LATOKEN Round 1](https://mirror.codeforces.com/contest/1534): Rating went from 1975 to 1974 (-1)↵

- [Problem A](https://mirror.codeforces.com/contest/1534/submission/119341166): Ad hoc reasoning with grids↵
- [Problem B](https://mirror.codeforces.com/contest/1534/submission/119348809): Ad hoc reasoning and math↵
- [Problem C](https://mirror.codeforces.com/contest/1534/submission/119352421): Cycle decomposition and binary exponentiation↵
- [Problem D](https://mirror.codeforces.com/contest/1534/submission/119378018): Ad hoc reasoning with trees↵

[Codeforces Round #729 (Div. 2)](https://mirror.codeforces.com/contest/1542): Rating went from 1974 to 2132 (+158)↵

- [Problem A](https://mirror.codeforces.com/contest/1542/submission/121190744): Ad hoc reasoning and math↵
- [Problem B](https://mirror.codeforces.com/contest/1542/submission/121209270): Ad hoc reasoning with number theory↵
- [Problem C](https://mirror.codeforces.com/contest/1542/submission/121214087): Ad hoc reasoning with number theory↵
- [Problem D](https://mirror.codeforces.com/contest/1542/submission/121224898): Binary exponentiation and dynamic programming↵
- [Problem E1](https://mirror.codeforces.com/contest/1542/submission/121241049): Dynamic programming and combinatorics (I used the [count permutations with given number of inversions algorithm](https://www.geeksforgeeks.org/number-of-permutation-with-k-inversions/), the numbers of permutations with a given number of inversions are also known as [Mahonian numbers](https://oeis.org/A008302))↵

[Hello 2022](https://mirror.codeforces.com/contest/1621): Rating went from 2132 to 2085 (-47)↵

- [Problem A](https://mirror.codeforces.com/contest/1621/submission/141497471): Ad hoc reasoning with grids↵
- [Problem B](https://mirror.codeforces.com/contest/1621/submission/141512066): Greedy↵
- [Problem C](https://mirror.codeforces.com/contest/1621/submission/141520974): Cycle decomposition↵

[Codeforces Round #765 (Div. 2)](https://mirror.codeforces.com/contest/1625): Rating went from 2085 to 2092 (+7)↵

- [Problem A](https://mirror.codeforces.com/contest/1625/submission/142469830): Greedy and bitwise operations↵
- [Problem B](https://mirror.codeforces.com/contest/1625/submission/142471463): Ad hoc reasoning and maps↵
- [Problem C](https://mirror.codeforces.com/contest/1625/submission/142480739): Dynamic programming↵

[Educational Codeforces Round 122](https://mirror.codeforces.com/contest/1633): Rating went from 2092 to 2168 (+76)↵

- [Problem A](https://mirror.codeforces.com/contest/1633/submission/144657965): Ad hoc reasoning with number theory↵
- [Problem B](https://mirror.codeforces.com/contest/1633/submission/144665541): Greedy↵
- [Problem C](https://mirror.codeforces.com/contest/1633/submission/144680927): Brute force↵
- [Problem D](https://mirror.codeforces.com/contest/1633/submission/144709590): Dynamic programming↵
- [Problem E](https://mirror.codeforces.com/contest/1633/submission/144752537): Kruskal's algorithm and binary search tree maps↵

[Codeforces Round #808 (Div. 1)](https://mirror.codeforces.com/contest/1707): Rating went from 2168 to 2138 (-30)↵

- [Problem A](https://mirror.codeforces.com/contest/1707/submission/164467742): Greedy↵
- [Problem B](https://mirror.codeforces.com/contest/1707/submission/164523052): Ad hoc reasoning with simulations↵

[Codeforces Global Round 23](https://mirror.codeforces.com/contest/1746): Rating went from 2138 to 2239 (+101)↵

- [Problem A](https://mirror.codeforces.com/contest/1746/submission/176313408): Ad hoc reasoning and math↵
- [Problem B](https://mirror.codeforces.com/contest/1746/submission/176319980): Greedy with stacks↵
- [Problem C](https://mirror.codeforces.com/contest/1746/submission/176326357): Ad hoc reasoning with permutations↵
- [Problem D](https://mirror.codeforces.com/contest/1746/submission/176343908): Tree DP↵
- [Problem E](https://mirror.codeforces.com/contest/1746/submission/176374424): Ad hoc reasoning, with inspiration from binary search↵

[Codeforces Global Round 24](https://mirror.codeforces.com/contest/1764): Rating went from 2239 to 2291 (+52)↵

- [Problem A](https://mirror.codeforces.com/contest/1764/submission/182654788): Ad hoc reasoning and math↵
- [Problem B](https://mirror.codeforces.com/contest/1764/submission/182656701): Ad hoc reasoning with number theory↵
- [Problem C](https://mirror.codeforces.com/contest/1764/submission/182661581): Prefix sums and maps↵
- [Problem D](https://mirror.codeforces.com/contest/1764/submission/182676791): Modular arithmetic, extended Euclidean algorithm, and combinatorics↵
- [Problem E](https://mirror.codeforces.com/contest/1764/submission/182691516): Greedy, sorting, and binary search tree sets↵

[Good Bye 2022: 2023 is NEAR](https://mirror.codeforces.com/contest/1770): Rating went from 2291 to 2358 (+67)↵

- [Problem A](https://mirror.codeforces.com/contest/1770/submission/187253125): Greedy and binary search tree sets↵
- [Problem B](https://mirror.codeforces.com/contest/1770/submission/187259308): Ad hoc reasoning with permutations↵
- [Problem C](https://mirror.codeforces.com/contest/1770/submission/187281845): 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](https://mirror.codeforces.com/contest/1770/submission/187324448): Disjoint set union, and I also used [DFS trees](https://mirror.codeforces.com/blog/entry/68138) for the intuition behind this solution↵
- [Problem E](https://mirror.codeforces.com/contest/1770/submission/187360343): Tree DP and extended Euclidean algorithm↵

[Hello 2023](https://mirror.codeforces.com/contest/1779): Rating went from 2358 to 2331 (-27)↵

- [Problem A](https://mirror.codeforces.com/contest/1779/submission/187729970): Ad hoc reasoning with simulations↵
- [Problem B](https://mirror.codeforces.com/contest/1779/submission/187741487): Ad hoc reasoning and math↵
- [Problem D](https://mirror.codeforces.com/contest/1779/submission/187781253): [IntervalContainer](https://github.com/kth-competitive-programming/kactl/blob/main/content/various/IntervalContainer.h) and maps↵
- [Problem E](https://mirror.codeforces.com/contest/1779/problem/E): Sorting and ad hoc reasoning with graphs and strongly connected components↵

[TypeDB Forces 2023](https://mirror.codeforces.com/contest/1787): Rating went from 2331 to 2416 (+85)↵

- [Problem A](https://mirror.codeforces.com/contest/1787/submission/191106010): Ad hoc reasoning and math↵
- [Problem B](https://mirror.codeforces.com/contest/1787/submission/191112116): Miller-Rabin, Pollard's rho algorithm, and number theory↵
- [Problem C](https://mirror.codeforces.com/contest/1787/submission/191122836): Dynamic programming↵
- [Problem D](https://mirror.codeforces.com/contest/1787/submission/191135044): Tarjan's SCC algorithm and DP over directed acylic graphs↵
- [Problem E](https://mirror.codeforces.com/contest/1787/submission/191156753): Greedy and bitwise operations↵
- [Problem F](https://mirror.codeforces.com/contest/1787/submission/191149639): 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)