PROBLEM LINK: CodeChef: Practical coding for everyone
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.