MAXEP Editorial(Unofficial)

You can straightaway know that we need to divide the voltages in range but what would be a good range?

Suppose our each interval range is m, and total length is n, then in the worst case we would look at (n/m) intervals and for the last interval we might need to do a linear search upto the end of the interval. So our cost function, let call it f(m) would be:

f(m)=(n/m)+c+m

We can find out by differentiating that this function achieves minimum value at m=sqrt(n) and the minima is less than 1000. Since we are not asked to minimize the cost but to achieve an answer in cost < 1000, we can use different ranges as well. I tried the value of m as 400, 500, 600 all of which worked.

Most people find that this sqrt(n) was intuitive and I would agree but still proof is better.

Hi, I followed your approach, but I got the wrong answer in some subtask. Can you check my code?
Link: https://www.codechef.com/viewsolution/22134354

//