algorithm
@gleb: a2[0] is the largest of a2
For your example
a1 = [7, 5] a2 = [2, 0]
b1 = [6, 4] b2 = [3, 2]
since a2[0] < b2[0] so a2 is in the lower 4, b1 is in the higher 4 that left if a1 and b2
a11 = 7 a12 = 5
b21 = 3 b22 = 2
Now we compare a12 and b22, b22[0] < a12[0] so b22 in the lower 2 left. The last one of lower 2 is decided between b21 and a21.
So we need total 3 weight to find the 4 lower number which is a2, b22, b21: [2, 0, 2, 3]
Sound like 2012 is the year of the test. By anyway first try with simple equivalent one and generalize latter.
- LinhHA05 July 31, 2013Let assume that you have 2^n = 32 weight, they are divide in to 2 group and then ordered. The question is how can you extract the small 16 weights.
Call them a, b group
Divide each group to 8 and 8 weight : a1 > a2, and b1 > b2
- 1st: Weight a2[0] and b2[0]. if a2[0] > b2[0] then a1, b1 > b2 so b2 is in the 16 less group, other wise a2 is in the 16 less. Now we have identified 8 of 16 lower and 8 of the upper 16 is a1 in the first case and b1 in the second
- 2rd. Without losing the generality assume a2[0] < b2[0]. What we have left is a1, b2.
Divide a1 by 2: a11 > a12. Divide b2 by 2: b21 > b22. Repeat the first step again to extract 4 of the lower 8
- Repeat the process we then identify 4, 2, 1 weight for the total of 15 after 4 weighting. If we need 16 then one extra weight will require for a total of log (2^n) = 5 weighting.
Now you see the answer for your question