One Pizza – Problem description & score

The "One pizza" problem is the practice problem proposed by Google for the Hash Code challenge 2022. Check the problem description and score.

A new practice problem has been published for the Google Hash Code 2022 challenge: the “One Pizza” problem.

“One pizza” problem description

Imagine you want to open a small pizzeria. It is so small that you can only offer one type of pizza.

Which ingredients you should put on your pizza? Obviously, you should offer the ingredients that are liked by the majority of the clients and avoid the ingredients that are not liked by this group of people.

Indeed, if the client doesn’t like any of the pizza ingredients or the pizza contains any ingredient he/she dislikes, the client will not buy the pizza. And you will lose money! 🙁

Luckily, the Google Team provides the information about the user preferences. But how to process this data in order to maximize the number of clients that will buy your product, i.e., your income?

My usual approach

I implemented an algorithm based on the previous “pizza” practice problems (for example, the more pizza problem). Please, check my score for each scenario here below:

One Pizza - Google HashCode - Temporary result achieved by Pietro LC Dot Com team.
One Pizza – Google HashCode – Temporary result achieved by Pietro LC Dot Com team

As shown in the image above, it is impossible to make all clients happy. Instead, it seems possible to only make happy at most half of clients. For sure, the most interesting scenarios are D and E.

A different approach

I’ve implemented a new algorithm to solve this problem. Since the time left to check my score was not enough to calculate the solutions for both the scenarios D and E, I preferred to try solving only the scenario E.

Using the new approach, I was able to increase a little bit my score. The calculations on the scenario D still take a lot of time (remember that the goal is to find an approach that provides a result long before 4 hours have been elapsed).

one pizza score 2 minutes left google hashcode
My score improved at 2 minutes left.

What about you? Which approach/algorithm have you used for the One Pizza problem? What is your score?

Pietro L. Carotenuto
Pietro L. Carotenuto

C++ Software Engineer, Ph.D. in Information Engineering. I like reading and learning new things while working on new projects. Main author on PietroLC.com looking for contributions and guest authors.

Articles: 22

Leave your feedback here:

Your email address will not be published. Required fields are marked *