EGRCAKE - Editorial

editorial
gcd
nov15
simple

#1

PROBLEM LINK:

Practice
Contest

Author: Egor Bobyk
Tester: Istvan Nagy
Editorialist: Xellos

DIFFICULTY:

SIMPLE

PREREQUISITES:

Greatest common divisor.

PROBLEM:

We have a permutation exttt{P}[0..N-1] with exttt{P}[x]=M+x for x < N-M and exttt{P}[x]=x-(N-M) for x \ge N-M. Start at x=0 and keep moving from x to exttt{P}[x]. When visiting some x for the second time, stop. How many different x-s have been visited?

QUICK EXPLANATION:

The number of robots with cakes is N/gcd(N,M), which can be found using Euclid’s GCD algorithm.

EXPLANATION:

For permutations, it’s a well-known fact that if we start at x=0, we’ll stop at x=0 as well - a permutation is made of cycles.

We can just simulate the first subtask. For the second subtask, this is too slow, but we can reduce our problem to a completely different one. The trick is to see that in each step, we’re sent from x to x+M and if we see that x \ge N afterwards (it really happens iff x \ge N-M before this step), then we subtract N to get it back into the range [0,N). Imagine what’d happen if we wrote the permutation on paper and connected its ends - we’re always just moving M places to the right on the tape. More formally, after moving to the next robot j times, we have x=(jM)\% N.

When will we visit x=0 again, then? It happens for the smallest positive j such that N\,|\,jM; which is known to be N/gcd(N,M) (think why). That’s the answer to the question “how many robots will have a cake at the end?”; if it’s N - if N and M are coprime - we should print “YES”.

The greatest common divisor can be computed using Euclid’s algorithm in O(\log N), which is the time complexity per test case. Memory: O(1).

AUTHOR’S AND TESTER’S SOLUTIONS:

The author’s solution can be found here.
The tester’s solution can be found here.
The editorialist’s solution can be found here.

RELATED PROBLEMS:


#2

could you please explain why its n/gcd(n,m), i didn’t get that.

what is wrong with my code.
I think of this problem as cyclic figure e.g 8, 2 (n, m)

    3(start) 
2       4 
1       5 

8       6 
    7

#include <stdio.h>

int main()
{
    int t;
    scanf("%d", &t);
    while(t--) {
	int n, m;
	scanf("%d%d", &n, &m);
	if(m==0) {
		if(n==1)
			printf("Yes

");
else
printf("No 1
");
continue;
}
if((n-m)%m==1)
printf("Yes
");
else
printf("No %d
", ((n-m)/m) + 1);
}
return 0;
}
Just think of we need to determine whether n-m is completely divisible by m or not, if remainder is 1 the print (n-m)/m else print yes(as if it would be greater than 1 or 0), it would surpass 1 and repeats until it gets to one, thereby filling all 2 to m. try some other cases.


#3

Any idea why this approach fails? @Xellos? It passes all except 4 testcases

I tried a different approach to this problem. Here’s what I did:

I precomputed the lowest prime number for every number less then the max limit of M as given in the question. Now, If you notice, (atleast this worked out for small values), we can prime factorize M and if any of it’s prime factor is divisible by N, we divide N by that prime factor ONCE and continue factorizing M.< br>
In the end, if N does not change, that means that the answer is ‘YES’ else the answer is ‘NO’ followed by the current value of N which had been divided in the middle


Here’s my code which explains it more clearly:

https://www.codechef.com/viewsolution/8772878

P.S: I came across the GCD logic hours later :stuck_out_tongue:


#4

What does N|jM mean ??


#5

author’s solution link broken, please check


#6

What is wrong with my code? Why is it necessary to use gcd?
#include
#include
using namespace std;

int main()
{
int t, n, m, i, k;

cin>>t;
while(t--)
{
    cin>>n>>m;
    pair <int,int> p[n];
    for(i=0; i<n-m; i++)
        p*.first=m+i+1;
    for(i=n-m; i<n; i++)
        p*.first=i-n+m+1;

    p[0].second=1;
    for(i=1; i<n; i++)
        p*.second=0;
    k=p[0].first-1;
    while(1)
    {
        k++;
        if(p[k-1].second==1)
            break;
        else
        {
            p[k-1].second=1;
            k=p[k-1].first-1;
        }

    }
    int count=0;

    for(i=0; i<n; i++)
        if(p*.second==0)
            count++;
    if(count==0)
        cout<<"Yes"<<endl;
    else
        cout<<"No "<<count<<endl;





}

}


#7

#include <stdio.h>
#include <stdlib.h>
int main(){
long int a[1000000000],b[1000000000],c[1000000000];
int t;
scanf("%d",&t);
while(t–){
int m,n,i,j;
scanf("%d",&n);
scanf("%d",&m);
for(i=1;i<=n;i++){
a*=i;
}
j=1;
for(i=m+1;i<=n;i++){
c[j]=a*;j++;
}
for(i=1;i<=m;i++){
c[j]=a*;j++;
}
for(i=1;i<=n;i++){b*=0;}
b[c[1]]=1;
i=1;
while(b*!=1){
b[c*]=1;
i=c*;
}
for(i=1;i<=n;i++){
if(b*==0){printf(“no”);}
else{printf(“yes”);}
}
}
return 0;

}
whats wron with my ans.


#8

@Xellos0

please explain this

When will we visit x=0,x=0 again, then? It happens for the smallest positive j such that N|jM; which is known to be N/gcd(N,M).


#9

can someone please explain why the smallest value of J is N/gcd(N,M)?


#10

Which part did you not get? You’re basically always moving M places to the right and looking for the first time when you’ve moved by a multiple of N places in total.


#11

Try it for N=3, M=1. You say the answer is NO, but it’s YES.

It seems you don’t know what GCD is.


#12

got it now thanks btw


#13

N divides j*M


#14

help me…somebody


#15

10**9 array? Insufficient memory


#16

as leaving the array part