NCOPRIMEN - Editorial

editorial
, , ,
24

There is a simpler algorithm for this problem.

For every set of 3 consecutive elements, replace the first and third with double of the middle one. Resulting array will have adjacent elements with GCD of 2.

We will meet both the constraints of the problem. We will not replace more than 2/3rd of the elements (since this number is rounded up in the problem statement) and no element in the new array will exceed 1e6 since we are multiplying it by 2.

25

3
99997 6 99997
try this case element will increase constraint
doing twice of a number(<=10^5) doesn’t guarantee it would be less than 10^6
test cases would be fine for it but problem statement should be much better