You are not logged in. Please login at www.codechef.com to post your questions!

×

EDITORIAL to MAXEP Problem - December Long 2018

12
7

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

asked 18 Dec '18, 01:12

ritesh1340's gravatar image

3★ritesh1340
17018
accept rate: 11%

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

(19 Dec '18, 20:25) shivam_g14704★

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

link

answered 18 Dec '18, 01:41

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066
accept rate: 18%

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

(18 Dec '18, 02:45) ritesh13403★

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.

(18 Dec '18, 06:52) ay23064★

Thanks...!!!

(21 Dec '18, 01:22) ritesh13403★

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

link

answered 18 Dec '18, 09:44

ssj5_aaryan's gravatar image

4★ssj5_aaryan
122
accept rate: 0%

edited 18 Dec '18, 10:11

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) ritesh13403★
(19 Dec '18, 08:28) ssj5_aaryan4★
(19 Dec '18, 08:28) ssj5_aaryan4★

Thanks...!!!

(20 Dec '18, 02:54) ritesh13403★

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.

link

answered 18 Dec '18, 12:13

devansh1497's gravatar image

4★devansh1497
213
accept rate: 0%

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) ritesh13403★

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.

link

answered 18 Dec '18, 02:21

shoom's gravatar image

6★shoom
3534
accept rate: 30%

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) ritesh13403★

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

link

answered 18 Dec '18, 03:07

ritesh1340's gravatar image

3★ritesh1340
17018
accept rate: 11%

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

link

answered 18 Dec '18, 06:05

david_s's gravatar image

4★david_s
1111
accept rate: 10%

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

(18 Dec '18, 07:55) ritesh13403★

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

link

answered 18 Dec '18, 06:18

ritesh1340's gravatar image

3★ritesh1340
17018
accept rate: 11%

edited 21 Dec '18, 18:04

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

link

answered 18 Dec '18, 06:46

loch_ish's gravatar image

2★loch_ish
27
accept rate: 20%

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

Thanks.

(18 Dec '18, 16:06) ritesh13403★

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.

link

answered 18 Dec '18, 13:24

akashbhalotia's gravatar image

5★akashbhalotia
865214
accept rate: 10%

Correct...!!!

(19 Dec '18, 00:54) ritesh13403★

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

link

answered 18 Dec '18, 13:30

jsaurabh312's gravatar image

3★jsaurabh312
1
accept rate: 0%

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.

link

answered 18 Dec '18, 13:32

prmondal's gravatar image

3★prmondal
512
accept rate: 0%

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.

link

answered 18 Dec '18, 14:01

ducpro's gravatar image

6★ducpro
26818
accept rate: 0%

edited 18 Dec '18, 14:02

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

link

answered 19 Dec '18, 01:41

new_naveen602's gravatar image

4★new_naveen602
1
accept rate: 0%

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.

link

answered 19 Dec '18, 02:31

oleg_b's gravatar image

7★oleg_b
3195
accept rate: 16%

@oleg_b, I meant 450 coins as a cost of repair, not the total number of coins.

(19 Dec '18, 04:27) shoom6★

@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) oleg_b7★

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

link

answered 19 Dec '18, 09:57

vaibhav2709's gravatar image

5★vaibhav2709
615
accept rate: 0%

link

answered 19 Dec '18, 11:14

dhar1mesh's gravatar image

3★dhar1mesh
11
accept rate: 0%

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

link

answered 19 Dec '18, 11:32

whiteshadow98's gravatar image

4★whiteshadow98
162
accept rate: 33%

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

link

answered 19 Dec '18, 13:30

satan48's gravatar image

3★satan48
2
accept rate: 0%

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!

link

answered 19 Dec '18, 15:06

llaki10's gravatar image

5★llaki10
01
accept rate: 0%

edited 19 Dec '18, 15:08

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

link

answered 19 Dec '18, 17:30

utaha's gravatar image

6★utaha
2
accept rate: 0%

I have two questions.

  1. How did we came up with $x^A + x^B$ ?

  2. How do we solve $x^A + x^B$ ?

(22 Dec '18, 07:21) ay23064★

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) ritesh13403★

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?

link

answered 19 Dec '18, 20:14

shashank_chugh's gravatar image

2★shashank_chugh
1
accept rate: 0%

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.

link

answered 20 Dec '18, 16:34

gospelslide's gravatar image

4★gospelslide
371
accept rate: 0%

@shashank_chugh

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.

link

answered 20 Dec '18, 17:06

masood786's gravatar image

4★masood786
1063
accept rate: 13%

edited 20 Dec '18, 17:07

I simply divided n into blocks of 500. if i get 1 from grader i divided it again in parts of 100 for reducing the time complexity`#include <stdio.h>

include <stdlib.h>

int main() { int n,c,x=1000,max=1,k,i,j,flag=0; scanf("%d %d",&n,&c); int b; i=1; while(i<=150000) { x=x-1; printf("%d %d\n",1,i); fflush(stdout); scanf("%d",&b); if(i+500>n&&b==0) { for(k=i;k<=n;k++) { if(k<=0) continue; else { printf("%d %d\n",1,k); fflush(stdout); scanf("%d",&b); if(b==1) { printf("2\n"); fflush(stdout); printf("%d %d\n",3,k); fflush(stdout); flag=1; break; } } if(flag==1) break; } } if(flag==1) break; if(b==1) { printf("2\n"); x=x-c; fflush(stdout); for(j=i-500;j<=i;j=j+100) { if(j<=0) continue; x=x-1; printf("%d %d\n",1,j); fflush(stdout); scanf("%d",&b); if(j+100>n&&b==0) { for(k=j;k<=n;k++) { scanf("%d",&b); if(b==1) { x=x-c; printf("2\n"); fflush(stdout); printf("%d %d",3,k); fflush(stdout); flag=1; break; } } } if(flag==1) break; if(b==1) { x=x-c; printf("2\n"); fflush(stdout); for(k=j-100;k<=j;k++) { if(k<=0) continue; printf("%d %d\n",1,k); fflush(stdout); x=x-1; scanf("%d",&b); if(b==1) { x=x-c; printf("2\n"); fflush(stdout); printf("%d %d",3,k); fflush(stdout); flag=1; break; } } if(flag==1) break; } if(flag==1) break; } if(flag==1) break; } i=i+500; } return 0; } `

link

answered 21 Dec '18, 10:19

pshrimal000's gravatar image

2★pshrimal000
1
accept rate: 0%

1

@pshrimal000

Maybe your intent was correct to share a code along with the approach... But the way your code is written ; Its toooooo hard to read...

Maybe the better alternative would be to provide a link to your code (From some submission somewhere) .

Do give a thought to that...!!! Thanks...

(21 Dec '18, 17:57) ritesh13403★

What if when -1 strikes you have to search left and right both way??isnt it?

link

answered 21 Dec '18, 15:27

dynamo214's gravatar image

3★dynamo214
1
accept rate: 0%

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

link

answered 21 Dec '18, 18:24

sam132's gravatar image

2★sam132
01
accept rate: 0%

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

link

answered 28 Dec '18, 21:41

phoemur's gravatar image

3★phoemur
11
accept rate: 0%

edited 28 Dec '18, 21:42

Can you please tell how you derived the ratio??

link

answered 03 Jan, 09:02

allenjv123's gravatar image

2★allenjv123
1
accept rate: 0%

@allenjv123

I 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 every-time 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...

link

answered 04 Jan, 10:04

ritesh1340's gravatar image

3★ritesh1340
17018
accept rate: 11%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×1,056
×43

question asked: 18 Dec '18, 01:12

question was seen: 4,560 times

last updated: 04 Jan, 10:04