Good Observations:

Revision en8, by ASHWANTH_K, 2023-07-27 15:54:23

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.

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.me/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)