×

# EGRCAKE - Editorial

Author: Egor Bobyk
Tester: Istvan Nagy
Editorialist: Xellos

SIMPLE

# PREREQUISITES:

Greatest common divisor.

# PROBLEM:

We have a permutation $\texttt{P}[0..N-1]$ with $\texttt{P}[x]=M+x$ for $x < N-M$ and $\texttt{P}[x]=x-(N-M)$ for $x \ge N-M$. Start at $x=0$ and keep moving from $x$ to $\texttt{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:

This question is marked "community wiki".

7★xellos0
5.9k54292
accept rate: 10%

19.8k350498541

 0 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 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\n"); else printf("No 1\n"); continue; } if((n-m)%m==1) printf("Yes\n"); else printf("No %d\n", ((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.  link This answer is marked "community wiki". answered 16 Nov '15, 15:43 1★dcode44 1●1 accept rate: 0% 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. (16 Nov '15, 16:22) xellos07★ 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. (16 Nov '15, 17:19) xellos07★ got it now thanks btw (16 Nov '15, 18:08) dcode441★
 0 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 :P answered 16 Nov '15, 16:56 61●1●5 accept rate: 0%
 0 What does N|jM mean ?? answered 16 Nov '15, 18:30 484●9 accept rate: 10% N divides j*M (16 Nov '15, 20:08) xellos07★

What is wrong with my code? Why is it necessary to use gcd?

# include<utility>

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[i].first=m+i+1;
for(i=n-m; i<n; i++)
p[i].first=i-n+m+1;

p[0].second=1;
for(i=1; i<n; i++)
p[i].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[i].second==0)
count++;
if(count==0)
cout<<"Yes"<<endl;
else
cout<<"No "<<count<<endl;

}


}

3★dimi
11
accept rate: 0%

 0 #include #include 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]=i; } j=1; for(i=m+1;i<=n;i++){ c[j]=a[i];j++; } for(i=1;i<=m;i++){ c[j]=a[i];j++; } for(i=1;i<=n;i++){b[i]=0;} b[c[1]]=1; i=1; while(b[i]!=1){ b[c[i]]=1; i=c[i]; } for(i=1;i<=n;i++){ if(b[i]==0){printf("no");} else{printf("yes");} }  } return 0; } whats wron with my ans. answered 23 Jan '16, 13:58 2★sahiji 1 accept rate: 0% help me.....somebody (23 Jan '16, 15:16) sahiji2★ 10**9 array? Insufficient memory (23 Jan '16, 16:14) vsp46★ as leaving the array part (23 Jan '16, 19:44) sahiji2★
 0 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). answered 26 Jan '16, 16:25 1★arpit728 683●17●65 accept rate: 10%
 0 can someone please explain why the smallest value of J is N/gcd(N,M)? answered 22 Aug '18, 22:16 4★skyhavoc 161●6 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,663
×1,173
×319
×120

question asked: 14 Nov '15, 19:02

question was seen: 4,803 times

last updated: 30 Aug '18, 21:57