MAXEP: Changing ratio in every iteration

general
,
1

I know that we can divide the entire range [1,N] into some appropriate ‘x’ number of blocks and solve it.

I am trying to solve the problem by binary search only (without linear search) by changing the ratio in every iteration. I am getting only 25 points by implementing the above idea.

Can someone please have a look at my code ? I have included comments wherever necessary.
Submission:-https://www.codechef.com/viewsolution/22016656

Thanks.

2

Your code fails because you are running out of coins. The first test case that fails is 1000 150 with the answer as 1 (the x required) (or something similar), your code asks the grader 6+ questions whose answer is 1 (i.e. the circuit breaks) so after resetting the circuit you get 150(7+) + (7+) coins > 1000 (max allotted) so the grader responds with a -1 and you get the WA.*

Reconsidering the proper ranges will help.

P.S.: I tested your code with 1000 150 and x as 1 and it throws a Division by Zero Exception.

3

The number of coins = 1000. Now consider the cost to repair is 150(max constraint). This means at max only 6 times we can repair the panel. N(max)=150,000. Now what if we use binary search. To find answer it will take at most log(150000)base 2 = 17 steps. Consider that answer is integer 1 , then you will find that 17*150 is the cost , which is greater than 1000. So to get answer take log(150000)base 8 which is less than 6. Just do binary search , but take mid = start+(end-start)/8; print out end , and you will get all points. We can prove that log base 8 actually solves the problem in at most 6 steps. It is guaranteed that it will get 1 as grader output at most 6 times, and I think this is optimal. There are many methods to solve but this was binary search style approach.

My code is provided.
link text

4

Thanks for the reply. In my code (You can check the link), I have used exactly the same formula which you have used to calculate ‘8’ as an optimal value. I change the divisor in every iteration as number of elements decreases and coins remaining decreases. I think something is going wrong when I round the value (floor or ceil) in every iteration.

5

Thanks for the reply. I think something is going wrong when I calculate the value of ‘div’ variable as I am rounding many values.

6

Try to figure out the maximum number of 1’s(number of times the panel is broken) that can be encountered while finding x.
You have 1000 coins, each time you find panel broken you have to pay c coins which are 150 in the worst case. So at max you can get floor(1000/150) 1’s i.e 6. So while interacting at runtime with the chef you can get only 6 1’s if you get 7th 1 you will not be able to find the answer. If you apply the binary search it iterates (log2 n) where n can be 150000 in the worst case, (log2 150000) comes out to be greater than 17. So there will be a point where a chef will return -1 i.e your coins will be finished and you will not be able to find the answer before that, thus you must be getting WA in the first and third test case.

As you stated that you are modifying the ratio and then applying binary search, try to figure out the maximum iterations where you can get 1, that can help you I guess.