"DETAILED" EDITORIAL to MAXEP Problem - December Long 2018

editorial
, ,
29

Can you please tell how you derived the ratio??

30

#@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 :slight_smile: …!!!

(Just be more specific about your doubt that what exactly you want to ask…)

But once again no problem at all. Hope this helps…

31

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

32

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

33

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.

34

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

35

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

Thanks.

36

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

37

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

38

Correct…!!!

39

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

40

Here is one such solution : CodeChef: Practical coding for everyone

41

Here is one such solution : CodeChef: Practical coding for everyone

42

please add “unofficial” to heading. btw, good work.

43

Thanks…!!!

44

Thanks…!!!

45

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

1 Like
46

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

47

I have two questions.

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

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

48

yes please @utaha ( Or anyone who got that )… why is that equation correct and how do we solve that equation…???