You are not logged in. Please login at www.codechef.com to post your questions!

×

MAXEP EDITORIAL (Unofficial)

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++ : https://www.codechef.com/viewsolution/21800555

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.

asked 18 Dec '18, 02:17

lax_99's gravatar image

3★lax_99
11
accept rate: 0%

edited 18 Dec '18, 15:20


Can you tell me the error in my code? I am not getting which test cases I am missing. My solution

link

answered 18 Dec '18, 16:08

shobhit907's gravatar image

3★shobhit907
1
accept rate: 0%

1 thing you should do better is you don't need to fix the bulb after it breaks for the last time so your equation should have c instead of 2*c. This would make it feasible even for 2nd subtask.

link

answered 21 Dec '18, 10:28

praveenkumar12's gravatar image

5★praveenkumar12
29819
accept rate: 8%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×989
×376
×146
×68

question asked: 18 Dec '18, 02:17

question was seen: 753 times

last updated: 23 Dec '18, 15:54