I will account for good observations and ideas while solving problems in codeforces/CodeChef/atcoder . The proofs of the below statements will not be mentioned here; It's advised to do such proofs on your own for exercise. ↵
↵
- Lets say I have a set $S$ consisting of integers, denote its $lcm(S) = L$, I add a new element $x$ to this set $S$ , ↵
Lets deonte the new set as $S'$,where $S' = union(S , x)$ and its $lcm(S') = L'$. Can we deduce a relation between $L$ and $L'$? We can observe $L = L'$ or $L' >= 2*L$. ↵
<hr>↵
- We want to find two numbers in an array $A[]$ with maximum common prefix bits in binary representation. It's easy to show that those two numbers always occur as adjacent numbers in $sorted(A[])$ ↵
<hr>↵
- The number of distinct gcd prefixed/suffixed at an index in an array will never exceed $log(A_{max})$ ↵
<hr>↵
- Let's say I have a number $X$, And I apply modulo operation as many times as I wish, i.e $X = X \% {m_i}$ for some different values of ${m_i}$. It can be shown that $X$ takes $log(X)$ distinct values until it reaches to $0$. ↵
<hr>↵
- If $N$ times $abs()$ function appears at any problem, maybe bruteforcing all $2^N$ combinations of $+/-$ may give way to the solution sometimes.↵
<hr>↵
- Prefix Bitwise Or/And can take a maximum of $log(N)$ values.↵
<hr>↵
- Nested totient function say $phi(phi(phi( ... (X) ... )))$ will eventually reach 1 in atmost $2log(X)$ nested functions. Useful for computing expressions like $(A^{(B^{(C^..)})})$ modulo $P$. (nested powers).↵
<hr>↵
- SOS dp may help to compute the number of $i$ such that $A[i]$ is a subset/superset/no bits common to a given mask $X$↵
<hr>↵
- Partial optimisation of SOS dp leading to $3^N$ complexity may pass for $N <=15$.↵
<hr>↵
- Whenever You want to maximize/minimize bitwise properties among some elements, consider iterating from the last bit and checking its possibility. This greedy assigning from the last bit will work. ↵
<hr>↵
- Any counting problem, like counting pairs of elements/counting subarrays satisfying some property: If any common technique, like fixing the L pointer or 2pointer approach, does not work, try to divide and conquer. It may be easy to come up with a solution sometimes. https://mirror.codeforces.com/contest/1849/problem/E↵
<hr>↵
- The contribution Technique impresses me every time. Try this: https://atcoder.jp/contests/abc312/tasks/abc312_g. Hint: number of ways of choosing three nodes in the same tree path can be converted to summating all path lengths in the tree. ↵
<hr>↵
- General Technique: For counting problems: try to fix some parameters and iterate on it. It may happen that fixing just one parameter may be difficult sometimes to count properly. So try to do casework and identify which cases can be easily calculated by fixing different parameters. Eg, let's say my problem can be divided into 2 cases, $case1$ and $case2$. It can happen that fixing parameter $A$ can be easy to count distinct answers for $case1$, and fixing another parameter $B$ can be easy to count distinct answers for $case2$. Try this: https://mirror.codeforces.com/contest/50/problem/E Hint: case1: rational, case2: irrational roots. ↵
<hr>↵
- It's not wrong to complicate ur solution with a lazy segtree. Try this: https://mirror.codeforces.com/contest/1553/problem/F↵
<hr>↵
- Lets take an array $A$ and let $f(x)$ be number of subsequence with $Xor(subseq) = x$. It can be shown that $f(x)$ is always a power of 2. Strong result: f(x) = 0 or f(x) = f(x1) = f(x2) ...!= 0. More insights on this can be understood well by studying the xor basis technique. ↵
<hr>↵
-$O(N^2)$ may give tle, but $O(N^2/64)$ will pass. clue: BITSETS ↵
<hr>↵
↵
- Lets say I have a set $S$ consisting of integers, denote its $lcm(S) = L$, I add a new element $x$ to this set $S$ , ↵
Lets deonte the new set as $S'$,where $S' = union(S , x)$ and its $lcm(S') = L'$. Can we deduce a relation between $L$ and $L'$? We can observe $L = L'$ or $L' >= 2*L$. ↵
<hr>↵
- We want to find two numbers in an array $A[]$ with maximum common prefix bits in binary representation. It's easy to show that those two numbers always occur as adjacent numbers in $sorted(A[])$ ↵
<hr>↵
- The number of distinct gcd prefixed/suffixed at an index in an array will never exceed $log(A_{max})$ ↵
<hr>↵
- Let's say I have a number $X$, And I apply modulo operation as many times as I wish, i.e $X = X \% {m_i}$ for some different values of ${m_i}$. It can be shown that $X$ takes $log(X)$ distinct values until it reaches to $0$. ↵
<hr>↵
- If $N$ times $abs()$ function appears at any problem, maybe bruteforcing all $2^N$ combinations of $+/-$ may give way to the solution sometimes.↵
<hr>↵
- Prefix Bitwise Or/And can take a maximum of $log(N)$ values.↵
<hr>↵
- Nested totient function say $phi(phi(phi( ... (X) ... )))$ will eventually reach 1 in atmost $2log(X)$ nested functions. Useful for computing expressions like $(A^{(B^{(C^..)})})$ modulo $P$. (nested powers).↵
<hr>↵
- SOS dp may help to compute the number of $i$ such that $A[i]$ is a subset/superset/no bits common to a given mask $X$↵
<hr>↵
- Partial optimisation of SOS dp leading to $3^N$ complexity may pass for $N <=15$.↵
<hr>↵
- Whenever You want to maximize/minimize bitwise properties among some elements, consider iterating from the last bit and checking its possibility. This greedy assigning from the last bit will work. ↵
<hr>↵
- Any counting problem, like counting pairs of elements/counting subarrays satisfying some property: If any common technique, like fixing the L pointer or 2pointer approach, does not work, try to divide and conquer. It may be easy to come up with a solution sometimes. https://mirror.codeforces.com/contest/1849/problem/E↵
<hr>↵
- The contribution Technique impresses me every time. Try this: https://atcoder.jp/contests/abc312/tasks/abc312_g. Hint: number of ways of choosing three nodes in the same tree path can be converted to summating all path lengths in the tree. ↵
<hr>↵
- General Technique: For counting problems: try to fix some parameters and iterate on it. It may happen that fixing just one parameter may be difficult sometimes to count properly. So try to do casework and identify which cases can be easily calculated by fixing different parameters. Eg, let's say my problem can be divided into 2 cases, $case1$ and $case2$. It can happen that fixing parameter $A$ can be easy to count distinct answers for $case1$, and fixing another parameter $B$ can be easy to count distinct answers for $case2$. Try this: https://mirror.codeforces.com/contest/50/problem/E Hint: case1: rational, case2: irrational roots. ↵
<hr>↵
- It's not wrong to complicate ur solution with a lazy segtree. Try this: https://mirror.codeforces.com/contest/1553/problem/F↵
<hr>↵
- Lets take an array $A$ and let $f(x)$ be number of subsequence with $Xor(subseq) = x$. It can be shown that $f(x)$ is always a power of 2. Strong result: f(x) = 0 or f(x) = f(x1) = f(x2) ...!= 0. More insights on this can be understood well by studying the xor basis technique. ↵
<hr>↵
-$O(N^2)$ may give tle, but $O(N^2/64)$ will pass. clue: BITSETS ↵
<hr>↵
