Given a list of preferences find how many people can be satisfied at most

Problems and Contests
#1

Hello,
I’ve recently encountered a problem in an internal resource at work (thus cannot link) and tried for a couple of days to solve it and then to understand the solution. It seems like a relatively simple problem but for some reason I cannot grasp why and how the solution works.

Problem statement:
You are given a list of preferences in the form of tuples (A, B, C), standing for Apricot jam, Banana jam, Chocolate. You want to make cookies that use a mix of the three ingredients and serve them to your friends.
A friend will eat the cookies only if the ratio of the ingredients is above their expectations.

Given the list of preferences, how many friends can you satisfy at the same time?

0 <= A, B, C <= 10’000
A + B + C <= 10’000
Given a friend F and their preferences Af, Bf and Cf, they are satisfied if and only if the cookies contain at least Af apricot jam, Bf banana jam and Cf chocolate.

Solution in CPP:

constexpr int32_t APRICOT = 0;
constexpr int32_t BANANA = 1;
constexpr int32_t CHOCOLATE = 2;

int ingredient_ratios[5000][3];
int counts[10001];

int main() {
        int num_of_friends;
        cin >> num_of_friends;
        int ans = 0;
        for(int i = 0; i < n; i++) cin >> ingredient_ratios[i][APRICOT] >> ingredient_ratios[i][BANANA] >> ingredient_ratios[i][CHOCOLATE];
         
        for(int i = 0; i < num_of_friends; i++)
        {
            memset(counts, 0, sizeof(counts));
            for(int j = 0; j < num_of_friends; j++)
            {
                if(ingredient_ratios[j][APRICOT] <= ingredient_ratios[i][APRICOT])
                {
                    int b = ingredient_ratios[j][BANANA];
                    int c_start = ingredient_ratios[j][CHOCOLATE];
                    int c_max = 10000 - b - ingredient_ratios[i][APRICOT];
                    if(c_max >= c_start)
                    {
                        counts[c_start]++;
                        if(c_max<10000)
                            counts[c_max+1]--;
                        else counts[10000]--;
                    }
                }
            }
            int sum = 0;
            for(auto x: counts)
            {
                sum += x;
                ans = max(sum, ans);
            }
        }
        cout << ans << "\n";
    }
}

Why and how does this solve the problem? I think I sort of understand that when we sum the counts array, we’re always getting the max amount of people that can be satisfied by chocolate in range of C to C_max, but why is that sufficient to solve the problem? Doesn’t this solution miss some possible fits that could have higher Apricot jam content but less of the remaining ones required?

#2

If I read the problem correctly, then the solution would be to find the maximum amount of A, B, and C for each friend. If we make a cookie with A_mx + 1, B_mx + 1, C_mx + 1, then all friends will be satisfied as it’s the maximum plus 1.

#include "bits/stdc++.h"
using namespace std;

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n; cin >> n; // number of friends
    cout << n << "\n";
    return 0;
}

Note in my code that I didn’t find the max for A, B, and C because we already know that we can satisfy all friends.

#3

We are asked to find the maximum amount of friends that can be satisfied at the same time with 1 combination of A, B and C. Sorry if that was unclear.
In addition to that, please note that the solution I provided is not only correct, it is the fastest solution anyone at my company could figure out.

Here’s an example:
F1 (10’000, 0, 0)
F2 (3’000, 3’000, 3’000)

F1 requires at least 10’000 apricot jam, so F2 would be satisfied with the apricot jam as well. But F2 also requires 3’000 banana jam and 3’000 chocolate jam.
As the sum of A + B + C <= 10’000, we cannot satisfy both friends (because 10’000 + 3’000 + 3’000 would have been 16’000). As such, the maximum amount of friends that can be satisfied in this example is 1 (either F1 or F2).

Now consider this example:
F1(0, 2000, 3000)
F2(3333, 3333, 3333)
F3(3333, 3334, 3333)

Now we can satisfy all friends by taking F3’s preferences directly.

Another example:
F1(2000, 4000, 4000)
F2(3000, 5000, 2000)
F3(2000, 3000, 4000)

Now I believe we can satisfy at most 2 friends (namely F1 and F3). The sum for F3 is 2000 + 3000 + 4000 = 9000. So we have 1000 leftover. Thus, we can also make F1 by doing this: (2000, 3000 + leftover 1000, 4000) and we can satisfy them as well. But F3’s mix can never satisfy F2, we only have 1000 leftover and the difference between F2’s banana requirement and F3’s banana requirement is 2000.