15295 Spring 2021 #3 Binary Search -- Problem Discussion

February 7, 2021

This is where we collectively describe algorithms for these problems.  To see the problem statements and scoreboard, go to this page and select this contest.

A. Aggressive Cows

This is a typical instance of the binary search optimization problem. Instead of trying to choose optimal positions to obtain a minimal distance, we choose a distance d, and check if we can choose c points out of the n points such that each pair of the points are at least d apart. One can check if you can choose c points such that they’re all at least d apart by a greedy algorithm (choose the first point, choose the next point at least d further than that one, etc.).

In order to find the next point that is at least d further than the last point chosen, one can do a binary search (lower_bound for c++, for example), so it takes at most C log N steps to determine if all cows can be placed at least d apart.

It remains then to find the optimal distance, which can be done by binary searching on the distance d. As the maximum possible distance is 10^9, the complexity of this is C log N log 10^9, which is well within time bounds.

-Brad

Brad, I just want to add one thing to your solution.  When doing the test to determine if a given value if d is possible, there’s a simpler O(n) algorithm -- no binary search is necessary.

Say you’ve just put a cow at point x_i. Now you start walking to x_(i+1), x_(i+2) etc each time checking if the distance is at least d from x_i.  Eventually it finds x_j which is far enough, and then does the same thing again with x_j.  Since the algorithm always proceeds to the next point (never considers a point more than once) the total work is O(n).  --Danny

B. Valhalla Siege

Compute the prefix sum of all the strengths. Then for each group of incoming arrows, do a binary search to find out how many of the rest of the people does it take to take on all the arrows.

Specifically, keep track of which person is currently at the front of the line, as well as how many more arrows this guy can take (or alternatively, keep track of how many arrows have been taken before the last revive, similar idea). Then loop through all groups of arrows: if a group of arrows cannot all be taken by this front guy, calculate how many more arrows need to be taken. Then perform a binary search ranging from the next guy to the last guy to find exactly who will the last arrow hit. Finally update who is at the front and how many more arrows can be taken.

-Yichen Zhang

(hint: std::lower_bound is helpful)

You can also just keep track of how much total damage has been taken in the current “wave” and use the same binary search to just print out how many people died, resetting it once everyone dies.

C. Preparing for the Contest

We sort the bugs by decreasing difficulty. It suffices to see if we can fix all the bugs in x days, and binary search on x. A clear upper bound for x is m, so we can do this is log(m) iterations.

We need to hire a student with skill at least the most difficult bug, and we greedily assign it to the hardest x bugs, and recurse. To choose the best student for these bugs, we note it’s always optimal to just choose the student that requires the least number of passes. This is because we’re choosing students in decreasing requirements of skill, so we’ll always have more choices in a later decision. Finding this student can be done with just a min-heap in O(n log n). We sort the students by decreasing order of skill, and add them to the heap if they can solve the current problem.

Then we just keep track of how many passes we’ve spent and see it’s impossible if we require more than s passes, or there’s a bug that’s too hard for a student to solve. Overall this takes O(log m(m + n log n)) time - Zack

D. Weakness and Poorness

The poorness of the array formed by subtracting x from all constituent elements varies unimodally with x. So one method to solve this problem is via ternary search. The poorness for a fixed choice of x can be computed in time O(n) (just compute both the minimum and maximum subarray sums), which gives us an O(n * log(1/eps)) time algorithm for this problem, where epsilon is the desired precision we wish to attain. Doing 200 iterations or so of the ternary search should be more than sufficient.

Btw, there’s also a solution with binary search (looking for the point at which the negation of the minimum would exceed the max), but I think ternary search is more obvious (apparently with precision issues?) I ran into precision issues myself; I think one just needs to run it at least 100-200 iterations to solve the precision problem.

-Wassim

(👆yes the smart idea is to cap the number of iteration at 200 or so, if using binary search. I failed 15 times during the competition and accepted in one go after seeing this.. thx) - Yichen Zhang

(For what it’s worth, I mentioned this trick in my lecture before class yesterday.  --Danny :-)

Quick proof for why this varies bitonically: the poorness of a subsegment corresponds in terms of x to |x*len + base| which looks like a V above the x axis.  This has upper area being convex, and the maximum of some amount of graph is their intersection, so we remain convex as we consider the upper area graph of the function that is the maximum of all the poornesses in terms of x. - Chris

E. Max and Bike

The quickest way to do this is (surprise surprise) binary searching on the answer.  Given some amount of time t, we want to be able to check for the furthest “distance” the tracker can travel in that time.  The expression for the position of the tracker after t time is

 (note that this is actually monotone w.r.t. t which justifies the binary search) where t0 is just some constant we get to choose (think of it as the current time of rotating when we start), and t is the time that elapses.  We want to find the t0 that maximizes that expression.  Plug this into Wolfram Alpha to get

 where the last two answers are clearly the ones we want.  We can then compute the t0 in constant time, plug it back in in constant time to that above expression, and check for the longest distance we can travel.  If that distance is at least the distance between the start and finish lines, then the time we’re checking upper bounds the answer, otherwise it lower bounds the answer.  (I then proceeded to accumulate 10 failed submissions by screwing with epsilons right before the contest ends).

--- Chris

F. Guess two numbers

The first idea is to keep track of the 2-d space of possible (x,y) pairs efficiently. To do this note that the possible area always looks like a sort of staircase function and store the list of top right corners of every stair. Now that we have this we can keep track of the viable area on receiving any of the 3 responses from the grader.

Once you do that we want to reduce the area of the space by a constant factor every turn (ie. we ‘binary search’ on the 2d area).

To do this we can pick a point such that <⅓ of the area is to the left and <⅔ of the area is to the right (with the remainder being in line with the point) and <⅓ of the area is to below and <⅔ of the area is to the above.

We can find this point by computing the x and y values independently by iterating over the possible area structure.

Now note that on any response of 1,2 or 3 the new valid area is at most ⅔ of the old valid area.

Thus after log_3/2(10^3 6) < 205 steps, the valid area will be 1 and we will win.