Contest starts in ~25min.

My thoughts on Grid Path (Hard):

Let $$$\text{cost}(i, j)$$$ denote the cost of moving the first $$$j$$$ (or the last $$$j$$$) '1's in the $$$i$$$-th row to valid positions.

We observe that:

• $$$\text{cost}(1, j+1) - \text{cost}(1, j)$$$ is non-decreasing, and
• $$$\text{cost}(2, j+1) - \text{cost}(2, j)$$$ is non-increasing.

This implies that the total cost function is convex.

I used a Fenwick Tree combined with binary search to maintain it, and applied ternary search to find the optimal answer.

Unfortunately, I didn't handle the edge cases properly. And the complexity of $$$O(q \log^3 n)$$$ only passes the first 7 test cases. I believe that direct binary search in data structure can be $$$O(q \log^2 n)$$$.

is there any greedy solution for coloured array ?

I really like the way problems are described.. No nonsense and stories and to the point.. Nice problems..