I will make an account of good observations and ideas I come across while solving problems. 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 that $L = L'$ or $L' >= 2*L$. ↵
- We want to find two numbers in an array $A[]$ with maximum common prefix bits in binary representation. Its easy to show that those two numbers always occur as adjacent numbers in $sorted(A[])$ ↵
- The number of distinct gcd prefixed/suffixed at an index in an array will never exceed $log(A_{max})$ ↵
- 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$. ↵
- If $N$ times $abs()$ function appears at any problem, maybe bruteforcing all $2^N$ combinations of $+/-$ may give way to the solution sometimes.↵
- Prefix Or/And can take a maximum of $log(N)$ values.↵
- 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).↵
- 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$↵
- Partial optimisation of SOS dp leading to $3^N$ complexity may pass for $N <=15$.↵
- 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. ↵
- Any counting problem, like counting pairs of elements/counting subarrays satisfying some property: If any of the common techniques, like fixing the L pointer or 2pointer approach, does not work, try to do divide and conquer. It may be easy to come up with a solution sometimes.[problem:https://mirror.codeforces.com/contest/1849/problem/E].↵
↵
- 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 that $L = L'$ or $L' >= 2*L$. ↵
- We want to find two numbers in an array $A[]$ with maximum common prefix bits in binary representation. Its easy to show that those two numbers always occur as adjacent numbers in $sorted(A[])$ ↵
- The number of distinct gcd prefixed/suffixed at an index in an array will never exceed $log(A_{max})$ ↵
- 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$. ↵
- If $N$ times $abs()$ function appears at any problem, maybe bruteforcing all $2^N$ combinations of $+/-$ may give way to the solution sometimes.↵
- Prefix Or/And can take a maximum of $log(N)$ values.↵
- 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).↵
- 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$↵
- Partial optimisation of SOS dp leading to $3^N$ complexity may pass for $N <=15$.↵
- 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. ↵
- Any counting problem, like counting pairs of elements/counting subarrays satisfying some property: If any of the common techniques, like fixing the L pointer or 2pointer approach, does not work, try to do divide and conquer. It may be easy to come up with a solution sometimes.
