When I started looking into the Google Hashcode challenges, the first suggestion I received from Google Team was to try solving the pizza problem… just to make practice.
I learnt that solving this problem really helps to find a solution to the challenges that Google has proposed during these years to pass the qualification process (and maybe the final qualification too).
In addition, it is a good opportunity to check your coding skills and improve them to implement your own algorithm in a limited amount of time.
#The pizza practice problem
Unfortunately, the pizza cannot be divided into slices of custom size. In fact, the slices must have an area that belongs to the range [2*L,H], where L is the minimum required number of tomatoes and mushroom in each slice.
#The input files
- R: number of matrix rows
- C: number of matrix columns
- L: the minimum number of each ingredient required for each slice
- H: the maximum area of the slice
| Filename | R | C | L | H |
|---|---|---|---|---|
| Example.in | 3 | 5 | 1 | 6 |
| Small.in | 6 | 7 | 1 | 5 |
| Medium.in | 200 | 250 | 4 | 12 |
| Big.in | 1000 | 1000 | 6 | 14 |
Pizza problem – Input test files (test scenarios) Download
#Solutions for two first input files
For the input files example.in and small.in, the choice of the slices that maximize the score is straightforward.
The solution for the given example.
Small pizza (11 slices, score is 42)
Small pizza (13 slices, score is 42)
Small pizza (14 slices, score is 42)
If you are interested to learn about my algorithm and how I achieved these results and the solutions for the medium and the big pizza, then subscribe to my blog or follow my free updates on the social networks. I’m planning to publish soon the explanation of my algorithm.