can you provide me with some approach on how to go ahead with this problem as i am unable to think the initial step on this
Not able to think of the approach
should i go with the approach of thinking about all the cuts in the grid and then calculating the cost of the subgrids formed through that grids ?? i think that could work
Hey @Shobhit_kumar
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(n5).
N is upto 50 .
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
Check this only if required :
yes sir i got the approach but the code is not giving right answer for all the test cases… i.e some of the test cases are failing here.
Hey @Shobhit_kumar
sorry the code I shared earlier is only for the case when only 1 operation is allowed ,and we haven’t applied DP in it .
Here check this one
sir can you plz explain me this line again as i am unable to grasp that why we need to leave one column as if we leave it there might be some black shapes…plz clarify thisTo 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.
how can i share an image with you??
D[bx][by][ex][ey] = min(D[bx][by][ex][ey], D[bx][by][i][ey] + D[i + 1][by][ex][ey]); in this step when you do D[i+1] you are skipping one row or column but why??
Hey @Shobhit_kumar
So what its saying is assume we take a
HXW rectangle i.e with H rows and W cols such that W >= H
Now ans for it could be W at max
or we can reduce its cols and find for smaller rectangles
yes definitely we can reduce the size and find ans for smaller rectangles but the rectangles which i am dividing into and finding answers for is not contiguous right?? as we have left one column unused in the middle to two rectangles…
No we are not skipping anything in between if first rectangle ends at ith then next stars at i+1 right
okay right got it so in short we are making every possible cut in the rectangle and then checking for the min answer right??
yes correct…
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.