We can think of what separates a _better_ competitive programmer from the rest as — (, among other things) one, having the ability to see a pattern and place it in a container of similar problems done before that all used a similar idea. Harder problems make it difficult to determine which container to place it in, if at all any! ↵
This can be abstracted away, as instead of accessing the main memory for ideas every time, they store certain ideas in a cache. The better you become, the closer your cache gets to your CPU and the larger the repository of ideas inside it, ↵
↵
In an effort to become a good CPer myself, I decided to jot down some ideas along the lines of **if I see $x$, think of $y$** that I observed doing problems. Hopefully they help other people in the community as well.↵
↵
1. Whenever you want to calculate / optimise a function of type $f(GCD(x, n))$.↵
↵
In an effort to become a good CPer myself, I decided to jot down some ideas along the lines of **``if I see $x$, think of $y$''** that I observed doing problems. Hopefully, they help other people in the community as well.↵
↵
1) Whenever you want to calculate or optimise a function of type $f(GCD(x, n))$, _where x can vary_, instead of iterating over x, iterate over the divisors of n. <br>↵
This goes hand in hand with a fact about the number of divisors of $n$ being approximately $O(n^{1/3})$.↵
↵
This might seem obvious now, or when you already see a straight representation of this form. However, remembering this would still have a benefit in the sense that when you don't have your answer in the form $f(GCD(x, n))$, this could force you to try and convert it into that form, which you know to be solvable in the given time constraints. <br>↵
Problems related to 1. — [1744E2](https://mirror.codeforces.com/problemset/problem/1744/E2)↵
↵
2) Whenever you come across querying a subtree of a node in a tree, think in terms of **entry and exit times** that you get from a DFS (just as you would to do a toposort). This is probably more well known. <br>↵
Example: [1899G](https://mirror.codeforces.com/problemset/problem/1899/G)↵
↵
3) **Line Sweep Algorithm for intervals on a number line:** When presented with a number of intervals over a number line, you can iterate through segments by sorting (l, 0) and (r, 1) pairs if you want to prefer opening brackets before closing ones. Now count the number of brackets that enclose a point by keeping track of the number of open segments at each moment. ↵
↵
4) **Re-rooting Tree-DP**: Say you are given a tree. You want to find a value $f(root, tree)$ where root can be all possible nodes in the tree (e.g., the max of a value $f(node, tree)$ over all possible nodes, that can be thought of as roots). This could be done via DP over trees, where you re-root the tree in each dp iteration. Since this has been explained before a number of times, I will just link an article that I personally liked which goes in detail about it — [:)](https://usaco.guide/gold/all-roots?lang=cpp). ↵
↵
This could be further generalised as finding some particular operation on a tree for $x$ nodes, and you can find it in the given time complexity for $x-1$ nodes if you fix one node as the root, then you iterate over that fixed root via re-rooting.↵
↵
5) Problems related to finding the maximum distance of a node from a given node in a tree — always recall **Theorem:** Let $v_1v_2$ be the diameter of a tree. Then the furthest node from $v$ is always either $v_1$ or $v_2$. ↵
The diameter can be found in $O(n)$ via standard techniques. <br>↵
Example problem — [1881F](https://mirror.codeforces.com/contest/1881/problem/F) ↵
↵
↵
Feel free to add to the list of examples mentioned here. I am open to suggestions since this would be my very first blog. I might continue on expanding this list with more ideas.
This can be abstracted away, as instead of accessing the main memory for ideas every time, they store certain ideas in a cache. The better you become, the closer your cache gets to your CPU and the larger the repository of ideas inside it
↵
In an effort to become a good CPer myself, I decided to jot down some ideas along the lines of **if I see $x$, think of $y$** that I observed doing problems. Hopefully they help other people in the community as well.↵
↵
1. Whenever you want to calculate / optimise a function of type $f(GCD(x, n))$
↵
In an effort to become a good CPer myself, I decided to jot down some ideas along the lines of **``if I see $x$, think of $y$''** that I observed doing problems. Hopefully, they help other people in the community as well.↵
↵
1) Whenever you want to calculate or optimise a function of type $f(GCD(x, n))$, _where x can vary_, instead of iterating over x, iterate over the divisors of n. <br>↵
This goes hand in hand with a fact about the number of divisors of $n$ being approximately $O(n^{1/3})$.↵
↵
This might seem obvious now, or when you already see a straight representation of this form. However, remembering this would still have a benefit in the sense that when you don't have your answer in the form $f(GCD(x, n))$, this could force you to try and convert it into that form, which you know to be solvable in the given time constraints. <br>↵
Problems related to 1. — [1744E2](https://mirror.codeforces.com/problemset/problem/1744/E2)↵
↵
2) Whenever you come across querying a subtree of a node in a tree, think in terms of **entry and exit times** that you get from a DFS (just as you would to do a toposort). This is probably more well known. <br>↵
Example: [1899G](https://mirror.codeforces.com/problemset/problem/1899/G)↵
↵
3) **Line Sweep Algorithm for intervals on a number line:** When presented with a number of intervals over a number line, you can iterate through segments by sorting (l, 0) and (r, 1) pairs if you want to prefer opening brackets before closing ones. Now count the number of brackets that enclose a point by keeping track of the number of open segments at each moment. ↵
↵
4) **Re-rooting Tree-DP**: Say you are given a tree. You want to find a value $f(root, tree)$ where root can be all possible nodes in the tree (e.g., the max of a value $f(node, tree)$ over all possible nodes, that can be thought of as roots). This could be done via DP over trees, where you re-root the tree in each dp iteration. Since this has been explained before a number of times, I will just link an article that I personally liked which goes in detail about it — [:)](https://usaco.guide/gold/all-roots?lang=cpp). ↵
↵
This could be further generalised as finding some particular operation on a tree for $x$ nodes, and you can find it in the given time complexity for $x-1$ nodes if you fix one node as the root, then you iterate over that fixed root via re-rooting.↵
↵
5) Problems related to finding the maximum distance of a node from a given node in a tree — always recall **Theorem:** Let $v_1v_2$ be the diameter of a tree. Then the furthest node from $v$ is always either $v_1$ or $v_2$. ↵
The diameter can be found in $O(n)$ via standard techniques. <br>↵
Example problem — [1881F](https://mirror.codeforces.com/contest/1881/problem/F) ↵
↵
↵
Feel free to add to the list of examples mentioned here. I am open to suggestions since this would be my very first blog. I might continue on expanding this list with more ideas.
