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

9 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.

53 Likes

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

11 Likes

@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.

3 Likes

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.

1 Like

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

2 Likes

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

2 Likes

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

Click to view

hidden text

1 Like

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.

10 Likes

Can I know why we are dividing by 2?

3 Likes

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?

poorly worded question

3 Likes

https://www.codechef.com/viewsolution/27269102
My code uses the logic ans = floor(n/2) + 1
I am still getting wrong answer.

hey @exarchias123 can you explain this line with an example
" The +1 because if we leave an odd number (2 is an odd number), we will not have remainder. "

@habib_bit in your case if n=5 then package size will be (5/2)+1=2+1=3 which is okie, but leftover cakes will be (5/2)-1=2-1=1 which is wrong.
i think leftover cakes will work fine with (n-package size)

Okay, we want to know divisor that gives maximum remainder;

let n be a number to be divided and i be the divisor.

we are interested to find the maximum remainder when n is divided by i , for all i<n .

we know that, remainder = n - (n/i) * i //equivalent to n%i

If we observe the above equation to get maximum remainder we have to minimize (n/i)*i

minimum of n/i for any i<n is 1 .

Note that, n/i == 1 , for i<n , if and only if i>n/2

now we have, i>n/2 .

The least possible value greater than n/2 is n/2+1 .

Therefore, the divisor that gives maximum remainder, i = n/2+1

Here is the code in C++

#include <iostream>

using namespace std;

int maxRemainderDivisor(int n){
    n = n>>1;
    return n+1;
}

int main(){
    int n;
    cin>>n;
    cout<<maxRemainderDivisor(n)<<endl;
    return 0;
}

Time complexity: O(1)

14 Likes

this type of apparently self-contradicting and glossy questions are what causing new comp sci students to be afraid of the amazing world of competetive programming, including me.

3 Likes

this type of glossy problems, which barely have an implementation to the real world, are itselves not explained properly - surely is a hastle to competitive programmers.

1 Like