SRM 383, D1, 500-Pointer (FloorBoards)

James S. Plank

• Problem Statement.
• A main() with the examples compiled in.
• A skeleton that compiles with main.cpp.

• Problem Given in Topcoder: December, 2007
• Competitors who opened the problem: 469
• Competitors who submitted a solution: 244
• Number of correct solutions: 117
• Accuracy (percentage correct vs those who opened): 24.9%
• Accuracy (percentage correct vs those who submitted): 48.0%
• Average Correct Time: 30 minutes, 55 seconds.

The strategy here is not obvious, so I'll help you out. Since room.size() and room[i].size() are capped at 10, you should be thinking "enumeration." You should also think "sentinel". The first thing that I did was sentinelize room so that the first line was all #'s, and the remaining lines end with a '#'. Now, you could try to enumerate all possible flooring configurations. That would be 2ⁿ where n is equal to the total number of "."'s in room. Which means it could be as bad as 2¹⁰⁰. That won't do. However, you can instead work row-by-row, and at each step you enumerate all possible flooring combinations for just that row. That's only 2¹⁰ combinations per row, which is very doable. Here's how it works:

At each step, I work on room[r] for r going from 1 to room.size()-1. For that step, I maintain four vectors:

• last_boards is a vector of all possible configurations of row r-1. For example, if for r-1 is "#..#", there are four possible configurations:

   { "#||#", "#|-#", "#-|#", "#--#" }
  

• current_boards is a vector of all possible configurations of row r.
• last_nplanks is a vector of the same size as last_boards. last_nplanks[i] contains the minimum number of boards that are required to floor a room containing just the first r-1 rows of room, whose row r-1 is equal to last_boards[i].
• current_nplanks is a vector of the same size as current_boards. current_nplanks[i] contains the minimum number of boards that are required to floor a room containing just the first r rows of room, whose row r is equal to current_boards[i].

Obviously, at the end of each step, you'll simply copy current_boards to last_boards and current_nplanks to last_nplanks. Since you've sentinelized room so so that room[0] has all #'s, on the first pass, last_board contains one element: room[0], and last_nplanks contains only the integer 0, because ther are no ways to floor that row.

Now, at each pass, you should create current_boards by enumeration. A simple recursive procedure will do it. After creating current_boards, you create current_nplanks. For each board current_boards[i], you run through every last_boards[j] and calculate how many boards will be required to floor when the last two rows are current_boards[i] and last_boards[j]. Take the minimum value of these and that will be current_nplanks[i].

When you're done, the minimum value in current_nplanks will be the value of the optimum flooring.

##|
--|
##|

In the table below, I include the value of the four vectors at each pass of the algorithm. I've sentinelized room.

To help, focus on when r equals 2 and current_board[i] is equal to "|||". You check both elements of last_boards. The first, last_boards[0], equals "##|#" and can be floored with one board. If you floor the next row of room with "|||#", then it will require two more boards, since the one in the last column will be attached to the board in the row above. That's a total of 3 boards. When you look at last_boards[1], it equals "##-#", and if you floor the next row of room with "|||#", it will require three extra boards, for a total of four. Thus, the entry of current_nplanks that corresponds to "|||#" will have a value of 3 (the minimum of 3 and 4).