Sharon's blog

By Sharon, history, 4 years ago,

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.

• +501

 » 4 years ago, # |   +61 happy April fool's day :D
 » 4 years ago, # |   +53 I've been getting angry emails from the government to take this down, as well as programmers thinking this is simply an April Fools joke and it does not actually work. I have proof of these tricks working, and you have to look no farther than today's contest:And some more proof .
•  » » 4 years ago, # ^ |   +47 admin please ban for cheating
 » 4 years ago, # | ← Rev. 2 →   +74 Joke's on you, clang with aggressive optimizations really does make it O(1).
 » 4 years ago, # |   -39 "We can turn every linear time algorithm into constant time by considering the maximum value of N",but how will it make a difference !!!no of iterations are although same
•  » » 4 years ago, # ^ |   -9 XD,XD,XD,XD,XD......stupid me...
 » 4 years ago, # |   +14
 » 4 years ago, # |   -22 It says #3 will shock you but there is no #3 -_-
•  » » 4 years ago, # ^ |   +27 That's the shock !
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Only 31.50\$ and you can unlock the final trick that reds don't want you to see.
 » 3 years ago, # |   0 P = NP trick :v
 » 3 years ago, # |   -26 Trick 2: Does it really work?