Hackerearth: June Easy’19 Solutions

Hi! Hackerearth had it's monthly rated competitive round on June 2, 2019. I could solve just 2 of em during the contest. I’ll keep updating this post as I upsolve the contest.

Problem: Mosiacs and holes

The editorial’s code is beautiful. Takes some time to understand it. I recommend that you have the solution code open on the side while reading on.

We maintain 2 arrays of size n x m a[][] and b[][]. a[][] is to store the actual state of the matrix. b[][] is used to determine whether the a[i][j] should be flipped or not.

• Row-Wise Traversal: We will be traversing row-wise and if we encounter a ‘0’ marked cell(current cell), we do the flip.
• Flip Operation: The k*k square will flip all the cells with its top-left corner coinciding with the current cell(i,j). So, we flip the current cell.
• Use State Matrix: Next, for all remaining cells that lie under the range(k*k), we update the matrix — b[][] by performing a flip operation. Lets say 0 means (no-flip), 1 means (flip). To flip a cell, we will set that cell to the other option. Now, when we continue the row-wise traversal in a[][], before checking the current cell’s current state, we will use b[i][j] and set the latest state of a[i][j]. This is why at every cell iteration in the solution, we have a[i][j] ^= b[i][j] first.

What is this creepy line a[i][j] ^= b[i][j] actually doing?
For b[i][j], 1 means FLIP, 0 means DON’T-FLIP.

However, there’s a catch. The current solution is likely to give us TLE.

When we perform the flip operation on k*k cells, do really need to update all k*k cells? Think about it. We are doing row-wise traversal, let's say k=10 and we update cell(i,j). This will cause cell(i, j+2) to flip(of course its just one of the cells that will be flipped). Now, continuing the row traversal, suppose that the very next element(adjacent right)turns out to be ‘0’ as well. We will again flip k*k cells starting from (i, j+1). This will reset the cell(i, j+2) to its state when we were at cell(i,j).

In order to reduce this redundancy, we update cells adjacent to the current cell(i,j) : (right, bottom and bottom-right). All other remaining cells will automatically get flipped when needed since we are using the state array b[][]. How? Everytime we arrive at a cell(i,j), we use b[i][j] to get the latest state of a[i][j]. Next, we add another operation: update the state matrix b[][] by transferring the current operation to the adjacent cells(right, bottom, bottom-right). Bingo! the state of all remaining k*k cells gets propagated(Segment Tree Lazy propagation thingy??) as we do row-traversal.

But what about the cells that were not part of the k*k range? By this logic, they are going to get flipped too. Yup.. so we simply add an extra flip to the 4 corners of the k*k range we flip every time. This will reset everything as the propagation reaches those cells.

Hope it helped.
Boiboi.