How to approach this question

#1

firstly i thought that lets find the largest rectangle of # but it will not work out . so any hint how to approach this ?

#2

Let’s solve the problem for rectangle W×H (W≥H). Of course, we can cover all rectangle with itself for cost W. To get something smaller than W we have to leave at least one column uncovered — otherwise we pay at least sum of w over all rectangles which is at least W. This gives us an idea to use DP on rectangles to solve the problem: dp[x1][x2][y1][y2] is minimal cost to cover the rectangle [x1;x2)×[y1;y2). It is initialized by max(x2−x1,y2−y1), and we have to try not to cover every column/row. Of course, we have to check if it is all white from the beginning; to do that we will precalculate 2D prefix sums. Total complexity is O(n^5).

#3

. . . .
. # # .
. # # .
. . . #

Can we dry run something on this example ? Although above explanation looks really helpful but i couldn’t cope up with the statements

#4

@aryan_007 the answer for this will be 3
You can think of this like breaking the rectangle in smaller rectangles
And when the rectangle consists of only black cells then return count of cells
Else keep on dividing the rectangle

look at this dp solution which uses 4d DP if you want, i guess you will understand solution by looking at that code.

#5

okayyy , thankyou so much !!!

#6

@aryan_007
please mark your doubt as resolved and rate as well :slight_smile:

#7

just a doubt what actually bx,dx,ex mean in this solution . and same for y