How to solve SPOJ : SCALE using binary search?

Question

http://www.spoj.com/problems/SCALE/ I am trying to do it using recursion but getting TLE. The tags of the problem say BINARY SEARCH. How can one do it using binary search ? Thanx in advance.

Answer 1

First thing to notice here is that if you had two weights of each size instead of one, then the problem would be quite trivial, as we we would only need to represent X in its base 3 representation and take corresponding number of weights. For, example if X=21 then we could take two times P_3 and one time P_2, and put those into another scale.

Now let's try to make something similar using the fact that we can add to both scales (including the one where X is placed):

1. Assume that X <= P_1+P_2+...+P_n, that would mean that X <= P_n + (P_n-1)/2 (easy to understand why). Therefore, X + P_(n-1) + P_(n-2)+...+P_1 < 2*P_n.

(*) What that means is that if we add some of the weights from 1 to n-1 to same scale as X, then the number on that scale still does not have 2 in its n-th rightmost digit (either 0 or 1).

From now on assume that digit means a digit of a number in its base-3 representation (but it can temporarily become larger than 2 :P ). Now lets denote the total weight of first scale (where X is placed) as A=X and the other scale is B=0 and our goal is to make them equal (both A and B will change as we will make our progress) . Let's iterate through all digits of the A from smallest to largest (leftmost). If the current digit index is i and it:

1. Equals to 0 then just ignore and proceed further
2. Equals to 1 then we place weight P_i=3^(i-1) on scale B.
3. Equals to 2 then we add P_i=3^(i-1) to scale A. Note that it would result in the increase of the digit (i+1).
4. Equals to 3 (yes this case is possible, if both current and previous digit were 2) add 1 to digit at index i+1 and go further (no weights are added to any scale).

Due to (*) obviously the procedure will run correctly (as the last digit will be equal to 1 in A), as we will choose only one weight from the set and place them correctly, and obviously the numbers A and B will be equal after the procedure is complete.

2. Now second case X > P_1+P_2+...+P_n. Obviously we cannot balance even if we place all weights on the second scale.

This completes the proof and shows when it is possible and the way how to place the weights to both scales to equalise them.

EDIT:

C++ code which I successfully submitted on SPOJ just now https://ideone.com/tbB7Ve