Solutions and code for the Practice Round of Hash Code 2020 "More Pizza".
The problem statement can be found here.
The input files can be found in input/
- example
- Pizza types:
4 - Slices per type:
5.25±2.17 - Slices to order:
17
- Pizza types:
- small
- Pizza types:
10 - Slices per type:
42.00±33.25 - Slices to order:
100
- Pizza types:
- medium
- Pizza types:
50 - Slices per type:
94.38±59.41 - Slices to order:
4,500
- Pizza types:
- quite big
- Pizza types:
2,000 - Slices per type:
504,916.60±288,099.66 - Slices to order:
1,000,000,000
- Pizza types:
- also big
- Pizza types:
10,000 - Slices per type:
75,396.84±43,144.36 - Slices to order:
505,000,000
- Pizza types:
You are organizing a Hash Code hub and want to order pizza for your hub’s participants. Luckily, there is a nearby pizzeria with really good pizza. The pizzeria has different types of pizza, and to keep the food offering for your hub interesting, you can only order at most one pizza of each type. Fortunately, there are many types of pizza to choose from! Each type of pizza has a specified size: the size is the number of slices in a pizza of this type. You estimated the maximum number of pizza slices that you want to order for your hub based on the number of registered participants. In order to reduce food waste, your goal is to order as many pizza slices as possible, but not more than the maximum number.
from Problem statement for the Practice Round of Hash Code 2020
Your goal is to order as many pizza slices as possible, but not more than the maximum number.
from Problem statement for the Practice Round of Hash Code 2020
The solution gets 1 point for each slice of pizza ordered. The total number of slices in the ordered pizzas must be less than or equal to the maximum number.
See the section on scoring in the Problem statement for the Practice Round of Hash Code 2020 for more details.
It's a basic knapsack problem.
In the knapsack problem, you need to pack a set of items, with given values and sizes (such as weights or volumes), into a container with a maximum capacity. If the total size of the items exceeds the capacity, you can't pack them all. In that case, the problem is to choose a subset of the items of maximum total value that will fit in the container.
A brute force or dynamic programming approach to this knapsack problem is not sufficient, because the input sizes for D and E are quite big. We use a branch and bound method to handle those cases as well.
Google OR-Tools provide an implementation for all of this, so the solution is quite short.
Overall 1,505,004,616 points.
- Pizza types:
4 - Slices per type:
5.25±2.17 - Slices to order:
17
16 points
- Pizza types:
10 - Slices per type:
42.00±33.25 - Slices to order:
100
100 points
- Pizza types:
50 - Slices per type:
94.38±59.41 - Slices to order:
4,500
4,500 points
- Pizza types:
2,000 - Slices per type:
504,916.60±288,099.66 - Slices to order:
1,000,000,000
1,000,000,000 points
- Pizza types:
10,000 - Slices per type:
75,396.84±43,144.36 - Slices to order:
505,000,000
505,000,000 points