Tricks

If you know the proof of #3, please tell me.

Trick 7 is my personal favourite

nice

This trick is quite well known probably but still maybe it is useful for beginners:
Ways of initializing a global array :

memset(a,0,sizeof(a)) ; // initialize with 0
memset(a,-1,sizeof(a)); // initializing with -1
memset(a,0xc0,sizeof(a)); // initializing with negative infinity
memset(a,0x3f,sizeof(a)); // initializing with positive infinity

For $$$7$$$, you can also do this: for start values, store $$$2*start$$$, and for end values, store $$$2*end+1$$$. If it's even, it will be a start value, else an end value. And start values will always come before end values.

I think 6 is coordinate compression

It would be great if everybody could share a few of the peculiar tricks they know

Can you provide links of some problems related to every tricks. It will be very helpful.

For trick 1, you can use it on this problem.

A different trick is that for queries, you can sometimes split it into 2 types of queries (when query is greater than sqrt(n) and less than sqrt(n)) so instead of using O(n) time you use O(sqrt(n)). You can use it in these problems 1 2.

Be careful using unordered_map , it can give TLE or your solution may get hacked , see the blogpost by neal about this link also unordered_map doesn't let you use complex data type like pair<int,int>,int . to make it work see the blog by arpa about it link

Time to add the blog to favorite and read it after eternity.

Any problems related to 7?

Can we make this blog like every coder shares their one trick which is not mentioned in the post. It will be a great learning experience for all of us

LOL stop treating cp as a game of remembering tricks...

For trick #8, I usually loop up to 200 times just to be safe. :P

can you explain 5 one, i mean what is the operator being used?

Oh, man!! Point-8 is the best I was getting TLE for some weird reason but this trick got me accepted.

Hey bro @nubir345 can u please give the question according to the trick just below each trick , would be very easy for others , the questions given below in comments .

When I started with CP, I struggled with Binary search a lot. Nowadays I use these rules-of-thumb for BS.
Say we are doing BS on some variable x. And There is some function bool check(int x) which is monotonic.
And check returns $$$[False, False, ..., False, True, ..., True]$$$ for different values of x and 0 <= x <= 1e9

bool check(int x){

}

int low = 0, high = 1e9; //Here check(low) should be False and check(high) should be True
while(high-low>1){
    int mid = (l+r)/2;
    if(check(mid))high = mid;
    else low = mid;
}
// Now `high` will be the first value of x which check(x) is True

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'm sure there have been tutorials etc about this trick but since people are talking about binary search, I want to add this. I like to use iterative binary search that looks like this:

int ans = 0;
for (int k = 1 << MAX_LG; k != 0; k /= 2) {
  if (!has_some_property(ans + k)) {
    ans += k;
  }
}

This assumes 0 doesn't have "some property". In the end, ans will be the largest integer that doesn't have "some property".

Using this, I have been able to avoid guessing about one-off errors for 6 years already. It is short to write, intuitive and generalizes well to floats and bigints. I'm not sure exactly what your "trick 8" accomplishes, but I suspect iterative binary search also makes that unnecessary.

How to get the inversion of just one number?

long long get_inv(long long x)
{
	if (x <= 1) return 1;
	return (p - p / x) * get_inv(p % x) % p;
}

For trick 1, you can add this great problem.

Given a strictly increasing array $$$a_1 < a_2 < a_3 < .... < a_n$$$
Do this transformation $$$a_i := a_i - i$$$
Then the array becomes non- decreasing $$$a_1 <= a_2 <= a_3 <= .... <= a_n$$$
Fairly simple trick but quite useful sometimes :)

Guys I'm not getting the point 8. Can anyone help me with that?

please keep updating this blog it is very helpful

for $$$2$$$ and $$$3$$$, every number up to $$${10}^{12}$$$ accepts a goldbach decomposition with one of the numbers less than or equal to $$${10}^6$$$ (I'm not sure if the upper limit is $$${10}^5$$$).

Problems for 9)
1354D - Multiset
1404C - Fixed Point Removal

The second problem in #3 is not related to the Goldbach conjecture.

They use that every even positive integer is a difference of two primes.

If you have any implication between these two conjectures, it would be a big breakthrough in number theory. See e.g. this paper.

Can anyone help me with problem 1 of point 1 — Xor sum on Atcoder. I failed to solve it but could not find any English editorial for the problem. I found a recursive formula online

However, the explanation is in Chinese and GG translate only makes things messier.

lcm(a, gcd(b, c)) = gcd(lcm(a, b), lcm(a, c)) -- (1)
gcd(a, lcm(b, c)) = lcm(gcd(a, b), gcd(a, c)) -- (2)

https://codeforces.me/contest/1350/problem/C

Wow, this blog is quite useful for me. Upvoted :)

$$$F[gcd(x,y)]=gcd(F[x],F[y])$$$

$$$F$$$ is the Fibonacci sequence that $$$F(0)=0$$$, $$$F(1)=1$$$, $$$F(n)=F(n-1)+F(n-2)$$$ for $$$n \ge 2 $$$

You can also add one more property.

gcd ( x , y ) = gcd ( x-y , y );

This results in, gcd ( x , y , z , w ,.....) = gcd ( x-y , y , z , w,....)

Also,

for any a, b, if b > a, a%b = a. Additionally, if a ≥ b > [a/2] , a%b = a - b.

For Trick # 2 you can add this Problem

Using point 2 can we state that for checking if n is prime we just need to check if n is not divisible by any number from 2 to 300 rather than sqrt(n) if n<=1e12?

Here I got one trick , If n>1, then there is always at least one odd prime number x satisfying n < x < 2n

You can check this problem 1178D - Prime Graph

This has been very helpful, thank you so much!

Another recent problem that can be solved using trick 1: 1556D - Take a Guess