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 MN squares. Also you are given an unlimited number of standard domino pieces of 21 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.
What is the optimal substructure for this greedy-algorithm solvable problem (Domino Piling)?
algorithms;greedy algorithms
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.