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!!!!!!!!
Auto comment: topic has been updated by Sharon (previous revision, new revision, compare).
As Asian, I have full access to the content :) I can sell this content to you guys if you want.
Apparently if you combine those nested logs with bitsets you can create code so fast it will finish execution before it is written. This is especially useful for problems you can't solve where there exists a version of you in the future that has already solved it.
Be careful of using too many logs, as deforestation causes global warming.
There's a simple trick to compensate for this. What you do is start start a forest fire every time you get a TLE that could have been avoided by using more logs. With proper tweaking of the size of the forest fire you will start if you TLE you can make it that your expected contribution to global warming will remain the same regardless of the number of logs you use.
I wouldn't recommend to do this because of the risk to damage the temporal-spatial continuum.
My memes can't be arrested.
Mastercard wants to know your location.
What if my logs are stacked like this?
That would just be 2log(n) time.
Avoid doing this.
Correct, it is better to nest your logs like .