jha_rishi's blog

Binary Search Solution Needed !!!
By jha_rishi, history, 3 years ago, In English

Problem Link : Obtain Two Zeroes

The editorial have very nice solution But what if we have to print X for every operation and also minimum number of operation is intended. Then According to me Binary Search based solution worked here.

And One more thing as this Problem is tagged as Binary Search problem so it made me more curious.

Please help me to write Binary search based solution.

  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
3 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I don't see why you would need binary search to get optimal solution. My aproach is:

First asuming that a<b (a==b is a simple case, apply op1(a/3) and op2(2*a/3)), you know that applying operation 1 with value b-a will get you to a-(b-a), b-2*(b-a) = 2a-b, 2a-b. This is again solveable in 2 operations so for a pair of distinct numbers, you can get 3 operations.

But notice that the operations can be combined. First, assume that you apply op1(x) and then op1(y). This changes a, b to a-x-y, b-2x-2y = a-(x+y), b-2*(x+y). But that is the same result we would have gotten by doing op1(x+y). So in the worst case, you should only need 2 operations: one of the first type, one of the second. To solve this you can just get the 3 values and combine them into 2.

One final notice is that in the case when 2*a==b or 2*b==a you have a solution in one operation.

→ Reply