“Even more pizza” is the new practice problem proposed for the Hash code 2021 challenge.
The Hash Code challenge gets more and more attendants every year and I like particularly because it involves – of course – coding, logic, mathematics, and a deep knowledge of algorithms and data structures. In addition, a good dose of team-working is very important. These are all ingredients that are fundamental when working at any IT Company.
Last year, Google has proposed – IMHO – a very simple problem (see my previous article on the Pizza problem – Google Hash Code 2020). Instead, this year the Google Hash Code team has proposed a practice problem that is very close – as complexity – to the qualification challenges.
Even More Pizza: the problem description
The goal is to help an imaginary pizzeria to choose the pizzas to deliver to Hash Code teams. As you know, each team can have a minimum of 2 members and a maximum of 4 members.
Each pizza has different ingredients and it is very important to deliver a pizza to each member of a team.
A specific pizza can be delivered to only one person: in other words, two persons cannot receive the same pizza.
Therefore, an order can be made of 2, 3 or 4 pizzas. The score of the order is the square of the sum of the unique ingredients for that order. The total score is calculated as the sum of the scores of each order.
At each Google Hash Code competition, there are T2 teams of 2 members, T3 teams of 3 members and T4 teams of 4 members.
The goal is to assign each pizza to a specific order only, so that the sum of the scores of the order is maximized, but the number of orders made of 2 pizzas cannot exceed T2, the number of the orders made of 3 pizzas cannot exceed T3 and the number of the orders made of 4 pizzas cannot exceed T4.
The input data
The input data set is composed of 5 files:
In each file, you can find:
- M: the number of pizzas
- T2: the number of teams of 2 persons
- T3: the number of teams of 3 persons
- T4: the number of teams of 4 persons
| Scenario | M | T2 | T3 | T4 |
|---|---|---|---|---|
| A | 5 | 1 | 2 | 1 |
| B | 500 | 65 | 60 | 60 |
| C | 10000 | 504 | 539 | 585 |
| D | 100000 | 1696 | 3661 | 2742 |
| E | 100000 | 39748 | 49195 | 29832 |
The rest of each files contain the ingredients of each pizza.
For each scenario, I’ve calculated the maximum number of orders and the number of pizzas required to deliver orders to all the Google Hash Code teams.
| Scenario | Max num. of orders | Num. pizzas required to deliver orders to all the teams |
|---|---|---|
| A | 4 | 12 |
| B | 185 | 550 |
| C | 1628 | 4965 |
| D | 8099 | 25343 |
| E | 118775 | 346409 |
The output data
The file to submit must contain a first line indicating the number of pizza orders.
The following lines contain the orders that are indicated with the number of pizzas of that order and the indexes of the pizzas (that belong to the range [0, M-1]).
Algorithm description
Coming soon.
C++ source code
My C++ code to solve the “Even More Pizza” problem is for patrons only and can be found here:
My current score
