PROBLEM LINK:
Author: Sergey Kulik
Tester: Pushkar Mishra
Editorialist: Florin Chirica
DIFFICULTY
Challenge
PROBLEM
You’re given a board and some pieces of irregular sizes and forms. You need to place them such as you cover as much as possible from the board.
EXPLANATION
This is a challenge problem, so no optimal solution is known. Instead, we need to find strategies to optimize the answer. We’ll focus on simple strategies now.
Choosing the order of the pieces
A first idea is to choose in which order we’ll add the pieces into the table. One obvious strategy is to use greedy - add firstly the largest pieces. The reasoning is simple: if we add “big” pieces, they’ll cover as much as possible from the table. There is a problem here - adding a big piece may block other small pieces to be added. From here we get our second greedy ordering - add from the smallest to the biggest one. Another option is to use our luck - simply use a random order (or start from one of the greedy strategies and do a fixed number of swaps). We can try a combination of all these methods.
Given an ordering, how to place the pieces?
Ok, so we fixed our ordering. How to add the pieces to the table? There are multiple possibilities here - too. Let’s use greedy and add to leftmost cell possible (with minimal row, if we have a draw choose the one with minimal column). This should ensure we use as little space as possible. Another strategy is to add random on the board. Other possible thing is to try somehow to make compact blocks (having forms of rectangles). Finally, we can even try a form of backtracking combined with the given heuristics.
What did you do? How do you combine all the possible approaches into a working solution?