For most people, the first method that comes to mind is binary search. However binary search in the worst case requires log2(n) comparisons. This is troublesome if the value of c is really high. We can only make about 6 mistakes before finding out the answer.
Other people have posted a modified version of binary search to solve this problem. Here’s my approach which doesn’t use binary search.
Assume N is 1000 and we sequentially go from 1 to 1000 and ask question about whether it is a faulty voltage or not. This will definitely give us the right answer as long as the faulty voltage is somewhere between 1 and 850. Because if the faulty voltage is 850, we have already spent 850 coins to reach 850 and we will require 150 coins to fix it. So we end up with 0 coins. However if the faulty voltage is anything above 850, we will not be able to get the answer.
So if you notice, we lose a lot of money when sequentially traveling. Instead of iterating one by one, let us iterate in steps of 2.
Now assume faulty voltage is 1000. When we reach 1000, we would have only spent 500. And to fix it, we would require another 150. Total spent - 500 + 150 = 650 which is well within our total amount we have initially.
Example, assume N is 1000 and c is 150 and the minimum faulty voltage is 6
First we start with 1. The program outputs 0. We now go to 3. We are good to go. Now we go to 5. We can move forward to 7. Now the program outputs 1. Which means we are at a faulty voltage. Now, we can be sure that the minimum faulty voltage is either 7 or 6. So to verify we go back to 6. And the program outputs 1. So we know 6 is the minimum faulty voltage. If we got 0 as the output, then we know 7 is the answer. However for this case, 6 is the answer.
So can we design an equation based on this?
The number of jumps we make is : (N / x) where x is the jump size. In the example, x is 2.
Once we find an error we know minimum faulty voltage is in the last x - 1 values.
Also, we will encounter a faulty value twice in the worst case
So equation becomes :
\frac{N}{x} \dotplus x \dotplus 2 \times c\leq 1000
For the first subtask, N <= 1000 and c <= 150
\frac{1000}{x} \dotplus x \dotplus 2 \times 150 \leq 1000
This can be reduced to a quadratic equation : x^{2} - 700\ast x \dotplus 1000 \leq 0
We get the range : [1.4314, 698.56]
So we can take x as any value in this range.
Now let us take the original constraints of the problem
N <= 150000 and c <= 150
\frac{150000}{x} \dotplus x \dotplus 2 \times 150 \leq 1000
If you try to solve the equation, you will get no real roots. To deal with this, I made a small optimization. I thought after finding a faulty voltage, instead of iterating last x - 1 values one by one, why not iterate in steps of 2.
Now the equation reduces to :
\frac{150000}{x} \dotplus \frac{x}{2} \dotplus 3 \times 150 \leq 1000
It becomes x / 2 because we are not traversing last x - 1 from first faulty voltage sequentially anymore. Instead in steps of 2. And also now in the worst case we may break our machine three times. (Why?)
Now we get a quadratic equation : x^{2} - 1100\ast x \dotplus 300000 \leq 0
If we solve this, we get the range [500, 600]
My solution in c++ : CodeChef: Practical coding for everyone
This is my first time writing an editorial. Let me know if there’s an error or if you have any queries and I’ll be happy to help you out.