Click here to Skip to main content
15,867,686 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
Hello there everyone

I am new to dynamic programming, and I would really appreciate if someone can help me on how I can approach the following problem in hacker rank:

you can see the problem description down below
Screenshot-4 — ImgBB[^]


Right now, I am thinking of using bottom up 2D tabulation. However I am not sure about what the dimensions will represent and how I will fill in the table.

What I have tried:

Demonstration image:
Screenshot-5 — ImgBB[^]
Let rows and columns represent row and column locations in the field. Let the cells in the table store the maximum rectangle size ending at that cell.
(1,1) = 4 maximum size rectangle so far is 4
(1,2) = 6 maximum size rectangle to the left was 4, now it is 6
(1,3) = 8 maximum size rectangle to the left was 6, now it is 8
(1,4) = 10 maximum size rectangle to the left was 8, now it is 10
(2,1) = 6 maximum size rectangle to the up was 4, now including this is 6
(2,2) = 6 maximum size rectangle to the up was 6, now including this is 8
The (2,2) in this case is incorrect. Because it should have been 6. The reason why it is incorrect is because the cell above (1,2) was storing the maximum size of a rectangle that goes from (1,1) till (1,2)
Posted
Updated 27-Dec-22 22:12pm
v2
Comments
Richard MacCutchan 27-Dec-22 7:46am    
Please use the Improve question link above, and add complete details of what is not working. Please ensure all the relevant information is in the question, rather than at other websites.
[no name] 27-Dec-22 11:44am    
I'd go from the largest case (4x4) to the smallest (2x2), and all the ones in between (which isn't a lot) and fit them. If there's an x on an edge, it didn't fit.

You can vary the size of the rectangle you're trying to fit, while varying the top, left coordinate and offsetting the rectangles row and columns into the "field". That's what's "dynamic" about it.

1 solution

1. I think you have slightly misread the question. It asks for the length of the fence, not the perimeter of that fence. A fence that goes from (1,1) to (2,2) would have length 4 (one in each of (1,1), (1,2), (2,2) and (2, 1).

2. Break the problem down into multiple steps. As a first step I stored the length of fence you can build to the right and down from each position. For screenshot 4 this gives:

2d3r 3d2r 0d1r 3d0r
1d1r 2d0r 0d0r 2d0r
0d1r 1d0r 0d0r 1d0r
0d0r 0d2r 0d1r 0d0r

This table can then be used to fit fences. For example at position (1,1) you can try building a fence 3 across to (4,1) you then check the downs on (1,1) and (4,1) to see if there is anywhere you can complete a rectangle. (you can not, because you are blocked by the down on (1,1), the across on (1,3) and the across on (1,2).
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900