By Radewoosh, history, 4 years ago,

Hello, codeforces!

Sorry for the long break, but the last weeks of holidays and the first weeks of academic year took my attention. I hope today's trick will make you forgive me. :P

I invented this trick a few years ago, but for sure I wasn't first, and some of you already know it. Let's consider the following interactive task. There are n (1 ≤ n ≤ 105) hidden integers ai, each of them from range [1, 1018]. You are allowed to ask at most 103000 queries. In one query you can choose two integers x and y (1 ≤ x ≤ n, 1 ≤ y ≤ 1018) and ask a question ''Is ax ≥ y?'' The task is to find the value of the greatest element in the hidden array. The checker isn't adaptive.

Unfortunately, this task is only theoretical, and you cannot solve it anywhere, but it'll turn out, that solution can be handy in many other, much more complicated problems.

Even beginners should be able to quickly come up with a solution which asks n·log(d) queries (where d = 1018). Unfortunately, this is definitely too much. The mentioned solution, of course, does n independent binary searches, to find each ai.

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.

The limit on the number of queries slightly higher than the limit on n should give us a hint: for many elements of the array, we should ask about them only once (of course we have to ask about each of them at least once). So, maybe let's develop a solution which at least has a chance to do it. Here comes an idea: let's iterate over numbers in the hidden array like in the n·log(d) solution, but before doing the binary search, ask if ai that we are looking at right now is strictly greater than the greatest value that we've already seen. It is isn't, there is no point in doing the binary search here — we are only interested in greatest value.

Of course, this solution can do the binary search even n times, for example when the hidden array is increasing. Here comes a key idea: let's consider numbers in random order! It would definitely decrease the number of binary searches that we would do, but how much? Let's consider the following example (and assume that numbers are already shuffled):

##### 10, 14, 12, 64, 20, 62, 59, 39, 57, 96, 37, 91, 88, 5, 76

A filled circle means that we do the binary search, an empty circle means that we skip this number.

Of course, we should do the binary search when the prefix maximum changes (increases, in particular, it can't decrease). How many times will it happen on average? Let's focus on the global maximum. It's clear that for sure we have to do the binary search to find its exact value and that we won't do binary search anymore to its right. What with elements to its left? The situation turns out to be analogical. Where will be the global maximum in a shuffled array? Somewhere in the middle, won't it? So, we'll do the last binary search in the middle (on average), one before last in the middle of the left (on average again) half and so on. Now, it's easy to see that we'll do the binary search only O(log(n)) times! A total number of queries will be equal to n + O(log(nlog(d)), which seems to be enough. It also can be proven or checked with DP/Monte Carlo, that probability that the number of binary searches will be high is very low.

OK, nice task, randomized solution, but how could it be useful in other problems? Here's a good example: 442E - Gena and Second Distance. Editorial describes the solution, so I'll mention only the essence. We want to maximize some result, and we have n ''sources'' that we can take the result from. In each of them we do the binary search to find the highest possible result from this source, and then we print the maximum of them. Looks familiar? The most eye-catching difference is that in this task we have to deal with real numbers.

Experience tells me that this trick is in most cases useful in geometry. It also reminds me how I discovered this trick: when I was solving a geometry problem in high school and trying to squeeze it in the time limit. I decided to check if current ''source'' will improve my current result and if not — to skip the binary search. It gave me many more points (it was an IOI-like problem) even without shuffling sources. Why? Test cases were weak. :D

So, did another blog about randomization satisfy your hunger? If you know more problems which could be solved with this trick, share them in the comments. See you next time! :D

• +1075

 » 4 years ago, # | ← Rev. 2 →   +159 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!
 » 4 years ago, # |   +28 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.
•  » » 4 years ago, # ^ |   +2 And what's the solution?
•  » » » 4 years ago, # ^ |   +22 SpoilerFind the first maximum using single elimination bracket. Second maximum is one of elements which has lost to the first maximum.
•  » » 4 years ago, # ^ |   0 Hey dalex! I just solved the problem "normally" (the intended solution i guess) and it got AC in 46ms. I tried shuffling the indices just to try and it got AC in 62ms. I'm guessing that's not the point of the trick, right? How would you apply the trick on this problem? Thanks!
•  » » » 4 years ago, # ^ |   +4 Normal solution is in my spoiler above.And the solution with trick is: SpoilerShuffle numbers, go through them, maintaining two maximums. Compare each number with second maximum first — most likely it will be less than second maximum, so no need to compare it with first maximum.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 Aaah got it, i was thinking the whole time i was going to do 2*N queries, but i forgot the whole point of the trick, the random shuffle, lol. It got AC in the same time as the original solution, but it's easier to code and you can clearly see why it works.Cool example, thanks dalex!
 » 4 years ago, # |   +6 How do you simulate the shuffling of the hidden array?
•  » » 4 years ago, # ^ |   +8 I think by randomly choosing the position of the array where you do each query
•  » » 4 years ago, # ^ |   +31 vector indices{0, 1, 2, ..., n-1}; random_shuffle(indices.begin(), indices.end());
•  » » » 3 years ago, # ^ |   0 Is this hackable in the same way as some other randonized algorithms only with srand(0)?
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +5 Use std::mt19937.  std::random_device rd; std::mt19937 g(rd()); std::shuffle(v.begin(), v.end(), g); 
•  » » » » » 3 years ago, # ^ |   0 Thank you!
 » 4 years ago, # | ← Rev. 2 →   +1 Why global maxima will be always somewhere in the middle and how will maximum number of binary searchies be logn?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +5 Not always. But the expected value of its position will be in the middle.
•  » » 4 years ago, # ^ |   0 Here is some good intuition to why the element is probably in the middle: For every position, compute the average distance to all other positions, the element that is “closer” to all others is the middle
 » 4 years ago, # | ← Rev. 4 →   +1 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! Proof of concept (in Java)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 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 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!"); } } 
 » 4 years ago, # | ← Rev. 5 →   +60 Here's the actual proof:Consider En 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
•  » » 4 years ago, # ^ | ← Rev. 2 →   +28 Okay, that's expected value, but more interesting thing is distribution. Like, what's the probability of taking k·En instead of En? Markov's inequality suggests it's at most , but maybe there is some better estimate?
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +16 Well, just an idea: assume that the sequence is a permutation. If you take Xk as the random variable indicating whether we have a prefix maximum at the k-th position, then , and X1, X2, ..., Xn are all independent. A way to see it: if you have a permutation on k - 1 numbers, you can create k permutations on k numbers by picking the last element and taking the remaining numbers to preserve their relative order. The k-th element is the largest in exactly one of them.Having that, you could probably try to approach with some Chernoff bounds (hopefully I didn't do anything fundamentally wrong here):I'll assume for simplicity that , the real result won't be far off. We have , and therefore . Now, for any δ > 0 and t > 0, Chernoff gives us , minimized at , which gives us . For instance, for δ = 4, we have .For our bounds, we can afford . When we plug in n = 105, δ = 4.34, we arrive at . And it's probably way lower than that.Edit: turns out I'm not that far off. A simple dp shows that .
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +52 I was anticipated.We are going to study the distribution. Some math is involved, come prepared.Given a random permutation , let Xi be the random variable that has value 1 if σ(i) > σ(j) for any j < i and 0 otherwise. Our goal is to study the distribution of X1 + ... + Xn. The first remark is that the random variables Xi are independent. This can be proven noticing that Xi depends only on the set of values in {σ(1), ..., σ(i - 1)} and on the value of σ(i). But this two information are independent from Xj for any j < i.Furthermore, it is very easy to compute and .Having shown that the variables Xi are independent and having computed their expected value and variance, we can apply Bernstein Inequality on the random variables . Exploiting that , if we plug in t = (λ - 1)Hn with λ > 1, Bernstein inequality tells us that is much stronger than the bound that you were suggesting. For example, if n is sufficiently large (like n ≥ 100), the above inequality implies Let me add that it is very natural to apply Bernstein inequality when trying to bound the tail distribution of a sum of independent random variables. In some sense, Bernstein inequality is the correct version of Markov inequality. Indeed Markov inequality is extremely far from being optimal in almost any situation where the variables are independent, whereas Bernstein gives an almost sharp estimate quite often. The proof of Bernstein inequality is more involved than the one of Markov inequality but still elementary. If you want to learn it, take a look into A gentle introduction to concentration inequalities, specifically Section 4.
•  » » » 4 years ago, # ^ |   0 Although I have absolutely no idea how to work this out... since the maximum element is in a random position with equal distribution, then the expected value and the distribution in total are exactly equal to the depth of quicksort.I trust quicksort, So I don't prove :).
•  » » 3 years ago, # ^ |   0 How did you get rid of $E_n$ in the third equation?
 » 4 years ago, # |   +145 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!
•  » » 4 years ago, # ^ |   +202 Be Um_nik Be nice and kind this time Get downvoted anyway :O
•  » » » 4 years ago, # ^ |   +101 If community generally dislikes whining, it probably should also generally dislike bragging :)P.S. I don't imply anything
•  » » » 4 years ago, # ^ |   +54 Come a few hours late See a 100+ upvotes Get confused
 » 4 years ago, # |   0 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"
•  » » 4 years ago, # ^ |   0 I think it should be done the same way you can find two closest points in the given set. Either do divide&conquer or sweep from left to right, and maintain recent points on set, sorted by y. When we have a new point (x, y), in set check everything with values from y - 2·R to (y + 2·R).
 » 4 years ago, # |   0 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.
 » 4 years ago, # |   +5 hmm, thought this trick is well known, first time meet them like 5 years ago in preparing tests for problemand it close to another geometry feature: convex hull of random 2D points is O(logn)
•  » » 4 years ago, # ^ |   +8 And O(logd - 1(n)) in d dimensions.
•  » » 4 years ago, # ^ |   +8 And if you choose them uniformly from a disk, it's O(n1 / 3) (article).
 » 4 years ago, # |   0 You can do it in o(n) with a pivoting algorithm right? Like finding the median element.
 » 4 years ago, # |   +76 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 1018. 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 1018 have weight .The optimal way to do said binary search boils down to exactly the algorithm you describe.
 » 4 years ago, # | ← Rev. 2 →   +13 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].
 » 4 years ago, # |   -39 Is it rated?
•  » » 4 years ago, # ^ |   -18 Is it a joke?
•  » » » 4 years ago, # ^ |   -23 emm···emm···emm···emm···
 » 4 years ago, # |   0 If we are getting the highest value in the array and keeping track of it ,then why are we doing binary search to find maximum value, can anyone explain please? Thanks!
•  » » 4 years ago, # ^ |   0 You don't know the maximum value.What the basic approach is you have to find each number and for that consider every index and then ask queries of type x y. We are doing binary search on y for every index x. If a[x] > y then your ans is greater than y so go towards right else your ans is less than y so go towards left.Then you get the maximum in O(nlogd). This blog focusses on improving this complexity. Btw really nice trick :)
 » 4 years ago, # |   0 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.
 » 3 years ago, # |   0 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
•  » » 3 years ago, # ^ |   0 A simple case is all elements of array a with same value.For array a with distint elements we can build array {1018 - 99999, 1018 - 99998, 1018 - 99997, ..., 1018} of size 10^5 and you would only discard elements at the last steps of binary search.
 » 3 years ago, # |   0 That`s a very good trick, thanks!
 » 3 years ago, # | ← Rev. 2 →   0 Really cool! It works for yesterday's Fhttps://codeforces.com/contest/1101/problem/FEdit: ok it's now in the editorial https://codeforces.com/blog/entry/64483
 » 3 years ago, # |   0 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).
 » 3 years ago, # |   0 This useful technique also appears in this paper: "Geometric Applications of a Randomized Optimization Technique".
 » 2 years ago, # |   0 Can we solve it if n is uint32 or uint64?
•  » » 2 years ago, # ^ |   0 Even with uint64 it should work in O(n + log($2^{64}$)log(n)) which is O(n + 64*log(n))
•  » » » 2 years ago, # ^ |   0 Could you summarize the algorithm of this problem, please? My program's queries are greater than 103000 if n is uint64
•  » » » » 2 years ago, # ^ |   0 Oh I had thought you were referring to the range of a as uint64. My bad.What do you mean by n is uint64? n is the amount of numbers you have. If you mean that n can be $2^{32}$ or $2^{64}$ then no, only n <= $10^5$ will work under 103000 queries.
•  » » » » » 2 years ago, # ^ |   0 Oh, I'm sorry, what I mean is that A[n] is uint64 array and n <=100 000
•  » » » » » » 2 years ago, # ^ |   0 The premise is that we will only need to binary search an elements value if it is the current prefix maximum (i.e greater than or equal to max element till now). So we will have to compare each element to the prefix maximum upto that point so $10^5$ elements will require atleast that many queries.And for each prefix max element we run binary search to find it's value which would take at most 64*log($10^5$) queries in the worst case.Which fits quite nicely in our 103000 queries limit, but... Normally we randomly shuffle the array elements before running this algo. Now the maximum element is expected to be found in the middle of the array. So we will not have to binary search for elements to the right in the array. But for the elements to the left of this max element, we have a similar case that the maximum of left subarray will occur in the middle of that and so on. So the array size is being halved at every max element and that is why we have log(n) binary search queries.But that being said it is still a randomized algo and works if array values are uniformly distributed between [ 1, $2^{64}$ ]. Consider if you have an array of uint64s such that all the elements are very big and very close to each other like in range [ $2^{64}$-10, $2^{64}$ ], then you will run the binary search not log(n) times but more than that because the maximum element now occurs in the array many times.You could have avoided this by checking that the new max element is strictly greater than the current prefix max, but our queries can only answer >= which would require 2 queries to check eequality, which would be 200000, already exceeding our query limit.
 » 2 years ago, # | ← Rev. 2 →   0 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.
 » 21 month(s) ago, # |   0 Pretty niice!!