We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Now if you compare partitions of delta and delta' into {1, 2, 5} it's evident that delta' has one more 5 in each element di' so compared to number of ops in delta it requires n extra -5 operations. For that reason each of the cases min-5, min-6 etc are always less optimal than cases min, min-1, ... min-4.
Equal
You are viewing a single comment's thread. Return to all comments →
First find min {1 5 5}. In this case it's 1.
In general, you need to try the following targets: min, min-1, min-2, min-3 and min-4 and target >=0.
So in this particular case min=1 so we try only min and min-1.
Case 1: target is (1 1 1)
Find the delta between (1 5 5) and (1 1 1):
delta = (1 5 5) - (1 1 1) = (0 4 4)
In terms of {1, 2, 5} operations we can minimally partition (0 4 4) elements as follows:
0 = 0 * 5 + 0 * 2 + 0 * 1
4 = 0 * 5 + 2 * 2 + 0 * 1
4 = 0 * 5 + 2 * 2 + 0 * 1
Note that you get above partition as follows:
For some delta = (d0 d1 ... dn-1)
di = ai * 5 + bi * 2 + ci * 1
ai = di / 5
bi = (di % 5) / 2
ci = (((di % 5) % 2) / 1)
Now count the occurences of {1, 2, 5} in (0 4 4) partition and this is the min number of operations to reduce (1 5 5) -> (1 1 1):
min number of ops = (0 + 0 + 0) + (0 + 2 + 0) + (0 + 2 + 0) = 4
Case 2: target is (0 0 0)
Find the delta between (1 5 5) and (0 0 0):
delta = (1 5 5) - (0 0 0) = (1 5 5)
In terms of {1, 2, 5} operations we can minimally partition (1 5 5) elements as follows:
1 = 0 * 5 + 0 * 2 + 1 * 1
5 = 1 * 5 + 0 * 2 + 0 * 1
5 = 1 * 5 + 0 * 2 + 0 * 1
Now count the occurences of {1, 2, 5} in (1 5 5) partition and this is the min number of operations to reduce (1 5 5) -> (0 0 0):
min number of ops = (0 + 0 + 1) + (1 + 0 + 0) + (1 + 0 + 0) = 3
Case 1 requires 4 steps and case 2 requires 3 steps, so case 2 is optimal and min number of steps is 3.
Why do we not look min-5, min-6 etc? Suppose min-5 >=0 so (min-5 min-5 ... min-5) is a valid (non-negative elements) target.
delta' = (v0 - (min -5) ... vn-1 - (min -5)) = (v0 - min + 5 ... vn-1 - min + 5)
When we did (min ... min) target, delta was:
delta = (v0 - min ... vn-1 - min)
Now if you compare partitions of delta and delta' into {1, 2, 5} it's evident that delta' has one more 5 in each element di' so compared to number of ops in delta it requires n extra -5 operations. For that reason each of the cases min-5, min-6 etc are always less optimal than cases min, min-1, ... min-4.