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