Unable to get the idea of the question

#1

I am unable to get the idea behind the hint video and also it is very confusing at the same time. plz provide me with some hints based on it

#2

hello @Shobhit_kumar
whats the name of video that u r talking.

#3

it is the hint video of square painting problem

#4

this problem i am finding very difficult to deal with plz help on this

#5

have u understood the brute force?

#6

brute force approach is put eraser at each cell (i,j) and check number of white rows after it .
total n^2 cell possible and it will take O(n^2) to count number of white rows
due which overall time complexity will be O(n^4) .

now we need to optimise it .
how ?
if u see if we place eraser at cell (i,j) then rows that get affected are [i…i+k-1]. rest other rows are remain as it is. ie rows [0…i-1] and [i+k…n-1] will remain as it is.
so here we can save our time by precomputing already white rows by maintaining prefix array and suffix array .
where prefix[i] will store number of white row among [0…i] rows
suffix[i] will store number of while row among [i…n-1] rows.

now try to watch the hint video again , it will make some sense

#7

but the video only talks about white rows but we need to take care of white columns also as mentioned in the question

#8

yeah becuase procedure will be same for column as well.

refer this->
Let’s consider a single row that contains at least one black cell. If the first appearance of a black cell is at the l-th column and the last appearance of a black cell is at the r-th column, we can determine whether it becomes a white line when a certain cell (i,j) is clicked in O(1), after some preprocessing. It becomes a white line if and only if a cell (i,j) is clicked where the row is at [i,i+k−1] and j≤l≤r≤j+k−1. We just need to compute ll and rr in advance.

Now let’s consider all n rows (not columns). First, count all rows that are already white lines before clicking. Then we count the number of white rows when the cell (1,1) is clicked, by applying the above method to all rows from 1 to k. Ignore the already-white rows that we counted before. So far we obtained the number of white rows when the cell (1,1) is clicked. From now, we slide the window. Add the k+1-st row and remove the 1-st row by applying the same method to them, and we obtain the number of white rows when the cell (2,1) is clicked. We can repeat this until we calculate all n−k+1 cases for clicking the cells at the 1-st column. Then we repeat the whole process for all n−k+1 columns.

The same process can be done for counting white columns, too. Now we know the number of white rows and white columns when each cell is clicked, so we can find the maximum value among their sums.

#9

sir i have tried this question alot now can you plz provide me with the code of this to get a better understanding… of this plz…

#10

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.