Codeforces Round #724 Omkar and Medians Solution (Java/C++)

Solution:

First, we can find that: for b[i+1], compare to b[i], actually, we add two number to a: a[2i+1] and a[2i]. So, the impact to the median is limited to 1 position.
For example, [1,3,5,7,9], the median is 5. After added two numbers, at most move left or move right 1 step.

If b[i+1]==b[i], then just add any one number on the left, and add any another one number on the right.

Consider b[i+1]>b[i]. Then our task is move to median one step right. So, let us consider the x which is the first one bigger than b[i] currently.
If b[i+1]>x, then no way. whatever we do, the next median at most be the x. So, no solution.
If b[i+1]==x, then it is nice. So, we can just add any number on both sides.
If b[i+1]<x, which mean b[i]<b[i+1]<x. Then we know b[i+1] not in the array a. So, we can add b[i+1], and add a number which is bigger than b[i+1].

Now, we found that, it does not matter which number we add, except b[i+1]. Because for the two cases which have solution, the difference is b[i+1] already in the array a or not. And because each time only can move one step from b[i]. So, the number can be any big number.

b[i+1]<b[i] is same thing.

Code:

Java

C++