On Codeforces, the first problem that comes up for the tag "greedy" is "50A: Domino Piling". Here is the problem:

You are given a rectangular board of M × N squares. Also you are given an unlimited number of standard domino pieces of 2 × 1 squares. You are allowed to rotate the pieces. Find the maximum number of dominoes you can place on the board so that each domino covers exactly 2 squares and no dominoes overlap.

I solved it quite easily: the solution is just floor(M*N/2).

I read that in order for a problem to be solved Greedily, it needs to have "optimal substructures". For this problem, what were the "optimal substructures"?

Thank you in advance.


1 Answer 1


I think there's a slight misunderstanding in the question. The phrase is "optimal substructure", not "optimal substructures". It's not a matter of looking at the individual substructures (e.g., regions of the grid you're trying to tile) and saying, "This one's optimal", "This one's optimal", "This one isn't". Rather, it's a matter of looking at the structure and interactions of the subproblems and saying, "The substructures of this problem (i.e., the subproblems) interact in a way that lets me find an optimal solution easily."

I also don't think this is a great example for greedy algorithms, since greedy algorithms are naturally somewhat recursive and it's so easy to domino-tile a grid iteratively that it feels artificial to force it into a recursive solution. But here goes...

One example of optimal substructure is that, if you can divide your grid into rectangles $A$ and $B$ and you can perfectly tile $A$, then an optimal tiling of the whole grid can be made from the perfect tiling of $A$ along with an optimal tiling of $B$. This gives the following greedy algorithm.

function tile (int width, int height, int startrow)
if (startrow <= height-1)
    perfectly tile rows startrow and startrow+1 like this | | ... |
    tile (width, height, startrow+2)
else if (startrow == height) then
    tile the last row like this -- -- ... -- , with one empty square
    at the end if width is odd
/* else startrow > height and there's nothing to do */

Note that this just produces tilings like this one for a $7\times3$ grid,

| | | | | | |
| | | | | | |
--- --- ---

which is exactly what you'd do iteratively.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.