Grandmasters HATE this one weird trick!!! Top ten tips to speed up your program (NUMBER THREE WILL SHOCK YOU!!)

Revision en1, by Sharon, 2018-04-01 05:57:36

It is currently 12:00AM, March 32nd. I was digging through the deep web and I found out about a couple tricks that legendary grandmasters have been using on this website for ages, though it was kept secret from the rest of humanity. These tricks are too dangerous for dangerous people to know (Kim Jong Un if you are reading this please stop). However, I am personally sick of the inequality and I think it is time to let the world know the secrets to make your programs run super fast.

Trick 1: The O(N) to O(1) trick.

Consider this problem. The bounds are clearly too large for an O(N) solution (looping from L to R). However, what if I told you that you could easily modify your O(N) code to make it O(1)?

Consider this piece of code:

long sum = 0;
for(long i = 0; i < N; i++){
sum += i;
}


We can clearly see that for large N, such as 10^18, the program will take a long time to run. BUT!!! We can turn every linear time algorithm into constant time by considering the maximum value of N (which is always given by problemsetters in the description in Codeforces). Here is the SAME code, but in constant time.

long sum = 0;
for(long i = 0; i < 1000000000000000000L; i++){
sum += i;
}


Now with your new knowledge, you can solve the problem above.

Trick 2: Thread.Sleep, a trick for the Java folks that are sick and tired of C++'s supremacy.

Now, you are reading this trick and thinking I am crazy. Sharon, how is it possible? Do you even know how to program? Thread.Sleep() slows your program down... It literally stops the program for the amount of time that you specify.

Now, I don't blame you for getting confused. I was too, originally. Until I found out you can manipulate the laws of the universe using this function to make your program run faster, like magic!

Here is what I mean. Have you ever considered passing a negative integer as an argument to that method? I bet you have not. What do you think it does? Well, we can follow simple logical reasoning. When we plug in a positive integer, the program stops for that amount of time. Therefore, when we plug in a negative number, the program should stop for a negative amount of time. In order to do that, it must start earlier, therefore faster, so the whole program runs faster!

Here is an example program:

import java.util.*;

public class R468A {

public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int a = scan.nextInt();
int b = scan.nextInt();
if(a > b){
int temp = b;
b = a;
a = temp;
}
long ans = 0;
long t1 = 0;
long t2 = 0;

while(a < b){
//System.out.println(a+" "+b);
t1++;
a++;
ans += t1;
if(a == b) break;
b--;
t2++;
ans += t2;
}
System.out.println(ans);
}
}



When you run this program, you will see that it terminates nearly instantly. This is the true power of the Thread.Sleep trick.

Anyway, I hope you enjoy my tutorial and that it will provide you with many AC solutions and high rating. I will be on the lookout for more weird tricks and I will make sure to share them as I find any.

History

Revisions

Rev. Lang. By When Δ Comment
en1 Sharon 2018-04-01 05:57:36 3548 Initial revision (published)