August 15, 2018 On TCO18 Marathon Round 4
TCO18 Marathon Round 4 finished late on Thursday, August 9. For participants from Eastern Hemisphere it was already early Friday morning, though.
Milanin won the match and secured his place in the Finals. He was on top of the provisional standings with a solid margin over sdya, 946K points versus 908K, and based on the type of the task, little people were questioning his future win. The strategy Milanin used has not changed since I remember him participating. He did only 3 official full submissions this time, each one being a considerable improvement over the previous one. To compare with, sdya did 25 submissions.
As this match was the last possibility for Marathoners to qualify for this year’s TCO, I would like to congratulate those who advanced to the Finals: wleite, nika, Errichto, Milanin, PaulJefferys, tourist, eldidou, marek.cygan, tomerun, sdya, atsT5515, hakomo. According to these results, current TCO Marathon champion Psyho will not be able to defend his title in the Finals.
This time we were pleased to see Nickolas’ task tested by Round 1 winner wleite, who in addition to the actual testing, added several important features to the visualizer – roses being drawn as neat flowers, points that can be used as cut starts being highlighted, manual play mode. The later add-on being of extra importance, as it allows to think about the solution without writing any line of code. I would like to thank the people involved in preparation for the overall success of the task – good distribution of scores, interesting and hard to hack scoring function, no usage of placement-based scoring.
The task CakeSharing asked to divide a rectangular cake into a fixed amount N of small pieces. These N small pieces had to be as equal in size, as possible. There would not be a problem – just cut these N pieces one-by one, if not a few details.
First, you can do exactly N-1 cuts. That means that you cannot cut an arbitrary shape for every next piece you are preparing. For instance, this cut configuration is forbidden:
Second, there are roses distributed evenly and at random on the cake surface. If we divide the cake into integer unit-sized cells, there will be some roses in the centers of some of these unit cells.
Last, cut endpoints must start and end at integer coordinates. Thus, if you managed to do a clever diagonal cut that does not have integer points on it, then your next cuts are very hard to make.
Overall, the task given to the competitors was quite hard to “just solve somehow”. In my opinion, this is the main reason only 81 participant managed to submit a solution that scores higher than zero.
To give you an idea, the leaders used Dynamic Programming (DP) to solve the main part of the task. I will start the description of the solution from some basic observations about the task instead.
The main and most important thing is that orthogonal cuts – are unavoidable for large boards. This is because vertical and horizontal cuts give large amount of extra points for possible future cuts. I have also tried 45° cuts, because they have almost the same density of integer points as orthogonal cuts. Adding them on early stages gave worse results though, thus I removed this logic from the solution.
Thus we can use only horizontal and vertical cuts at early stages, until the rectangles formed by these cuts are small enough.
Once we have small enough rectangles, we can add any cuts, not limiting them to 90° multiples. To be honest, it is not guaranteed that the optimal solution has only 90° cuts at the top layer. Given the constraints, it turned out to be not feasible to investigate such solutions, even though chances are high the optimum lies between those more complex solutions. The reason is that, as I said, orthogonal cuts give many integer candidate points for next cuts. This orthogonality also makes the integer candidate points to be evenly distributed on the boundaries of the smaller areas for subtasks.
Another observation is that we do not know the amount of roses in the final configuration we are making. There are some possibilities there: make an educated guess, ignore rose deletion, use an extra DP dimension, etc. I used an educated guess, assuming we will end up with the same equal integer amount of roses for all the final areas. I mean, that exactly (R mod N) roses will be thrown away. Later, once one of the solution candidates is fully constructed, I recalculate the standard deviation for roses from scratch. This allows distinguishing good solutions from even better.
The easy observation is that we know the mean area in any solution – it is total area of the cake divided by amount of pieces. This is so because the formula for the mean is a sum of all the components, divided by N. The sum of all the components is obviously the total area of the cake.
Here my path and best players’ path differs. I continued to iteratively improve my greedy solution, adding randomness to it, tuning parameters, as well as trying several completely different approaches. Some sort of DP was one of them, but I did not investigate enough amount of time into it, and the result did not take into account the roses’ positions and probably had other issues.
As for the top solutions, PaulJefferys, 3rd place, has shared his ideas on the forum. He solves 2 tasks first:
- All the small instances of the original problem, where you are given a rectangular part of the original board and the task is to split it into up to 8 pieces, using any type of cuts.
- The rectangular version of the problem where you can make only horizontal and vertical cuts. He solves this simpler task for all the possible sub-cakes of the original task using DP. There are 814 states in the DP and each state considers only 2 transitions. He assumes that in any good solution the area of any sub-cake is an integer multiple of the average area with some tolerance. He calculates the amount of final pieces in a bigger piece, K, by dividing the area of that bigger piece by average area. He considers only divisions into K±1 pieces only. This speeds up the DP by a factor of board size.
Then he injects the results of the DP for small instances into the other DP, for large orthogonal instances.
He also uses several tweaks, including a simpler evaluation function:
“I did A sum(area^2) + B(sum(roses^2) + 2 * deleted roses * (total roses / total pieces)). I started with A=B=1. This is nice because if you want to minimize std dev area and sum (area) is fixed, then its the same thing to minimize the sum of the squares of the areas. And the tweak above for roses basically does the same thing for roses. Then if X = sum(area^2) and Y = sum(roses^2) the derivative of the objective function with respect to X and Y is (1+std(area))/std(rose) and (1+std(rose))/std(area) so you can replace A and B with these quantities in subsequent iterations of the DP and generally get better solutions.”
The nice thing about this alternative scoring function is that it seems to converge with more iterations.