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
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?
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.
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 : CodeChef: Practical coding for everyone
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)…
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…
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…!!!
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…
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)).
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…!!!
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…!!!