no one has been able to solve this problem and the editorial is not clear. could anyone please give a better explanation. i.e what is the state of the dp ? and how to move from one state to another ?
problem name : "therectangularcitydiv1" problem link: https://community.topcoder.com/stat?c=problem_statement&pm=14901&rd=17158
editorial: https://www.topcoder.com/blog/single-round-match-734-editorials/
We go from left to right (column by column). The state of dp should remember everything that is important so far. It's enough to store the last column and the information how cells from the last column are connected. For example, if cells so far form the rotated U-shape, then we should remember that the first and the last cell in the last column is on, and that they are connected. It isn't important how exactly the cells on the left looked like.
The red arrow shows the last column.
but after finishing with the last column how do i know if all the open houses are visited and given a profile configuration how do i move to the next ?
You consider every possible "shape" of the next column (there is also a technique to add cell by cell, but that's harder). Shape meaning the info from where we enter every cell and how we exit every cell. In other problems we should usually consider every cell being visited or not, while here all open-houses-cells must be visited/used.