Expand description
§Christmas Tree Farm
There are 3 possibilities for each combination of region and presents.
§Best case
All presents fit into the region with no overlap. Each present has its own 3x3 space. For example:
AAABBBCCC
A....B.C.
AAABBBCCC§Worst case
The total number of tiles in the region is less than the total number of tiles in the presents, so even if the presents are packed to occupy 100% of the space, there is no possible way that they can fit. For example, the three shapes above contain 21 tiles, so they can never fit into the 6x3 region with 18 tiles below.
......
......
......§Mixed case
The presents can fit into the region with some clever arrangement. This problem is known as polyomino tiling and is NP-complete. This is an extremely complex and challenging problem with no known polynomial-time solution.
§Solution
For the inputs provided, all combinations of regions and presents fall into the first two cases (either trivially possible or impossible), so there is no need to even attempt the harder general case. Additionally, since each present is placed in its own 3x3 space, there is also no need to even consider the shape of the presents.