Codeforces Round 963 Discussion stream (with hints)

Sum of odd and even is odd. So we will have to remove even nos if array does not contain same parity in starting.

Most of the times we should do this type of operation - Pick maximum odd no and minimum even no and do the operation.

If you cannot do the above operation pick maximum odd no and maximum even no and do the operation. Now, you can always do the previous mentioned operation.

For any time $t \ge \max(a_i)$, the set of lights on at time $t$ is same as set of lights that are on at $t+2 \cdot K$

So, the answer is always between $\max(a_i)$ and $2 \cdot K+\max(a_i)$, if it exists. Because the pattern keeps repeating.

We can also find find the length of final array, and we can also find how many of the remaining elements must be $\ge$ median.

Binary search FTW

Let $F(X)$ be the maximum count of no we can have in the final array that are $\ge X$. If we have this blackbox function, then we can binary search on the answer.

For calculating $F(X)$: If we create a new array $C$, where $C_i = 1$ if $A_i \ge X$, and $0$ otherwise. Our problem reduces to finding maximum sum of $C$, we can get.

Lets create one $K \times \left \lceil \frac{N}{K} \right \rceil$ matrix $M$, where $M_{ij} = C_{i \cdot K+j}$. On paths from $(0,0)$ to $(\frac{N}{K}, N%K)$, if we take only one element from each vertical column, the problem reduces to finding maximum sum of elements.

Solve for $N=1$

Notice, how are elements changing. $A=(3,2,5,6,4)$, XOR of all elements $=6$.

Apply operation on first column. This changes to $A=(6,2,5,6,4)$, XOR of all elements $=3$.

Apply operation on third column. This changes to $A=(6,2,3,6,4)$, XOR of all elements $=5$.

Notice this is just swapping one element with XOR as an extra variable, and so on.

So among these $M+1$ elements, which final $M$ elements to keep, we can obtain any order of these $M$ elements. One overkill approach to find minimum sum of absolute difference will by solving Travelling salesman problem

Now, you can do this independently for rows and columns. Decide which $N$ rows and $M$ columns to take among $N+1$ rows and $M+1$ columns. Then solve TSP, independently for rows and columns.

Rows and columns are independent. Let $cnt_i$ be the difference between no of $L$ and $R$, after first $i$ instructions. Now, can you find the necessary and sufficient conditions when robot will be at $X=0$ and $X=W$?

Robot will at $X=0$ when $cnt_i \equiv 0 \pmod{2 \cdot W}$. Robot will at $X=W$ when $cnt_i \equiv W \pmod{2 \cdot W}$.