DISCLAIMER: DO NOT READ THIS POST IF YOU ARE IN PORTUGAL FOR WORLD FINALS OR LIVE IN THE EUROPEAN UNION
Attention World Finalists:
As you may know, Article 13 has been voted on by the European Union and all memes are now illegal. It is imperative that when you travel to Portugal you must LEAVE YOUR MEMES AT HOME, or they will be deleted at airport security and you will be arrested.
The contents of this post must be viewed at your own risk.
...
...It is March 32, 2, and I'm back with more expert algorithm analysis that the legendary grandmasters don't want you to see. I have to take extra discretion with this one, since the government of an entire continent decided to ban my means of passing information.
Ladies and gentlemen, I present to you:
The Log Trick 2
If you've been keeping up, you know that O(1) code isn't actually any good at all because O(1) = O(N), so the best algorithms possible are logarithmic. Unless you use Java, and then you have the Thread.Sleep trick which is brilliant but not everybody here is intelligent and uses Java so we must come up with something for the rest of you C++ plebians.
In order to understand this next segment we must use some math.
We have to prove log(log(n)) < log(n)
Take the equation:
log(log(n)) < log(n) <- divide both sides by log (log(n)) < (n) <- true
Let's check the graph and make sure we didn't make any mathematical errors:
See how when there are more logs, there are less operations?
Q.E.D, or as they say in Portugal: "Take that, b*tch!"
So how to we apply this in code?
Let's write a simple, classical binary search:
// Returns index of x if it is present in arr[],
// else return -1
int binarySearch(int arr[], int x)
{
int l = 0, r = arr.length - 1;
while (l <= r)
{
int m = l + (r-l)/2; //THIS LINE IS THE MOST IMPORTANT!!!!!! NOTICE DIVISION BY 2
// Check if x is present at mid
if (arr[m] == x)
return m;
// If x greater, ignore left half
if (arr[m] < x)
l = m + 1;
// If x is smaller, ignore right half
else
r = m - 1;
}
// if we reach here, then element was
// not present
return -1;
}
Now let's improve it:
// Returns index of x if it is present in arr[],
// else return -1
int binarySearch(int arr[], int x)
{
int l = 0, r = arr.length - 1;
while (l <= r)
{
int l = 0, r = arr.length - 1;
while (l <= r)
{
int l = 0, r = arr.length - 1;
while (l <= r)
{
int l = 0, r = arr.length - 1;
while (l <= r)
{
int l = 0, r = arr.length - 1;
while (l <= r)
{
int l = 0, r = arr.length - 1;
while (l <= r)
{
int m = l + (r-l)/2;
// Check if x is present at mid
if (arr[m] == x)
return m;
// If x greater, ignore left half
if (arr[m] < x)
l = m + 1;
// If x is smaller, ignore right half
else
r = m - 1;
}
int m = l + (r-l)/2;
// Check if x is present at mid
if (arr[m] == x)
return m;
// If x greater, ignore left half
if (arr[m] < x)
l = m + 1;
// If x is smaller, ignore right half
else
r = m - 1;
}
int m = l + (r-l)/2;
// Check if x is present at mid
if (arr[m] == x)
return m;
// If x greater, ignore left half
if (arr[m] < x)
l = m + 1;
// If x is smaller, ignore right half
else
r = m - 1;
}
int m = l + (r-l)/2;
// Check if x is present at mid
if (arr[m] == x)
return m;
// If x greater, ignore left half
if (arr[m] < x)
l = m + 1;
// If x is smaller, ignore right half
else
r = m - 1;
}
int m = l + (r-l)/2;
// Check if x is present at mid
if (arr[m] == x)
return m;
// If x greater, ignore left half
if (arr[m] < x)
l = m + 1;
// If x is smaller, ignore right half
else
r = m - 1;
}
int m = l + (r-l)/2;
// Check if x is present at mid
if (arr[m] == x)
return m;
// If x greater, ignore left half
if (arr[m] < x)
l = m + 1;
// If x is smaller, ignore right half
else
r = m - 1;
}
// if we reach here, then element was
// not present
return -1;
}
We can see that the runtime is log(log(log(log(log(log(log(log(log(log(n))))))))))))))))))))))))))))), much better than what we had before. This even works in Python, making it a viable language for World Finals for the first time in history.
By the way, you need to use this trick in order to solve the interactive problem C in World Finals this year. Don't worry, any world finalists who viewed this will be arrested anyway.
If you are excited world finals and want to get a sneak peak at the problems ahead of time, click here!!!!!!!!
