You are not logged in. Please login at www.codechef.com to post your questions!

×

EGRCAKE - Editorial

0
4

PROBLEM LINK:

Practice
Contest

Author: Egor Bobyk
Tester: Istvan Nagy
Editorialist: Xellos

DIFFICULTY:

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

asked 14 Nov '15, 19:02

xellos0's gravatar image

7★xellos0
5.9k54191
accept rate: 10%

edited 08 Jan '16, 17:29

admin's gravatar image

0★admin ♦♦
19.1k348495534


author's solution link broken, please check

link

answered 25 Nov '15, 22:51

codedog29's gravatar image

3★codedog29
556
accept rate: 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 <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\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

dcode44's gravatar image

1★dcode44
11
accept rate: 0%

edited 16 Nov '15, 16:27

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★

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

link

answered 16 Nov '15, 16:56

bholagabbar's gravatar image

4★bholagabbar
6115
accept rate: 0%

edited 16 Nov '15, 23:20

What does N|jM mean ??

link

answered 16 Nov '15, 18:30

sanket407's gravatar image

4★sanket407
4849
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<iostream>

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;





}

}

link

answered 17 Dec '15, 19:25

dimi's gravatar image

3★dimi
11
accept rate: 0%

#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]=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.

link

answered 23 Jan '16, 13:58

sahiji's gravatar image

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★

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

link

answered 26 Jan '16, 16:25

arpit728's gravatar image

2★arpit728
6831149
accept rate: 10%

edited 26 Jan '16, 16:30

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×14,809
×1,034
×282
×118

question asked: 14 Nov '15, 19:02

question was seen: 4,338 times

last updated: 26 Jan '16, 16:30