This is a repo of my solution to Grid Compression Contest held by Algotester and sponsored by Huawei
Here are the task, the final scoreboard and my 1st place certificate.
The build system is CMake so just run it. If you're not familiar with CMake try reading some docs.
In order to send your solution to Algotester you have to have a single a file. Here is how you can get it: sh bootstrap.sh
The general idea is to convert the grid into an undirected graph and find a MIS in it.
The graph's vertices is the set of rectangles and the edges is the set of pairs of intersecting rectangles. The conversion from grid to graph can be found here
The idea behind finding MIS is the same as in this paper:
- Generate random starting solution
- Improve it with
(1,2)-swaps and plateau search
My contribution is the observation that for grids with(1,x)or(x,1)rectangles (1<=x<=10)(1,2)-swaps without plateau search always give better results faster.
- Use reductions akin to OnlineMIS (the implementation)
- Find a better plateau search routine