ok, I will try a simplified explanation of what I tried. I know it’s not a clear explanation neither a great solution (6th place in div1) but for sure it will be the best you can find in this forum while noone else post his/her own.
-
take N=M=30. Why not 30x33? It was suposed I was going to do that later but, as I said, I’m a lazy guy and didn’t.
-
for each one of the 900 pieces do the following:
2.1) Calculate its convex hull to keep just the relevant points (in coordinates relative to the down-left corner of the piece)
2.2) Identify its left-most, right-most, up-most and down-most points.
2.3) for each of the corners of the cake, put the piece in that corner and just one point in the other 3 corners and calculate the area of the convex hull obteined with these points, that is, the points of the current piece and the other 3 points. This will tell us how good is the current piece in each corner of the cake. -
Identify the best piece for each corner and heuristically put it in that corner (I tried to do it using as few rotations as I can, failed to implement a cuasi-A* algo to do that). This will be the initial configuration of the following optimization procedure.
-
Calculate the convex-hull of the initial configuration. You can figure out that only points of the first and last column/row will be present in the hull.
Optimizing from the initial configuration:
5) while there is time:
5.1) For each row (or column, one of them; randomly choose if rows or columns) that is present in the hull (not incluiding first and last row/column) take the rotation of x steps that have the minimum distance between left-most point of first and right-most point of last column (the similar procedure if you are rotating a column).
5.2) Calculate the new convex hull and compare its area with the best area found so far.
5.3a) If the number of steps has not reach the limit (1024), go to 5.1 (if the number of loops (from 5.1 to 5.3) we have done for this particular solution is greater than a certain value (4 or 5), include the first and last row/column in the optimization process).
5.3b) If there’s no valid rotation that reduce the area restart from 5.1 with the initial configuration.