EDITORIAL to MAXEP Problem - December Long 2018

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…!!!

12 Likes

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.)

4 Likes

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.

Sure Sir… I am a beginner and right now not knowing even a scratch about Square root Decomposition Technique… But will Surely Learn and implement the way you have suggested

Thanks a lot for the feedback… Honored to get some tips and techniques from experienced coders…!!!

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…!!!

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

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…!!!

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…!!!

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

What I did was that I increased the base of search. As for Binary search, the base is 2 and tertiary base is 3, I went on ahead and made a search with the base 10. With that complexity of guess greater than x will always be O(log_{10}(N)).

By the way nice editorial.

Yes @david_s will do…!!! , just as @shoom said, every ratio of format 1:k with k>=3.5 and k<82 would work…!!!

This was my Very first Editorial and very pleased to see good coders sharing their experience…

Thanks a lot…!!!

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:

1 Like

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.

1 Like

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.

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.

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.

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.

Thanks For sharing a new approach… Makes me Learn new things…!!!

Thanks.

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…!!!

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…!!!