MUFFINS3 - Editorial

editorial
, , , , ,
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:

32

here there are two variables namely, the chef choses how many he wants to eat , and chef chooses the size of the package

if chef always want to get maximum on the more he can eat, then chef would always choose the size of the package as 1 right ? , so the maximum is N-1,

why is there so much explaination and confusion of n%a, n%2 round?

such a confusing question, from my side i think the answer is just n-1, chef can always choose the package size to be 1, and he can always choose to give only one cupcake, and the maximum he will have is n-1.simple

33

Wonderful Explanation! Even a beginner can also be able to understand it very easily. Thank you @ajaypanthagani for this explanation

1 Like
34

yes obviously !!

35

The answer is very simple after many testing
the always come is number by 2 +1

#include <iostream>
using namespace std;

int main() {
	// your code goes here
	int t;
	cin>>t;
	long int n;
	while(t--)
	{
	    cin>>n;
	        cout<<(n/2)+1<<"\n";
	}
	return 0;
}