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 uncertainity of voltage is [1,150000] (From Constraints) Now, Lets test the board at a voltage 'V' in this range of 1150,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 : 1150,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 HEREDon'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 OBSERVATIONIn 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 SENTENCESo 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 coordinate 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 WORKNote 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. IMPORTANTSo 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' withrespectto your Voltage : That is your answer COMMON MISTAKEIts 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 :
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 SAYI 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...!!!asked 18 Dec '18, 01:12

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 :) answered 18 Dec '18, 09:44
Thanks for the approach @ssj5_aaryan Since I am a complete beginner , so I try to read as many codes as possible to Learn what are the types of coding styles adopted by people. I Understand the logic of your code, but can you also share a link of your code so that I may come across varying coding styles as well...!!! thanks in advance...!!!
(18 Dec '18, 16:15)
Here is one such solution : https://www.codechef.com/viewsolution/21994162
(19 Dec '18, 08:28)
Here is one such solution : https://www.codechef.com/viewsolution/21994162
(19 Dec '18, 08:28)
Thanks...!!!
(20 Dec '18, 02:54)

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. answered 18 Dec '18, 12:13
Thanks for the approach @devansh1497 Since I am a complete beginner , so I try to read as many codes as possible to Learn what are the types of coding styles adopted by people. I Understand the logic of your code, but can you also share a link of your code so that I may come across varying coding styles as well...!!! thanks in advance...!!!
(18 Dec '18, 16:47)

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. :) Potentially the constraint for maximum repair cost could be even higher, like 450 coins. In which case the ratio of 1:44 would work. answered 18 Dec '18, 02:21
Hey @shoom... Thanks for the feedback. I actually had to write something about ratio here, but it exceeded the number of characters allowed in the comment box. So I wrote that in the answer section , Please suggest If I am wrong anywhere... Thank you...!!!
(18 Dec '18, 06:23)

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...!!!answered 18 Dec '18, 03:07

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...!!! answered 18 Dec '18, 06:18

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). answered 18 Dec '18, 06:46

The constraints were very beautiful in this question, isn't it?? 1,50,000(n) = 150(c) * 1000(coins) All i did was divide N in the range of 1000. Like let us say n=100005. So, ranges are= 11000, 100012000, 20013000,..................upto 99001100000, 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. answered 18 Dec '18, 13:30

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. answered 18 Dec '18, 13:32

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. answered 18 Dec '18, 14:01

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:
The total expense: 59+150+49+150+49 = 457 at most. answered 19 Dec '18, 02:31
@oleg_b, I meant 450 coins as a cost of repair, not the total number of coins.
(19 Dec '18, 04:27)
@shoom, I stand corrected. It appears that it is possible to design an algorithm where the total maximum cost is less than 400 coins in the worst case scenario.
(22 Dec '18, 00:26)

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)$ answered 19 Dec '18, 09:57

here is easiest solution https://www.codechef.com/viewsolution/21822674 answered 19 Dec '18, 11:14

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 answered 19 Dec '18, 11:32

150000 was a very very loose limit. I am pretty sure it could have been at least 10^8 within 1000 coins.(c=150) answered 19 Dec '18, 13:30

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:
(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].
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! answered 19 Dec '18, 15:06

A previous IOI gold medalist told me that there's a similar problem in POI: when the voltage is too high, we get a penalty of $A$ dollars when the voltage is too low, we get a penalty of $B$ dollars The interesting thing is that the best strategy is to guess with a ratio 1:$\alpha$, where $\alpha$ is the root of the equation $$x^A+x^B=1$$ so in the original problem, I used wolfram alpha to solve $x+x^{150}=1$ (it should be $x+x^{151}$ in fact) and got the magic number 0.97556. Here's my code: https://www.codechef.com/viewsolution/21774242 answered 19 Dec '18, 17:30
I have two questions.
(22 Dec '18, 07:21)
yes please @utaha ( Or anyone who got that )... why is that equation correct and how do we solve that equation...???
(24 Dec '18, 01:57)

I could not get this question right (I tried myself many values(testcases) and they were correct but still codechef said wrong answer? can anyone please tell mistake in my code of MAXEP? answered 19 Dec '18, 20:14

Similar to egg drop problem. As good as finding on which floor among 150,000 floors the egg will break with 6 eggs at most (1000//150). Can be solved with dp. answered 20 Dec '18, 16:34

In the condition checking of the for loop, you are comparing s against an uninitialised variable (e). That seems to be (one of the) problems. answered 20 Dec '18, 17:06

What if when 1 strikes you have to search left and right both way??isnt it? answered 21 Dec '18, 15:27

In my code , I used random function as a way to get an arbitrary no as specified in one of the constraints. Here is my code : https://www.codechef.com/viewsolution/21905623 answered 21 Dec '18, 18:24

I think using srqt decomposition would be better, as you only need to burn the panel 2 times to find the right voltage, regardless of the cost. This seems more likely what one would do in real life, instead of burning the panel many times for no reason as happens in binary search approach (with ratio)... answered 28 Dec '18, 21:41

@allenjv123I shared a link to that ratio determining code in the editorial above under the heading 'Key Sentence' ; well I can share that code again for you HERE ( Remember this is Python code  2.7 version ). You can run the code online or test in locally for a better understanding. This code actually tells that what would be the array size after 5 steps if you keep on dividing the array in ratio 1:k ( where k in the code is 3.5 ) and everytime discard the right half. And I have explained in the editorial itself as to why would this ratio work. You should read that. On How I derived 3.5 :What I explained in 'Why will that ratio work' and the concept of shift from binary search to linear search was in my mind beforehand. So actually I ended upon writing that code generalised for 1:k, Applied some hit and trials ( With k=1,2,3...(Actually I dont remember my trials) and finally ended up with k=3.5 ). So I didn't derive it, rather it was like maybe this ratio thing will work ; Wrote a ratio code and did hit and trials to what that 'k' can be instead of deriving it in some mathematical way. And I proceeded with k=3.5 when I saw that after 5 operations ; I was left with array size 82 ( From code ) and had 1000(150+1)*5=245 coins left ; enough to shift from binary to linear search with a scope of one more burn in the linear search) Still if you have any doubts , or wanted to ask something ; feel free to ask brother ; no Problem at ALLLL :) ...!!!(Just be more specific about your doubt that what exactly you want to ask...) But once again no problem at all. Hope this helps... answered 04 Jan, 10:04

please add "unofficial" to heading. btw, good work.