"DETAILED" EDITORIAL to MAXEP Problem - December Long 2018

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.

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

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; }

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

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

Can you please tell how you derived the ratio??

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

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…

Thank you…!!!

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

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

Correct…!!!

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

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