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?