“More Pizza” practice problem: solved with maximum score

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.

You might be interested also about:

• Description of the algorithm to solve “More Pizza” problem
• C++ implementation of the solution to the “More Pizza” problem

The problem description

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?

The test scenarios

On the Google Hash Code judge system, there are five tests scenarios for this problem:

• example
• small
• medium
• quite big
• also big

The following table summarizes the input data for each test scenario:

Maximum score achieved

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!

The Table of Contents of the article is:

• Introduction
• Qualification round: some considerations
• How to solve the pizza… sorry, the qualification round?
  • How the code should be structured
  • This is why this challenge help you to improve coding skills
  • Finally, the algorithm
  • … (hidden)
• Conclusions

In another article, the C++ code implementation of the algorithm to solve the “More pizza” problem has been described.

This article contains the following table of contents:

• Introduction
• The main() function
• Reading data from a file
• The solution class
  • How to quickly calculate new solutions?
• The orderPizzas() function
• The console output
• The complete code