EDITORIAL to MAXEP Problem - December Long 2018

binary-search
editorial
linear-search

#1

This is a classical problem of Binary Search.

#HOW BINARY SEARCH ------->>
For the very beginners : It is taught very much in schools (At least in Indian Schools) that binary Search has a prerequisite that it can only be applied to a sorted array in order to find an element stored in the array. That is correct but is INCOMPLETE.

Think of the problem in this perspective : That we need to find the maximum Voltage supply the electricity board can withstand (More Appropriately LEAST value of voltage at which board burns). And the band of un-certainity of voltage is [1,150000] (From Constraints)

Now, Lets test the board at a voltage ‘V’ in this range of 1-150,000.

Important Sentence :If the board is capable of withstanding (not burning at) this ‘V’ voltage , then its obvious that it can definately withstand any voltage less than ‘V’ without burning.

For example you assume ‘V’ for the First time is say 1500 and in response you get 0 (Meaning that the panel is not burnt, then the board can withstand 1200 Volts,1000 Volts - means every voltage less than the assumed ‘V’.

Similarly : If you assume this ‘V’ Voltage and you get ‘1’ in response (Meaning that the board is burnt) Then it will burn at every Voltage greater than ‘V’. Example : If your assumed ‘V’ was again let say 1500, and you come to know that the board burnt at this voltage, it will burn at Voltages 2000, 2100 Or every voltage greater than assumed 'V’

The reason I am calling this as an analogy to the classical binary Search approach that is taught in schools is because You have been provided with an answer range of Voltage : 1-150,000 (in question) Now lets consider this answer Range as Numbers Stored in an Array (Means numbers 1,2,3… 150,000 Stored in a sorted array)"

ANALOGY : If the board is burning at this voltage ‘V’ ; It will burn at all voltages Greater than ‘V’. SO AT THIS POINT ; YOU CAN DISCARD THE RIGHT HALF OF THE ARRAY ( As we Used to Discard A complete half while Searching for element in a sorted array )

#MISTAKE ONE COULD MAKE HERE
Don’t Discard the voltage ‘V’ itself because even that can be the true solution to the question

And In case Board is not burning at ‘V’ ; Then it will not burn at any voltage less than ‘V’ ; So you may DISCARD THE LEFT HALF OF THE ARRAY) This time you can discard the voltage ‘V’ as well.

This is the reason why you can think of Binary Search here

##TRICKY OBSERVATION
In classical Binary Search , we used to take the exact middle element and divided the array into exact two halves (If the array has even number of elements, and in case array has odd number of elements , still the division of length of array is done in Approx 1:1 Ratio)

Note ; Since on every burn ; you need to spend some coins from your purse in order to repair the circuit board (And expenditure on repair in worst case is 150 coins)

Initially we have 1000 coins in the purse. And voltage uncertainity in worst case in 150,000. So its easy math that we can at max allow 6 burns while trying to determine our answer (AS six burns would in worst case lead to 150*6=900 coins {Worst case means expenditure for repair = 150 MAX} and one more burn if happens, then we needed to spend 150 coins more which we cant as we initially had 1000 coins and spend 900 on 6 burns)

KEY SENTENCE

So instead of Dividing array into two parts with ratio 1:1 , Its Better to divide array at each step in some other ratio so that max number of burns <= 6. This means your partition should not be exactly in the center , rather somewhere to the left of it So that number of cases of burns could be minimised

So I used the section formula taught in basic co-ordinate geometry , and found that the ratio can be 1:(3.5)
Or 2:7.

I found this ratio by some hit and trials and with help of this code (You can copy paste this code and run on any online compiler in Python Version 2.7 {PYTH in Codechef Compiler)

REASON TO WHY THIS RATIO WILL WORK

Note that after 5th operation (Means board has burnt on 5 occasions) with ratio = 1:3.5, Integral Value becomes 82. So even if the actual answer is 1, you will now be left with a voltage uncertainity of in range [1,82] (Because if answer was ‘1’ you would receive ‘1’ which means burnt board on every of those voltages displayed as output of my code there and you would be discarding the right part of the array always.And you have just made 5 burns which in worst case would cost you : 150*5=750 on repair.

So you have enough money for one more repair.

IMPORTANT

So after allowing a binary search ; now you can shift to LINEAR SEARCH when you have coins in Purse more than the range of uncertainity of voltage. Do this from least value of answer range to highest value one by one… And the moment you receive ‘1’ with-respect-to your Voltage : That is your answer

COMMON MISTAKE

Its imperative to drop down your answer range to a certain level in ‘5’ burns ; Because your 6th burn will happen when you shift from Binary to the Linear Search to determine the final answer. So choose a ratio so that you allow 5 burns in binary and leave some coins in your purse for the 6th burn that would happen in the linear Search to determine the final answer

Its not that in my ratio 1:3.5 ; 3.5 is a magic number and only this golden ratio can be used to determine the outcome. you can play with the ratio part yourself but remember to stick to 5 burns at max in binary search section with your ratio.

CODE IMPLEMENTATION ----->>

Since this problem required some binary search and a Linear search Combination , that too where linear Search in worst case would have just 150 elements , it was quite obvious that the implementation can be done easily in some of the slow languages also…

Hence I wrote Solution to this Problem in PYTHON 2.7 and my code can be found HERE

UNDERSTANDING THE CODE :

  • Uptil Line no. 30 its Binary Search
  • From Line 34 its linear Search
  • Line number 28 is the crucial line to decide when to switch form binary to linear Search
  • Variable c holds the cost for repair
  • Variable Purse holds the number of coins left with you

ANOTHER COMMON MISTAKE ---->>

See this difference in line number 28 in this code with above code. This code misses ‘c’ and gives WA as verdict.

Reason is simple ; if you have shifted from binary to linear search without taking number of coins into account, then there is a possibility that on every enquiry and getting a 0 (Not Burnt) as answer in interaction, you are always spending 1 coin, which might turn you out of coins as that one voltage comes when you need to repair the board and print the answer.

I decided to point this mistake out as I assume many people ( and even me on first attempt) may have done this mistake.

FINAL SAY

I tried to bring out all sorts of mistakes someone makes with this editorial. IF you find this post helpful, kindly upvote it because I am a beginner and learning myself. Many times I like certain posts, certain articles but cant upvote them because I am not having enough reputation points.

Since I am a beginner, So any piece of advice anyone can give me upon my code or logic is very much welcome…

HOPE THIS HELPS… HAPPY CODING…!!!


#2

Good job. As an alternate, try to explore square root decomposition perspective of the problem. Meaning, divide numbers from [1,N] into \sqrt N blocks of equal size. We can, skip an entire block is the voltage at highest value in this block does not break the circuit. The beauty is that, we can get a worst case proof for this case which puts cost to be less than 1000, which is left as an exercise to the reader. (at least for now :p.)


#3

The other boundary for the ratio can be determined by considering the case when the answer is the very last point. It gives you the limit of around 1:82.
So selecting the ratio anywhere between 1:3.5 and 1:82 should work. :slight_smile:

Potentially the constraint for maximum repair cost could be even higher, like 450 coins. In which case the ratio of 1:44 would work.


#4

Sorry I missed out the fact that right after the contest ; solutions won’t be public…

If thats the case and you are not able to see my Full Code solution (Implementation) in those links above, you may check it HERE. The difference would be just that you won’t see the submission report… But its all AC so that even does not matter

HOPE THIS HELPS… HAPPY CODING…!!!


#5

I guessed a ratio of 1 : 9 for the biassed binary search. With this ratio, I found that I could achieve the solution quickly with no need for any linear search


#6

Thanks for the suggestion. It really helps a lot…@shoom

Actually, even when I was figuring out what the correct ratio should be, I knew very well that it has to be something of the format (1:k) such that k>1

Now, I started imagining that what if I had to discard the left half of the array at each step and always move rightwards (Basically was trying to figure out the mechanism of my algo if answer was 150,000). So when you needed to move all the way to the right, then it was IMPERATIVE FOR ME THAT EVEN WHEN I AM DOING SO, I SHOULD BE DOING IT IN LESS NUMBER OF STEPS.

This feeling was not to avoid a TLE, I already knew I wont be getting that (Thats because I coded in Python - a slow language when runtimes are considered) but just to lessen the number of steps…

So I decided not to just find out that ‘k’ in the ratio, rather finding out The least possible ‘k’ so that when I am discarding the left part (And moving rightwards, I am discarding a good amount of it) A long contest ; so I was technically free to experiment more rather than Straight up going for an AC.

Even I believe that the ratio is that part of my version of solution with which a lot of people can play and a lot of ratios would lead you to getting an AC verdict

But for me (Its just for me maybe someone else’s opinion differs here) —>

The least number of steps at cost=150 (In worst case) could be achieved very much optimally with a ratio of 1:3.5 in the best possible way, either if the Answer to the question is at the extreme left (that is answer is ‘1’) or at extreme right (Answer is ‘150,000’)

That’s the reason, for me : The Golden Ratio was always 1:3.5

But its true that this is correct for worst case cost of 150, otherwise if ‘c’ is changed, then the ratio would differ.

Once again, I am not very much experienced, so If I am thinking something wrong… Please let me know…!!!


#7

I did the problem in another way. Try with voltage 1. If it doesn’t break, try with voltage 2. Keeping doubling the voltage to try until the panel breaks. Once the panel breaks, the range will be limited to the last successful voltage ( + 1 to be specific) and the current voltage at which the panel broke. Each step decreases the search range from x to x / 2 (in worst case). Each iteration requires log(x) steps. So the complexity is going to be log^2(n).

https://www.codechef.com/viewsolution/21907561


#8

Another beautiful, easier method is basic linear search on chunks of say, 1000, the first position which returns a value 1, helps us restrain our range to under a 1000 (using the fact that 0s and 1s are in ascending order). Now, after one fix, you can break it into smaller chunks of say, 100. Again, the first ‘1’ restricts the the answer range within a range of a 100. Now, after another fix, you can just check every element in these 100(or less) and the answer should be the first value where we get a ‘1’(we need not fix it).

Therefore, the maximum money spent is 150000/1000 + 1000/100 + 100 + 2*c <= 150 + 10 + 100 + 300 = 560.

Hope this helps :slight_smile:


#9

I just divided the entire range in blocks of 500 indices. So that would give us a total of 150000/500= 300 checks in the worst cast. In case if the circuit breaks, then I exit this loop and repair the circuit once. This would give me a total expenditure of 300(first operation) + 150(repair operation) = 450 coins. Now I have gotten a bucket of 500 indices in which the answer lies. So, I again applied linear search here to check all the 500 indices for the correct answer which required 500 more coins.
So, the maximum number of coins that I needed to spent in this problem was 950.


#10

It is seen that minimum number of coins are used up when the gaps we choose are the square root of N, as @vijju123 mentioned.


#11

The constraints were very beautiful in this question, isn’t it??
1,50,000(n) = 150© * 1000(coins)

All i did was divide N in the range of 1000.
Like let us say n=100005.
So, ranges are= 1-1000, 10001-2000, 2001-3000,…upto 99001-100000, 100001 - N.

We check on the upper limit of each range. the first time we get a 1, we don’t check afterwards as our answer is between this upper limit and the upper limit of the previous range.

In this range finding process, we will use atmost (150 x 1 + 1 x c) coins, i.e atmost 300 coins.
Now, we have a range of 1000 numbers (just like N=1000 ) from which we have to find our answer.

Then we apply binary search 2 times in this range to decrease our range of values to 250.
coins used=300(previous)+300(current)=600.

So,600 coins have been used up and we have a range of 250 numbers. Here we apply linear search in that range.

So, max coins uded=600(previous)+249(linear search)+150(when the output is 1)=999 coins.

THUS BY USING MAX 999 COINS, WE HAVE FOUND OUT THE ANSWER.


#12

I solved the problem by doing ternary search (1:3 ratio) till I have left with n elements in search range and n <= c. Then I did linear search with c coins in my hand.


#13

You can find the accurate range by DP :). That’s what I did, finding out that for the max test case you need a minimal of 693 coins to solve.


#14

We can also just do binary search with ratio 1:7


#15

To the earlier comment by @shoom:

I don’t think 450 coins constraint is feasible. According to my calculations, it’s 457 coins. For such constraint, you can do the following:

  • Check the circuit on 2500, 5000, 7500, …, 147500 voltages. That’s 59 points to check, or 59 coins. You may break it once, and that’s extra 150 coins to shell out. You check with such interval only up to the breakage.
  • Now the interval to check is 2500 units. Split it in blocks of 50, so if you break the circuit at 7500, then you need to check at 5050, 5100, 5150, …, 7450. That’s another 49 coins. Again, you may break it once; that’s an extra 150 coins.
  • Now the interval is only 50 units. You need to check the first 49 points to figure out the maximum voltage - or another 49 coins.

The total expense: 59+150+49+150+49 = 457 at most.


#16

Another better approach to this question is Square root decomposition method. I divided the array of length n into \sqrt n divisions of length \sqrt n. Now we need to now check the voltage at the mean value of voltage of every division. If it dosen’t burn out go for next division else apply linear search for this division.
Time complexicity is O(\sqrt n)


#17

here is easiest solution
https://www.codechef.com/viewsolution/21822674


#18

Simply check in the intervals. What I did was checked in the intervals of 1000. then in a particular 1000 range. Eg:- 1 1000 THEN FEED 1 2000 and so on till you get 1. We will know the thousand range through this. Now say you get 1 for 1 7000, this means the voltage lies between 6000 and 7000. Now check for 100 range that is
1 6000, 1 6100 etc… You will get the final 100 range. Do the same for 20 range and 5 range. Now you will have 5 elements left. Check them one by one. The worst case possibility will occur for n=150000, c=150. Even the worst case will consume 168+4*c i.e 768 coins


#19

150000 was a very very loose limit. I am pretty sure it could have been at least 10^8 within 1000 coins.(c=150)


#20

Here’s my solution that would work for up to 10^11 in place of 150,000.

Let’s reverse the problem and ask the following question: If we have 1000 coins initially, what’s the largest value of N for which we’d be able to always find the smallest voltage that breaks the panel. Clearly, this value is at least 150,000, since the problem statement suggests there’s always a solution. Let’s generalize this question and ask the same for any number of initial coins <= 1000. Call this function f. Let’s see how to compute f[m], where m denotes the initial number of coins:

  • If the initial guess is X, 2 things can happen:
    (1) The response is 0, meaning the resulting voltage is in range R = [X + 1, f[m]] . In this case, we would be left with (m - 1) coins. By definition, we can guess from at most f[m - 1] values, so |R| <= f[m - 1], where |R| denotes the number of integers in range R.

(2) The response is 1, meaning the resulting voltage is in range L = [1, X]. In this case, if X > 1, we need to repair the panel and pay the penalty, which leaves us with (m - 1 - c) coins. By definition, X <= f[m - 1 - c].

  • Combining these 2 scenarios, taking X = f[m - 1 - c] maximizes f[m]: f[m] = f[m - 1] + f[m - 1 - c].

By precomputing this array, we see that the value of f[1000] can become quite large. For c = 150, f[1000] = 422250194531.

The way we constructed f[m] also shows the algorithm which will help us to find the minimum voltage that breaks, without violating rules:

  • Initially, the range of possible voltages is [1, N]. The range will keep shrinking as we make guesses.
  • Let’s say the current range is [low, high] and we have M coins left. Let’s look at the value of f[M - 1 - c]. By making our guess (low + f[M - 1 - c] - 1), we guarantee that after this move we’ll either have (M - 1) coins and a range with length <= f[M - 1], or f[M - 1 - c] coins and a range not larger than f[M - 1 - c]. In both cases, we’ll be able to find the answer without a doubt.

I omitted some base cases to keep it shorter, but here’s my implementation for more details. Hope it was helpful and feel free to ask questions if something’s unclear. Cheers!