nubir345's blog

By nubir345, history, 4 years ago, In English

The dot was not there in proposed logo. It is pretty annoying. Please look into this. MikeMirzayanov

Full text and comments »

  • Vote: I like it
  • +23
  • Vote: I do not like it

By nubir345, history, 4 years ago, In English

I lost expert, but my color is still blue.

Full text and comments »

  • Vote: I like it
  • +34
  • Vote: I do not like it

By nubir345, 4 years ago, In English

This blog is for personal use. You can check it out if you want.

As many people are checking out this blog, I thought of adding problems for some of the tricks.

Tricks

  1. Sum-Xor property: $$$ a+b = a \oplus b + 2(a\And b) $$$. Extended Version with two equations: $$$a+b=a\vert b + a\And b$$$ AND $$$a \oplus b = a\vert b - a\And b$$$ Problem 1 Problem 2
  2. Upto $$$10^{12}$$$ there can be atmost $$$300$$$ non-prime numbers between any two consecutive prime numbers.
  3. Any even number greater than $$$2$$$ can be split into two prime numbers. Problem1 Problem 2
  4. Sometimes it is better to write a brute force / linear search solution because its overall complexity can be less. Problem 1
  5. When $$$A \leq B$$$ then $$$\lfloor \frac{B-1}{A} \rfloor \leq N \leq \lceil \frac{B-1}{A} \rceil$$$ where $$$N$$$ is the number of multiples of A between any two multiples of B. Problem 1
  6. Coordinate Compression Technique when value of numbers doesn't matter. It can be done with the help of mapping shortest number to $$$1$$$, next greater to $$$2$$$ and so on. Problem 1
  7. Event method: When there is a problem in which two kinds of events are there (say $$$start$$$ and $$$end$$$ events), then you can give $$$-ve$$$ values to $$$start$$$ events and $$$+ve$$$ values to $$$end$$$ events, put them in a vector of pairs, sort them and then use as required. Problem 1 Problem 2
  8. When applying binary search on $$$doubles$$$ / $$$floats$$$ just run a loop upto 100 times instead of comparing $$$l$$$ and $$$r$$$. It will make things easier.
  9. For binary search you can also do binary lifting sort of thing, see this for more details. (I don't know how to add that code without messing up the list, that's why the link). Problem 1 Problem 2
  10. Sometimes, it is useful to visualize array into a number of blocks to move towards a solution.
  11. $$$gcd(F_n,F_m)=F_{gcd(n,m)}$$$, where $$$F_x$$$ is the $$$x_{th}$$$ fibonacci numbers and first two terms are $$$0,1$$$. Problem 1
  12. In ternary search, always keep in mind that when $$$r=l+2$$$ then $$$mid1=l$$$ and $$$mid2=r$$$ or we can say that $$$l$$$ & $$$r$$$ will remain same $$$i.e.$$$ $$$r=l+2$$$ and the condition $$$l+1$$$ will never get checked, so you have to check it explicitly. see this problem

Also, if you know any tricks / methods that you want to share and are not in the blog then you can write in the comment section, I will add them to the blog.
I will update this blog if I come across any more general methods / tricks.

Full text and comments »

  • Vote: I like it
  • +472
  • Vote: I do not like it