Hints : Add, Divide and Floor
Solve for 2 elements first.
What is the answer for
1
2
3 5
2
4 6
2
3 4
2
4 5
Note that if
a < b, then (a + x) < (b + x). Hence, adding a large x is useless, since if these elements meet, they’ll meet at some point less than a. Hence, we only have to look at a small subset for possible values of x. What are those?
An optimal configuration can be reached using only
0 and 1 as possible values of x. Why?
Suppose, you use x = 2 instead. Then, (a + x)//2 = 1 + a//2 and (b + x)//2 = 1 + b//2. Hence, we could’ve as well used x = 0, since we don’t want to increase the numbers unecessarily.
Suppose, you use x = 3 instead. Then, (a + x)//2 = 1 + (a + 1)//2, and (b + x)//2 = 1 + (b + 1)//2. Hence, we could’ve as well used x = 1, since we don’t want to increase the numbers unecessarily.
So, now we know that x = 0 and x = 1 suffices when dealing with 2 elements. Is it possible to simulate the entire operation. Why?
A simulation works because at each operation
a[i] is reduced by a factor of 2, meaning it’d reach 1 or 0 in around log(a[i]) steps. We just need to figure out when to use x = 0 and when to use x = 1.
Assume a < b.
Consider the case
a = odd
b = odd
// Example (3, 5)
- If you add zero, it goes to
[1, 2] - If you add one, it goes to
[2, 3] - Hence, pick
x = 0
a = even
b = even
// Example (4, 6)
- If you add zero, it goes to
[2, 3] - If you add one, it goes to
[2, 3] - Hence, pick
x = 0
a = odd
b = even
// Example (3, 4)
- If you add zero, it goes to
[1, 2] - If you add one, it goes to
[2, 2] - Hence, pick
x = 1
a = even
b = odd
// Example (4, 5)
- If you add zero, it goes to
[2, 2] - If you add one, it goes to
[2, 3] - Hence, pick
x = 0
So, we’ve solved the problem for 2 elements. How do we solve for n elements?