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…
