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:
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).
What about you? Which approach/algorithm have you used for the One Pizza problem? What is your score?
