Even more pizza: Hash Code practice problem (2021)

  • Post category:Algorithms
  • Reading time:3 mins read

“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
ScenarioMT2T3T4
A5121
B500656060
C10000504539585
D100000169636612742
E100000397484919529832
The main parameters at first row of the input files

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.

ScenarioMax num. of ordersNum. pizzas required to deliver orders to all the teams
A412
B185550
C16284965
D809925343
E118775346409
For scenarios A, B and E, it is not possible to deliver pizzas to all teams.

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

Even More Pizza Score > 703 Millions
Even More Pizza – Score greater than 703 Millions

Pietro L. C

C++ Software Engineer, Ph.D. working in Malta on embedded systems with a vision in mind: design best software to solve complex problems in the real world.