CHPUZZLE - Editorial

Author: Sergey Kulik
Tester: Pushkar Mishra
Editorialist: Florin Chirica

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?

1 Like

Go from largest to smallest;

1. try the first something positions (break if you’ve tried 10^6 or something positions in this step over all pieces) for the top left cell of this block’s bounding box, use the first such position that keeps the solution valid
2. try 100 or so random positions for the top left cell, the rest is the same as before
3. ???
4. PROFIT!!!

Considering how trivial this strategy is, it gets a shitload of points. I just tried slowly increasing the limits in steps 1. and 2. and it got 77 points and 13th place in the end.

2 Likes