This year, the Google Hash Code team has proposed a different version of the Pizza practice problem. For this reason, it has been entitled “More Pizza”.
The problem description – as usual – is available for all users registered to the Google Hash Code judge system. If you haven’t read yet, please, let me briefly describe the proposed problem.
Your menu contains N pizzas. Each pizza has a certain number of slices. You can order as many pizzas you want but:
you can order at most one pizza for each type
the total number of slices cannot exceed a given number M
The maximum number of slices M belongs to the range [1, 10^9].
The maximum number of pizzas N belongs to the range [1, 10^5].
Each pizza contains at least one slice, but it could also have M slices. In other words, for each pizza, the number of slices belongs to the range $[1, M]$.
Now you have all data,… which pizzas are you going to order?
My algorithm was able to get the maximum score for each given scenario, except for the “example”. I think this is an important suggestion to keep in mind during the real challenge: the optimal solution might not exist and – therefore – there might be no solution perfectly fitting the given constraints.
Funnily enough, the example was the only imperfect test scenario.
The “More pizza” problem can be solved using the algorithm described in this article. In this article, I reward the reader with some tips and tricks required to pass the Google Hash Code Qualification step. In fact, IMHO the real finish line is not solving the “Pizza” or “More Pizza” problem but – at least – pass the Qualification Round, then to attend the Final Round and – why not? – win some money!
