November 16, 2020 TCO20 Marathon Match Finals: Pizza Anyone?

The Pizza

What do you call someone that plays with pizza toppings?

Definitely a TCO20 Marathon Match finalist. 

After this match our finalists will never again look at a pizza without some thoughts about the TCO20 Marathon Match finals. They might love it, or hate it, or eat it. Let’s get to describing their task, and how this problem evolved to become what it is today.

The task seems pretty straight forward. You are given a clean pizza base, with a limited supply of ingredients to place on the base. We want a nice neat pizza, so the ingredients can’t overlap with the boundary of the base or with each other, but they can touch each other. The size of the base always remains fixed. Luckily the ingredients come in only two different shapes. Circles and rectangles. We thought about adding triangles, but it was difficult to find some real food matching the triangle shape. 

So, what is the objective? You need to cover the base with as many tasty ingredients as you can. The term tasty refers to the ratio between the area of circular and rectangular ingredients. Some test cases might require only circular ingredients, while other test cases require only rectangular ingredients, but mostly there should be some kind of balance between the two. The balance is randomly defined for each test case.

Let’s look at a sample pizza from the visualizer:

Have you ordered your pizza yet? While we wrote and tested this problem we certainly ate some pizza, and some more pizza, and another slice ….

For completeness I’ll include the official brief problem statement here:

Everyone loves pizza right? This is why you are making pizza for your friends. You have a circular pizza base with radius 100 and center (0,0). You have also prepared C circular ingredients (tomatoes, onions and salami) and R rectangular ingredients (pineapple and capsicum slices). Now you want to place some or all of the ingredients such that they cover as much of the base as possible. The ingredients cannot overlap each other and they cannot lie outside the base. In particular you want to maximize c + r – abs(X*c – (1-X)*r), where c is the total area of placed circles, r is the total area of placed rectangles and X is a provided coefficient that controls the balance between the two shape types.

Pizza Evolution

The following is a bit of background on how the problem statement evolved and changed as we worked on putting the problem together.

Our problem writer dimkadimon initiated the problem idea that the task would be to place circles and rectangles in as small a rectangle as possible. Enclosing circles in a box or circle is a famous problem, but we haven’t really seen many problems requiring contestants to place different shapes inside another shape. We had a circle inside a box type of problem many years ago, Round 3 of TCO MM 2013. In order to avoid too much similarity we decided the target shape would be circular. So, the pizza theme was born.

Some of the first iterations involved packing all the shapes in as small a circle as possible. A symmetry score was also added, where you had to balance the same number of shapes in each quadrant of the pizza. That seemed too trivial, so we had a few iterations on finding a simple scoring function that would allow the balancing of shapes.

At some stage we did away with the smallest circle goal, and decided to keep the base fixed and not force the solution to use all the shapes. 

In short, the solutions had to determine the following: (over-simplified)

• Determine which circles and which rectangles should be used in order to balance the area. The input parameter X determines this balancing ratio.
• Pack these circles and rectangles as tightly as possible.
• If there’s open space for more shapes, keep on adding them (as balanced as possible).

The Pizzaiolo

“A pizza-making professional is affectionately referred to as a pizzaiolo.”

We have a very strong group of pizzaiolos this year. Psyho and tourist both with multiple TCO victories under their names and wleite with over ten TCO finals. A special congratulations to vdave for his first TCO finals and being a community member way back since Marathon Match 14.  

This year we have a brutal twenty-four hour match. Everybody is competing from home in their own time-zone simultaneously. We have a great admin team taking turns watching the video and audio streams of these great contestants. The online competition format is definitely very exciting but it brings many more difficulties for the contestants. Some had to wake up very early, some did not sleep before the contest, and some opted to try and nap during the contest. There are minor connection issues, family members interrupting for a piece of pizza and contestants walking up and down talking in foreign languages. It’s brutal and intense.

From the start the whole leaderboard shuffled every few minutes, it was and is (there are seven hours to go while writing this) still difficult to know who will be crowned as champion. We saw great submissions very early on and were amazed at how the contestants figured out how to keep on improving their solutions.

Let’s look at the leaderboard at around seven hours to go:

Only fifty test cases were used for provisional testing, which means the leaderboard may change significantly with the thousands of system tests. One failed test case could cause a burned pizza.

Early on we already saw some great submissions. Below is one from tomerun where you can see that he tried to balance the area filled by circles and rectangles, but didn’t succeed yet. X is 0.5 which means we want an equal amount of circle and rectangle areas. He was already doing a great job in packing the shapes, just the balancing part needs more work.

This was a solution from Psyho much later in the contest where he did a great job placing small circles within larger circles and squeezing in a few rectangles.

Only time will tell who will be crowned as the champion this year. The one thing that I can tell you with less than seven hours to go is that the competition is still wide open. Anyone can still take it.