MUFFINS3 - Editorial

Problem Link

Practice
Contest

Difficulty:

CAKEWALK

Pre-requirements:

Simple Arithmetic

Problem:

Chef has N cupcakes, which he wishes to package. He makes as many packages of a fixed size as possible from the N cupcakes. After he has made these packages, he eats the remaining. Find what size of package (A) will ensure that he gets to eat the maximum possible number of cupcakes. If there is a tie, determine the largest such package-size.

Quick Explanation:

Given the size of the package A, the number of cupcakes Chef will get to eat will be N % A. Let us denote the optimal size by A#. A# is then [N/2]+1, where [x] is floor(x).

To see the proof of this, firstly note that [N/A#] = 1. If not, let k = [N/A#] > 1. Assuming that Chef uses size A#, he gets N - k * A#. If Chef had used A = k * A#, then too he would have got N - k * A#. And in deciding between these two which to choose, he would choose the larger, this means that he would have rather chosen “k * A#” instead of A#, thus contradicting that [N/A#] > 1.

Now, [N/A#] = 1 <=> A# > N/2, and that the amount Chef gets to eat = N - A#.

This is maximum for A# = “least integer > N/2” = [N/2] + 1.

Detailed Explanation:

In order to solve this question, we first need to ask ourselves, “if I were the Chef, and I were to use a package-size of A, how many cupcakes would I get to eat?”

If we can answer this question, it will give us an idea of what could possibly be the optimal A. In fact, the answer to the above question, is merely N % A. This is because Chef keeps on taking out cupcakes in groups of A to package, so the number of cupcakes he has left follows the sequence N, N-A, N-2A, …, N - k * A, where after taking out k packages, we have N - k * A < A. This is precisely N % A.

Approach 1:

This approach is exactly as described under “Quick Explanation”.

Claim: Chef will make only a single package in the optimal size (after getting rid of ties).

To illustrate the proof as given earlier, let us assume N = 15.
Now,

  • A = 2, chef uses up 14 cupcakes in his package. He might as well have chosen his package size as A=14 here.
  • A = 3, chef uses up 15 cupcakes in his package. He might as well have chosen his package size as A=15 here.
  • A = 4, chef uses up 12 cupcakes in his package. He might as well have chosen his package size as A=12 here.

In this manner, so long as his chosen package size allows for more than 1 package, then he might as well have chosen his package size correspondingly larger : [N/A]*A to be precise.

The above puts a lower-bound on the optimal package size (A#), namely > N/2. Also, given this size A#, the remaining cupcakes is exactly N-A#. Maximizing this quantity subject to A# > N/2 gives us A# = “least integer > N/2” = [N/2] + 1.

Approach 2:

In this approach, let us first investigate what happens to the number of remaining cupcakes (lets denote it by f(A)) as a function of A.
If we were to try simple values of A to see what happens, we get

  1. for A = 1, Chef has 0 cupcakes left.
  2. for A = N, Chef has 0 cupcakes left.
  3. for A = 2, Chef has 0 or 1 cupcakes left (depending on whether N is even or odd).
  4. for A = N-1, Chef has 1 cupcake left.
    and so on.

The above discussion qualitatively gives us the following ideas:
If A is too small, then f(A) is also small (bounded by A).
If A is too large, then f(A) is again small since we’ve already used up cupcakes in the package itself.

Formally,

  1. f(A) < A (N % A < A always)
  2. f(A) <= N - A (since A <= N, we take out at least one package).

Armed with the above two observations, we get that f(A) < N/2 irrespective of whatever size we choose: this is seen by summing the 2 inequalities above, giving us 2 * f(A) < N => f(A) < N/2.

Further, the bounds given above suggest that they will be weakest when A ~ N/2: the bounds can be written as f(A) <= min(A-1, N-A), where the term on the RHS is largest when A = (N+1)/2.
The above shows us a Necessary condition on the number of remaining cupcakes: f(A) < N/2.

Finally, if A <= N/2, then the bound “remaining <= N-A” wouldn’t be strong, since we could take out 2 packages, giving us remaining <= N-2A; however if A > N/2, then we get that f(A) = N - A. Thus, choosing A = [N/2] + 1, which is the least integer > N/2, we would get f(A) = (N-1)/2 (for odd N), = N/2 - 1 (for even N) which are in both cases the largest integer < N/2.
This shows us a Sufficient condition on the number of remaining cupcakes: that it is Possible to get “the largest integer < N/2” as our answer.

In other words, we have found a necessary and sufficient condition proving that A = [N/2] + 1 is the optimal package size.

Author’s Solution:

Can be found here

Tester’s Solution:

Can be found here

5 Likes

i think this question contradicts itself. First it says that “chef makes as many packages as possible” and then at the end it says that “chef wants to eat as many leftover cakes as possible”. Make up your mind, re-frame the question properly. If chef wants to eat the most number of cupcakes then A would be the least possible package i.e 2 always.

5 Likes

the explanation is confusing.i how can he do both tasks simultaneously i.e to maximize yield and maximize leftovers?

@chris_coder if we consider the answer to be 2, then the number of leftover cupcakes will not be maximum. I think if we consider a package size of (n/2)+1 we will get the maximum number of leftover cakes i.e (n/2)-1.

I am getting a WA on using

Isn’t normal integral division n/2 also gives floor value? I am getting an AC if not using std::floor()

This is regarding my submission on MUFFINS3 problem.

how is the output 2 for input 2 in the first test case ? i think the output must be 3

@shubam_53 How can you pack more cupcakes than number of available cupcakes?

1 Like

the editorial is good . awesome question . ac in 2nd go.

Click to view

hidden text

The editorial and the description was bit off and pretty confusing, but the problem was nice.
I would not say that it doesn’t belong to simple arithmetic, (the theory used for this problem is not exactly addition and subtraction), but that is just me I guess.
Nevertheless, thank you for posting this problem. :slight_smile:

I will try to make some kind of explanation though as I would like to receive it:
The chef wants to eat as many remaining muffins as possible, so he has to find a way to use packets that are leaving enough remaining muffins.

The number of the muffins has to be divined by the size of packet, let’s say A#.
So the division will be N/A#, (N is the number of the muffins).
Through calculating the margins, (for lack of better words).
We are ending up with the idea that the most optimal number for the size of the packet will be:
Let’s call it x
x = [N/2]+1 when:
The 2 is chosen for A# because it divines everything in the middle, (I assume).
The +1 because if we leave an odd number (2 is an odd number), we will not have remainder.
The N/2 part has to be floored, because it gives better results.
I know that my explanation is primitive, but I hope it helps :slight_smile:

In case that wasn’t clear this x is the answer:
x = floor(N/2)+1

Best Regards
Robert.

Can I know why we are dividing by 2?

1 Like

If chef wants to maximize the number of cup cakes then he will always choose 2 so the remaining will be there for chef

If chef wants to maximize the number of cup cakes then he will always choose 2 so the remaining will be there for chef

And in case of minimize number of cupcakes by which number he should divide then?