geekinprogress's blog

By geekinprogress, history, 4 weeks ago, In English,

hello codeforces!!

i had been struggling with THIS problem and i had found recursion for this on here . but i am not able to understand how to get that recursion with myself and how to simply it; if anyone here can help me it would be too kind and helpful for me ... thanks in advanced..

 
 
 
 
  • Vote: I like it  
  • +7
  • Vote: I do not like it  

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

please help ... it would be kind..

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Since the height of the corridor is five, the problem can be solved with a bitmask DP, where you would have as your states your current coordinate and the bitmask for the current column and the next column. You should traverse the corridor in the following manner: Place tatami at position (i, j) (if you haven't placed one beforehand) and then go to (i + 1, j). If i = 5, it means you have already completed that column and should proceed to (0, j + 1).

The bitmask would store which of the squares have already been occupied by tatamis. If your current square has already been occupied by a tatami, skip it. Otherwise, there are two ways to place it: Horizontally, occupying spots (i, j) and (i, j + 1) or Vertically, occupying (i, j) and (i + 1, j).

Say bits in positions [0, 4] will reference the current column and [5, 9] the next column. If you place a tatami horizontally, you should activate bits i and i + 5 to represent that those positions have been occupied. If you place it vertically, activate bits i and i + 1. Once your i coordinate has reached 5, the first 5 bits of the bitmask will no longer be relevant, since these such bits are a reference to the column that you have already passed by. In that case, you can do mask >>= 5 to shift the bits from [5, 9] to [0, 4].