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

what could be the rating of the problem ( Add 1 or 2 ) comparing with cf ?

Can anyone please drop the sudocode for problem add 1 or 2

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

loved the problem Grid Path (easy) :)