Maximum Area Serving Cake - Company-specific OAs / Google OA

Problems
1

https://algo.monster/problems/google_oa_max_area_serving_cake

2

The area of a circle with radius 3 is incorrect in explanation 1. It should be 28.274, not 28.743

3

Hi…did you manage to figure out how to do it? I get its a binary search problem but what should I search for in the sorted array of areas?

4

You should search for the largest possible slice that can adequately feed all your guests. Your search space will go from the largest slice (largest pizza area divided by 1) to the smallest slice (smallest pizza divided by the number of guests). I started by generating a list of areas, then adding elements to that list to contain all the divisions of each of those areas from 1 to the number of guests, then sorting that list, then doing a binary search over it.

5

I also made a function to test whether a given slice size (area) is adequate to feed the number of guests. Then the problem boils down to the boolean search space that the other binary search problem examples show.

6

Thanks PK. Have you understood the heap solution given on this page?

7

I used binary search to find the largest area that still satisfies the number of guests.

The tricky part is because the number being searched is not an integer, we have to decide on what resolution we increase/decrease the boundaries of the search space, and I ended up using 0.00001.

def get_max_pizza_slice_size(radii: List[int], guests: int) -> float:
    areas = [r*r*pi for r in radii]
    def countGuests(slc):
        g = 0
        for a in areas:
            g += floor((a+0.000001) / slc)
        return g
    res = None
    lo = 0.00001
    hi = 1000*1000*pi
    while hi-lo > 0.00001:
        mi = (lo+hi)/2
        got = countGuests(mi)
        # print(f'try {lo}..{hi} -> {mi}, got {got}')
        if got >= guests: # slice too small, but OK
            res = mi
            lo = mi+0.00001
        else: # slice too big
            hi = mi-0.00001
        
    return res