Attention World Finalists:

...

...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!!!!!!!!