SRM 451 - BrickPuzzle - Part 1

Remember that time I said that I would be making editorials for topcoder problems that lack official editorials? Remember how I stopped doing that after the first such time I did that?

Here is another problem I made for TopCoder that does not have an official editorial. It is a div 1 1000 (oooh).

BrickPuzzle
Link to problem statement

So you have infinitely many tetraominoes of the following shapes:


We want to place them in a grid with black and white squares in such a way that all white squares are covered by a tetraomino. Black squares do not necessarily have to be covered but can be covered if you need to. Tetraominoes you place must be aligned to the grid, cannot overlap and must lie completely inside the grid. You cannot rotate the tetraominoes , so they must be placed in the same way as the figure. Use as few tetraominoes as possible.



The maximum dimensions for the grid are 22x22. If it is impossible, return -1.


The backstory
You know what? Writing problems for Topcoder is difficult. Do not get me wrong, I am not saying that it is very hard. I am saying that it is horribly hard and makes your head melt. Right now I am still trying to think of problems that I needed to think of exactly the moment after the last SRM I wrote ended.

Sometimes I think of a problem I find in real life and try to turn it into TopCoder juicem this is the honest way to do it and is rarely useful. The dishonest way is to first think of a cool idea for a solution to a problem and then find some sort of problem that fits that idea of a solution.

What happened here is that I figured, that bitmask dp and similar are based on encoding a number as a bit mask and then using that number as a key. The idea was , why not think of a problem that does the same but instead of bitmasks, uses another number format?

The result was the problem that eventually became FourBlocks. An easy typical dp problem with the twist that the dimensions (22x22) do not allow the typical bitmask dp approach. For some reason I thought that was a good idea for a division 1 medium. When I showed this problem to Ivan Metelsky, he said that I should change the maximum dimension to 10x10 (Yes, really). He predicted (quite correctly) that even with 10x10 it would be a problem difficult enough for division 1 500, because a lot of people would be lame enough to use a greedy solution even though the constraints make it very easy to use dynamic programming.

I still wanted to use my original idea, so I saved it up for later. I figured that if I instead of using it in a typical problem, I used it in a less typical setting and included further implementation complications, it would actually be a div1 hard (Division 1 hards are to me the holy grail of problem setting, because they are impossible to think of, and once you have one, thinking of the rest of the SRM is not very hard, so you can ensure to take 500 dollars home).

Thus in the next SRM, I used BrickPuzzle. It turned out to be very difficult. I mean, nobody solved it. As such it is a failure. Every problem that does not get solved during a match is a failure. It still makes an interesting topic. I really love this problem and consider it a homage to dynamic programming. I also think that if you learn this problem you will finally understand the cons and pros of iterative dynamic programming and recursion + memoization.


This finishes part 1. In the next part I will hopefully write an editorial. I plan that part to be finished tomorrow.