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