ICL1906-EDITORIAL

PROBLEM LINK: https://www.codechef.com/ICL2019/problems/ICL1906

DIFFICULTY: EASY

PROBLEM
There are D and H planets in two galaxies respectively.You have two guns. The first gun, in one move, subtracts 1 from both D and H whereas the second gun, in one move, doubles any one of them. Find the minimum moves to reduce both D and H to zero. Else output -1.

EXPLANATION
If either one of D and H is zero while the other is non-zero, the answer is straight away -1 because we cannot perform either operation.

If both D and H are non-zero,

Let A = min (D, H) and B = max (D, H)

First, by observation, we may say that we need at least B decrements in any valid solution.

Next, through any solution, the gap between A and B has to be reduced to 0 i.e. A-B has to be made zero. For this, A must be multiplied by 2.

Consider the following two sequence of operations.
(A,B)-1 (A-1,B-1) *2 (2*A-2 , B-1)
(A,B) *2 (2*A , B) -1 (2*A -1 , B-1)

Therefore, by observation, decrementing after magnifying reduces the gap in a better way than magnifying after decrementing. Thus,we can deduce that we will need at least k magnifications such that A*2^k>=B.

A proposed solution is:-

  • Double A till you get B > A >= B/2.
  • Decrease A, B until B = 2*A. It is guaranteed that such a situation will be achieved(Try proving it!).
  • Double A.
  • Decrease A, B till it becomes 0,0.

Since this solution contains exactly k magnifications and B decrements, we may conclude it is optimal.