Bear and Bribing Tree
Problem link : Practice
I am going to try and explain a solution similar to what is described by the editorial. It’s mostly what I have picked up by reading the editorial, seeing the tester’s code, and using my own reasoning. I agree with @gonecase and @neget here that the provided explanation and code is quite hard to follow. So here goes.
First of all I think the “dp” solution (in the editorial) is a bit misleading. The problem can be understood better as a recursion tree. In fact it is nearly identical to the mergesort procedure. This is the only prerequisite. You don’t even need a segment tree as in the tester’s solution.
The approach:
Let’s start with an array b of n=2^h bears, with each having a strength and bribes value. We are going to apply a mergesort-like procedure on this array. We will split the array in half, run recursive calls on both halves, and then somehow merge the two halves. At each level of the recursion tree, b[i].bribes will denote the minimum number of bribes it takes to ensure bear b[i] reaches that level. So after we have applied our procedure, b[0].bribes (assuming 0-based indexing) will be our answer, as Limak is the first bear in the array. Initially all bribes values are 0. The strength values are set initially for each bear and never change.
Assume we are at a recursive call at height d with a range of the array from start to end. We recursively solve for the left and right halves of our current range. We now know how many bribes it takes to get each bear in [start, end] to height d-1. Now is the important part. Take your time and understand the following points.
- If a bear b[i] has reached the height d-1, it can only compete with a bear in the other half to reach height d. This is because it must have already defeated other bears in its own half.
- A bear b[i] can reach height d from height d-1 by two ways only, either by winning fairly OR by means of a bribe from Limak.
i. If we choose the fair win, then we can only considers bears in the other half with strength less than b[i].strength and we will choose a bear who required least bribes to get to height d-1. The new value of b[i].bribes would be b[i].bribes + b[j].bribes where j is the bear with minimum bribes value among all bears in the other half with strength\lt b[i].strength.
ii. If we choose to get a bribed win, then we should consider only those bears in the other half with strength not greater than b[i].strength+k and once again choose the bear who required least bribes. The new value of b[i].bribes would be b[i].bribes + b[j].bribes + 1 where j is the bear with minimum bribes value among all bears in the other half with strength\le b[i].strength+k.
Out of the two, we choose the option which minimizes b[i].bribes. If no suitable bear j is found in either choice, we set b[i].bribes to a very large value.
If you have understood the procedure above, the only thing left is an efficient implementation. As order does not matter in the other half when picking a bear from the other half, we can sort a copy of the other half by the strength values. Then we can binary search on the sorted array for our desired limiting value, which will either be b[i].strength or b[i].strength+k. Next we need to query minimum in the range [0, x] where x will be the index returned by the binary search. We can easily use a prefix min array for this which can be precalculated in linear time.
(We have avoided the segment tree in the tester’s solution by querying minimum from the beginning to strength+k instead of from strength+1 to strength+k).
The cost of sorting dominates and the worst case at each level is \mathcal{O}(n\ log\ n). There are log\ n levels in the tree, hence overall time complexity is \mathcal{O}(n\ log^2n).
Link to my solution here.
Improvement 1:
A small modification to the above algorithm improves performance significantly. Instead of sorting the left and right halves by strength each time, we can simply merge them in sorted order into the main array (as in mergesort). The downside of this is that a bear loses his position in the array as it gets shuffled. However as each bear remains in the half he should be in, the algorithm remains correct. To identify our bear Limak we can add another field id to each bear value. At the end of procedure we linearly scan for Limak and output his bribes value as the answer.
Accepted solution here.
Improvement 2:
As mentioned in the editorial, it is possible to achieve \mathcal{O}(n\ log\ n) runtime with the “two pointer” method. These pointers move monotonically, that means they move in one direction only, and they can help us get rid of the binary search to shave off a factor of log\ n.
Consider you have two sorted arrays of integers A and B. For each A[i], you are required to find the smallest j such that B[j]>A[i]. This is simple task if you use binary search, taking \mathcal{O}(n\ log\ n), but let us discuss an alternate approach.
j = 0
for i in range 0 to len(A)-1
while B[j] <= A[i]
j = j + 1
current value of j is the answer for A[i]
Why does this work? It works only due to the fact that if i_2>i_1, then answer for A[i_2] \ge answer for A[i_1]. The pointers here are i and j. When we move i along A from low to high, we can also move j along B in the same direction from low to high, and still be sure of getting all the correct answers, that too in O(n).
We can adapt this in our solution to work for the strength values of each bear, and maintain a prefix min variable on the bribes values as we update the pointer. We will need two separate j pointers (similar to the two separate binary searches), one for the fair win which depends on strength, the other for bribed win, which depends on strength + k.
The runtime has been reduced from \mathcal{O}(n\ log^2n) to \mathcal{O}(n\ log\ n).
For implementation details, check my solution here.
As a sidenote, for a better understanding of the pointer technique, check out this link.
Please feel free to ask if something is not clear 