This is maybe the coolest trick I've ever seen. Radewoosh told me this thing a few years ago and it helped me get a few AC's since then. I strongly recommend reading and understanding it well.

also: a gif, hurray!

I have stolen set a problem from Cormen's book where you have to find a second maximum in the array: 101149M - Ex Machina. This problem is not hard and has easier solution without this trick, but the trick is appliable.

How do you simulate the shuffling of the hidden array?

Why global maxima will be always somewhere in the middle and how will maximum number of binary searchies be logn?

I was a little doubtful that this would work (due to the randomness). So I tried to simulate the checker program and the algorithm described in your blog. It works after all! I learnt a great deal today! Thanks Radewoosh!

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Random;

public class Blogwoosh {

    static int number_of_queries = 0;
    static final int QUERY_LIMIT = 103000;
    static final long MIN_VALUE = 1;
    static final long MAX_VALUE = (long) 1e18;
    static final int NUMBER_OF_HIDDEN_ELEMENTS = (int) 1e5;

    public static void intialize_hidden_array(long[] hidden_array) {
        Random rand = new Random();
        long[] buffer = rand.longs(hidden_array.length, MIN_VALUE, MAX_VALUE + 1).toArray();
        System.arraycopy(buffer, 0, hidden_array, 0, buffer.length);
        Arrays.sort(hidden_array);
    }

    public static boolean check_if_hidden_element_is_larger_or_equal(long[] hidden_array, int i, long y) {
        number_of_queries++;
        return hidden_array[i] >= y;
    }

    public static long get_hidden_value_using_shuffled_index(
            long[] hidden_arr, ArrayList<Integer> shuffled_indexes, int idx, long lower_bound, long upper_bound) {

        int index_of_hidden_array = shuffled_indexes.get(idx);

        long smallest_possible_value = lower_bound, largest_possible_value = upper_bound, guessed_value = -1;

        for (int i = 0; i < 70 && smallest_possible_value < largest_possible_value; i++) {
            guessed_value = (smallest_possible_value + largest_possible_value) >> 1;

            boolean is_hidden_element_larger_or_equal = check_if_hidden_element_is_larger_or_equal(hidden_arr, index_of_hidden_array, guessed_value);
            
            if (is_hidden_element_larger_or_equal) {
                smallest_possible_value = guessed_value;
            } else {
                largest_possible_value = guessed_value;
            }
        }
        return smallest_possible_value;
    }

    public static void main(String[] args) {

        long[] hidden_arr = new long[NUMBER_OF_HIDDEN_ELEMENTS];

        for (int number_of_tests = 0; number_of_tests < 100; number_of_tests++) {

            number_of_queries = 0;

            intialize_hidden_array(hidden_arr);

            ArrayList<Integer> shuffled_indexes = new ArrayList<>();
            for (int i = 0; i < hidden_arr.length; i++) {
                shuffled_indexes.add(i);
            }
            Collections.shuffle(shuffled_indexes);

            long prefix_max = get_hidden_value_using_shuffled_index(hidden_arr, shuffled_indexes, 0, MIN_VALUE, MAX_VALUE);
            long actual_max = hidden_arr[0];

            for (int i = 1; i < shuffled_indexes.size() && prefix_max < MAX_VALUE; i++) {
                boolean is_hidden_element_larger = check_if_hidden_element_is_larger_or_equal(hidden_arr, shuffled_indexes.get(i), prefix_max);

                if (is_hidden_element_larger) {
                    prefix_max = get_hidden_value_using_shuffled_index(hidden_arr, shuffled_indexes, i, prefix_max + 1, MAX_VALUE);
                }
                actual_max = Math.max(actual_max, hidden_arr[i]);
            }

            if(prefix_max != actual_max) {
                System.out.println("Sorry. Test Case Failed.");
                System.out.println("The computed answer is " + prefix_max);
                System.out.println("The correct answer is " + actual_max);
                return;
            } else if(number_of_queries > QUERY_LIMIT) {
                System.out.println("Sorry. Test Case Failed.");
                System.out.println("Sorry. Query limit exceeded.");
                System.out.println("The number of queries used is " + number_of_queries);
                return;
            }
            System.out.println("Test Case Passed using " + number_of_queries + " queries.");
        }
        System.out.println("All tests passed!");
    }
}

Here's the actual proof:

Consider E_n as expectation of number of changes of the maximum in every prefix.

by considering the position of the maximum we get:

using two equations above we get:

so we proved

• Read the problem
• Think for three minutes
• Come up with a solution
• Read the blog
• Find out that the solution in blog is exactly the same
• Feel great about yourself

Have been waiting for your blog, big thanks that you keep doing it!

Could someone explain how to solve the "almost a typical problem" mentioned in the editorial? I'm bad at geometry but me and kllp thought about this a lot yesterday and couldn't figure out how it can be done.

I mean this part: "Finding such point is almost a typical problem which can be solved in O(klogk) where k — number of intersections points of circles"

Thanks for the great idea!

I read about similar idea in some old Russian blog in a comment. The task is to find a minimal covering circle for a set of points, and it can be done in linear time with a help of shuffling points.

hmm, thought this trick is well known, first time meet them like 5 years ago in preparing tests for problem

and it close to another geometry feature: convex hull of random 2D points is O(logn)

You can do it in o(n) with a pivoting algorithm right? Like finding the median element.

Here's another way at looking at this trick, not sure if it actually makes mathematical sense :)

Suppose we have checked i numbers in random order and the maximum so far is m. For the next number, we would normally binary search between m and 10¹⁸. However, we know that it's quite likely that the next number is less than or equal to m — that happens with probability at least . So we need to do binary search with weights: m has weight , and the numbers between m + 1 and 10¹⁸ have weight .

The optimal way to do said binary search boils down to exactly the algorithm you describe.

It is the same as insert 1, 2, ..., n into a treap with priority are shuffled_a[1], shuffled_[2], shuffled_a[3], .., shuffled_a[n].

Is it rated?

Can anyone kindly explain how the numbers of binary search is O(logn)? Maybe I am facing difficulties getting the places where the binary searches should take place.

The blog says : " Some techniques come to mind, for example we could do all binary searches at the same time, ask for each element if it's greater than , or something, then forget about lower values... but no, things like that would aim only at really weak, random test cases. More, it seems that they wouldn't work on a first random max-test. "

Techniques like " taking a [d/2] and checking each ai if ai >= d/2 and continue filtering elements, till you have one element and do binary search to get its value " works only on weak, random test cases, can someone provide a corner case where this method fails I feel this technique may work

That`s a very good trick, thanks!

Really cool! It works for yesterday's F

https://codeforces.net/contest/1101/problem/F

Edit: ok it's now in the editorial https://codeforces.net/blog/entry/64483

Thanks for this blog and it makes me came up with a strange idea:) It means that the length of increasing subsequence that include the maximum number is O(log n) in average.And I have been known that the LIS of a permutation is O(sqrt(n)).Then I want to know that how many permutations that one of the LIS's ending is number i? For example,for n=3,there is 1 permutation for number 1 (3 2 1),and 2 permutations for number 2 (1 3 2 and 3 1 2), and 5 permutations for number 3 (exclude 3 1 2).

This useful technique also appears in this paper: "Geometric Applications of a Randomized Optimization Technique".

In case someone is having a hard time understanding the time complexities of randomised algorithms/data structures, there's a pretty cool paper called 'Randomized Reduction', by Brian Dean, which uses the 'randomized reduction lemma' to explain their time complexities in a simple and intuitive fashion.

This problem was featured 4 years later in BAPC ($$$n \leq 10,000$$$, same $$$a_i$$$ range, 12000 queries). You can solve it here: https://www.acmicpc.net/problem/26001