Good Observations:

Revision en10, by ASHWANTH_K, 2023-07-29 17:36:17

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://codeforces.net/contest/1849/problem/E].

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en25 English ASHWANTH_K 2024-05-04 08:29:27 140
en24 English ASHWANTH_K 2024-01-05 16:13:28 617
en23 English ASHWANTH_K 2023-08-15 17:31:05 73
en22 English ASHWANTH_K 2023-08-15 08:29:28 182
en21 English ASHWANTH_K 2023-08-14 19:03:22 27
en20 English ASHWANTH_K 2023-08-14 18:57:17 1047 Tiny change: '\n<hr>\n- Idea: Intuitive' -> '\n<hr>\n- **Idea:** Intuitive'
en19 English ASHWANTH_K 2023-08-04 19:56:30 129
en18 English ASHWANTH_K 2023-08-04 17:11:19 167
en17 English ASHWANTH_K 2023-08-02 19:58:33 281
en16 English ASHWANTH_K 2023-08-01 17:29:10 368
en15 English ASHWANTH_K 2023-07-30 16:40:36 163
en14 English ASHWANTH_K 2023-07-29 21:04:40 1 Tiny change: ' <hr>\n-$O(N^2)$ m' -> ' <hr>\n- $O(N^2)$ m'
en13 English ASHWANTH_K 2023-07-29 21:04:24 73
en12 English ASHWANTH_K 2023-07-29 20:47:27 1538
en11 English ASHWANTH_K 2023-07-29 17:37:06 11 Tiny change: 'problem/E].\n' -> 'problem/E] .\n'
en10 English ASHWANTH_K 2023-07-29 17:36:17 158 Tiny change: 'I will mak' -> '[problem:https://codeforces.net/contest/1849/problem/E]I will mak'
en9 English ASHWANTH_K 2023-07-28 18:58:14 189 (published)
en8 English ASHWANTH_K 2023-07-27 15:54:23 6 Tiny change: 'll work.\n- \n\n' -> 'll work.\n' (saved to drafts)
en7 English ASHWANTH_K 2023-07-27 15:53:15 266
en6 English ASHWANTH_K 2023-07-27 15:46:50 0 (published)
en5 English ASHWANTH_K 2023-07-27 15:45:03 204 (saved to drafts)
en4 English ASHWANTH_K 2023-07-27 15:41:00 0 (published)
en3 English ASHWANTH_K 2023-07-27 15:40:41 664 Tiny change: 'i.e $X = X%{m_i}$ for' -> 'i.e $X = X \% {m_i}$ for' (saved to drafts)
en2 English ASHWANTH_K 2023-07-27 15:30:41 107 Tiny change: 'ixed at a point in array ' -> 'ixed at a index in array '
en1 English ASHWANTH_K 2023-07-27 15:29:19 753 Initial revision (published)