**Video editorial**

**Hint 1**

Sum of odd and even is odd.

So we will have to remove even nos if array does not contain same parity in starting.

**Hint 2**

Most of the times we should do this type of operation -

Pick maximum odd no and minimum even no and do the operation.

**Hint 3**

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.

**Video editorial**

**Hint 1**

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*K$$$

**Hint 2**

So, the answer is always between $$$max(a_i)$$$ and $$$2*K+max(a_i)$$$, if it exists.

Because the pattern keeps repeating.

**Video editorial**

**Hint 1**

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.

**Hint 2**

**Hint 3**

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.

**Hint 4**

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.

**Hint 5**

Lets create one $$$K* \left \lceil \frac{N}{K} \right \rceil$$$, matrix $$$M$$$, where $$$M_{ij} = C_{i*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.

**Video editorial**

**Hint 1**

Solve for $$$N=1$$$

**Hint 2**

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.....

**Hint 3**

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

**Hint 4**

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.

**Video editorial**

1993F1 - Dyn-scripted Robot (Easy Version)

**Hint 1**

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$$$?

**Hint 2**

Robot will at $$$X=0$$$ when $$$cnt_{i} \equiv 0 \mod 2*W$$$.

Robot will at $$$X=W$$$ when $$$cnt_{i} \equiv W \mod 2*W$$$.

**Video editorial**