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.
