SURCHESS - Editorial

Problem Link :

Division 1

Division 2

Author : Evgeny Shulgin

Tester : Misha Chorniy

Editorialist : Anand Jaisingh

Pre-Requisites :

Rectangular Sums

Problem :

Not repeated here.

Explanation :

First of all, this problem should not really be very new for experienced participants. Most of the techniques required to solve this problem may be standard by now.

Let’s try and observe the structure of any good square. Looking at it, we can make the following observations :

  1. All rows in it with odd index have the same structure

  2. All rows in it with even index have the same structure.

  3. There are two possible options for odd rows, and the mask for even rows is exactly the inverse mask of the odd rows.

  4. Masks of type 1 are of the form 010101... and masks of type 2 are of the form 101010..., so mask1 is the inverse mask of mask2 and vice-versa.

Now, further in this problem, we are going to try and find for each cell (x,y), for each possible side length l, the minimum cost to make square (x-l,y-l),(x,y) a good square. Let the number of changes required be z. Then we can do something like ans[z]=max(ans[z],l), i.e we brute the maximum length square we can make in exactly z changes.

Later we can do something like ans[z]=max(ans[z],ans[z-1]) from left to right, i.e the maximum side square we can make in \le z changes. Then we can just output answers to queries in O(1). So, now let’s solve a sub-problem, i.e for each cell (x,y), for each possible side length l, find the minimum number of changes to make square (x-l,y-l),(x,y) a good square.

The minimum cost for a square is :

Sum of Hamming distance between mask of type 1 and all rows inside the square having odd index + Sum of Hamming distance between mask of type 2 and all rows inside the square having even index or vice -versa

For example, consider you want to make the following square a good square :

alt text

Then, there are two cases :

  1. For all rows with an arrow in front of them we sum the hamming distance between these rows and mask of type 1 + sum the hamming distance between rows that do not have arrows in front of them and mask of type 2

  2. For all rows with an arrow in front of them we sum the hamming distance between these rows and mask of type 2 + sum the hamming distance between rows that do not have arrows in front of them and mask of type 1

The minimum among the two is the answer we require.

So,to pass sub-task 1, we can fix the bottom left corner (x,y) and the side length L. This square has top left (x-L,y-L). Then we can find the minimum over both possible cases mentioned above by looping over all even and odd rows separately and summing the hamming distances.

The pseudo code for it would look something like :

for(int i=1;i <= n;i++)
{
    for(int j=1;j<=m;j++)
    {
         for(int len=1;len<=min(i,j);len++)
         {
            // now we find min cost for square (i-len,j-len),(i,j)
            // for all odd indexed rows try mask1 and for all even indexed rows try mask 2
           or vice versa
         }
    }
}

However, the above approach is not enough to pass sub-task 2. But guess what, we can just do some kind of pre-computation and maintain some prefix sums to avoid doing the same things again and again. Let odd1[i][j] denote the sum of hamming distances between mask 1 and all odd rows located in the rectangle with top left (1,1) and bottom right (i,j). Similarly we can construct tables even1[i][j], even2[i][j] and odd2[i][j].

For example, odd1(3,3) would store :

alt text

That is the hamming distance between mask of type 1 and odd rows of prefix of length 3 having row index \le 3

All these tables can be built in O(N \cdot M). Now, once we fix the bottom right and side length, it is possible to find the minimum cost required to transform this into a good square in O(1) operations. But how ?

We can use something called as rectangular sum queries, you can read about it here. We can use the above approach to query each of the matrices odd1,odd2,even1,even2. Now, the answer will be minimum over assigning mask 1 to odd rows and mask 2 to even rows, or vice versa, but now we just query these tables for sums in O(1), not loop again and again.

Reading the code to understand statements written above should be trivial now. That’s it .

Time Complexity : O(N \cdot M \cdot Min(N,M))

Tester’s Code : Link

My Code : Link

Weak TC - O${(n^2*m^2)}$ passes for this question.

Can you please explain this editorial by giving an example? The editorial is looking too abstract to understand.

Ok, please give me some time I’ll add a nice image for better explanation

1 Like

please don’t forget. I am waiting for it.

I used just one 2D array of prefix sums prefix[i][j] that shows how many cells need to be inverted to have a (rectangular) chess board from (1,1) to (i,j) with cell (1,1) having ‘0’ (black) cell. It can be constructed in O(N*M) with something like this:

prefixes[i+1][j+1] = prefixes[i][j+1] + prefixes[i+1][j] - prefixes[i][j] + ((i+j)&1 ^ board[i][j])

Then for each square size L and for each top left point (i,j) we can calculate the minimum number of cells to invert as

changes = prefixes[i+L][j+L] - prefixes[i+L][j] - prefixes[i][j+L] + prefixes[i][j]
changes = min(changes, L*L - changes)

At the same time we can track the minimum number of changes for each L. Finally the results can be stored as a mapping from the minimum number of inverted cells to the maximum size of the correct sub-board. For example, the map below means that no flips are needed to get a correct sub-board of size 6, 1 cell should be flipped to get a correct sub-board of size 7, 3 cells need to be flipped to get a correct sub-board of size 9 (and 8 as well), and so on. Then answering queries becomes just a binary search.

{0: 6, 1: 7, 3: 9, 5: 10}
1 Like

updated, is it better ?

Thanks @anand20 It is better. One last thing please tell the meaning of “sum of hamming distance” ?

It’s like the number of positions the strings differ in.

For example :

101 and 111 differ in 1 position, i.e. the 2nd position