MUFFINS3 - Editorial

editorial
, , , , ,
11

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

12

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

14

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

15

poorly worded question

3 Likes
16

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

17

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

18

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

19

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
20

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
21

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
22

Explanation on point. Thank you so much @ajaypanthagani

1 Like
23

You are considering that smallest size of cupcakes will be two and so goon and chectk the maximum size of cupcakes.

24

But it’s take 1.01 second :neutral_face: :neutral_face:

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

#define ll long long int
int main() {
int T;
cin>>T;
while(T–) {
ll N;
cin>>N;
int size,lft,var=0;
if(N==2)
cout<<N<<endl;
else {
for(int i=2;i<= N/2 + 1;i++) {
if(N%i!=0) {
lft=N%i;
if(var<=lft) {
var=lft;
size=i;
}
}
}
cout<<size<<endl;
}

}
}

25

the number will substract by itself which results 0 ie no cupcakes is left…

26

nice explanation, Thanks for explanation!

27

I tried with this but its giving TLE :cry:

 #include <iostream>
#include <math.h>
using namespace std;
int result(int num)
{
    int max=-1;
    for(int i=1;i<=num;++i)
    {
        if(abs(num%i)>max)
        max=abs(num%i);
    }
    return max;
}

int main() {
	// your code goes here
	int t,n;
	cin>>t;
	while(t--)
	{
	    cin>>n;
	    cout<<(n-result(n))<<endl;
	}
	return 0;
}
28

I think i have explained pretty well through example.

Take example of n = 11.
Number of muffins = 11
Package Size = 1 2 3 4 5 6 7 8 9 10 11
Cupcakes Remaining = 0 1 2 3 1 5 4 3 2 1 0 (we get remaining Cupcakes by n % package size)

now, take the case of n = 15
Package Size = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Cupcakes Remaining = 0 1 0 3 0 3 1 7 6 5 4 3 2 1 0

clearly, you can see if package size is n / 2 + 1 we get max number of cupcakes for chef i.e if package size is 6 in
case of 11 muffins remaining cupcakes is 5 and if package size is 8 in case of 15 muffins remaining cupcakes is 7
which is the max the chef can get. So for n number of muffins package size should be n / 2 + 1 so that chef can get
max number of muffins in hand.

4 Likes
29

same bro! have you got the cause?

1 Like
30

Thanks…This explanation is pretty simple.

31

nope :frowning_face: