Not able to pass this problem.

[samarth123]

Chef arranges the N robots in a row, in the (increasing) order of their indices. Then, he chooses the first M robots and moves them to the end of the queue. Now, Chef goes to the robot at the first position in the row
and hands it one cake. He then notes this robot's index (say k) in his notebook, and goes to the kth position
in the row. If the robot at this position does not have a cake, he give him one cake, notes his index in his
notebook, and continues the same process. If a robot visited by Chef already has a cake with it, then he
stops moving and the cake assignment process is stopped.
Chef will be satisfied if all robots have a cake in the end. In order to prepare the kitchen staff for Chef's wrath
(or happiness :) ), you must find out if he will be satisfied or not? If not, you have to find out how much robots
have a cake, so that the kitchen staff can prepare themselves accordingly.
Input
The first line of input contains a single integer T denoting the number of test cases.
The single line of each test cases contains two space separated integers N and M.
Output
For each of the T test cases, output a single line:
If all N robots have a cake, output "Yes" (without quotes).
Otherwise, output "No" (without quotes) followed by a space and the number of robots which have a
cake.
Constraints and Subtasks
1 ≤ T ≤ 10
0 ≤ M < N
Subtask 1: 25 points
1 ≤ N ≤ 10^5
Subtask 3: 75 points
1 ≤ N ≤ 10^9

#include<iostream>
using namespace std;
int main()
{
	int t,n,m,k,c;
	cin>>t;
	while(t--)
	{
		cin>>n>>m;
		int a[n]={0};
		k=m;
		a[k]=1;
		c=2*k; 
		if(c==n)
		{
			c=c-n;
		}
		if(c>n)
		{
			c=c-n-1;
		}
		int flag=1;
		while(a[c]==0)
		{
			a[c]=1;
			flag=flag+1;
			c=c+k;
			if(c==n)
			{
				c=c-n;
			}
			if(c>n)
			{
				c=c-n-1;
			}
			if(a[c]==1)
			{
				break;
			}
			else continue;
		}
		if(flag==n)
		{
			cout<<"Yes\n";
		}
		else cout<<"No "<<flag<<"\n";
	}
}

In the problem i am trying to give the cake to each robot by assigning the value 1 to each element of the array.If the element of the array is already assigned the value 1 then the loops breaks..and then i ckeck that if every element of the array is 1 then answer is "Yes"
else "No".

[Duthomhas]

I don't think the assignment is worded very carefully, particularly as there is a possible fencepost issue, but this is how I read it:

You are being asked to use modulo operations to fill an array (there is no 'queue' involved). Also, for clarity, we are going to do this without "moving" anything.

For simplicity, let's say N=10 and M=2.

    1 2 3 4 5 6 7 8 9 10
        k

That is, k=3 (it is the index of the first robot after the first M robots.

Here is the fencepost problem: you are now asked to go to the "kth" position. If the robots are arranged thus (had they been moved, then the kth position is:

    3 4 5 6 7 8 9 10 1 2
        k

Robot 5. Not robot 6. That said, your professor might expect you to select robot six -- you should ask for clarification. I will continue with the assumption that robot 5 is the correct choice. (And again, I've numbered the robots starting with one, not zero, so again, you need to ask your professor for clarification.)

As it is, the exact details don't matter, but the process does. As long as you can correctly compute the next k you are good.

So, now we have:

    1 2 3 4 5 6 7 8 9 10
        *   k

That is, robots 3 and 5 now have a cupcake. Our next robot is going to be, according to our (possibly incorrect) assumptions above, k+k-1 == 5+5-1 == 9:

    1 2 3 4 5 6 7 8 9 10
        *   *       k

And again, 9+9-1=17. We don't have 17 robots, so we have to wrap around to the first robot. (This part was left out of your assignment's wording.)

Since there are ten robots, you can use modular arithmetic -- that is, find the remainder: 17%10 == 7. Robot 7 is the next kth robot.

    1 2 3 4 5 6 7 8 9 10
        *   *   k   *

Now for the interesting part. We again update k as: k=7+7-1=13→3:

    1 2 3 4 5 6 7 8 9 10
        *   *   *   *
        k

Robot 3 already has a cupcake. (Chef will be so disappointed! -- Irrelevant info!) Only four of the ten robots get cupcakes.

This is essentially a sieve algorithm.

Now, the way you implement it is not too important. Using an array is a good idea. Have an array of robots, numbered by their index (as all array elements are), and the array values are simply whether or not the element (the robot) has been visited (has a cupcake).

bool robots[10] = { false };
...

Keep in mind that you don't have to have exactly as many robots as the size of your array. You can have a big array but pretend it is smaller:

bool robots[100] = { false };
int num_robots = 10;
...

Write a loop which only terminates if robot k has a cupcake:

k = M+1;  // M <= num_robots
while (!robots[k-1])
{
  k = ...
}

Again, the above was written with k = 1, 2, 3...
If you use the C++ convention of indexing arrays from 0, then your robots will also be indexed from 0:

k = M;  // M < num_robots
while (!robots[k])
{
  k = ...
}

When you are done, all you need to do is count the number of robots that have a cupcake.

Hope this helps.

[samarth123]

@Duoas

I understood the whole concept except this line..
"Keep in mind that you don't have to have exactly as many robots as the size of your array. You can have a big array but pretend it is smaller:"
What does this mean??

[mutexe]

he/she means you can test your logic with a much smaller number of robots.

[samarth123]

#include<iostream>
using namespace std;
int main()
{
	int t,n,m,k;
	
	cin>>t;
	while(t--)
	{
                int a[100000]={0};
		cin>>n>>m;
		k=m;
		int count=0;
		while(a[k]==0)
		{
			a[k]++;
			count++;
			k=2*k;
			if(k>=n)
			{
				k=k%n;
			}
		}
		if(count==n)
		{
			cout<<"Yes\n";
		}
		else cout<<"No "<<count<<"\n";
	}
	return 0;
} 

well i made my code according to the above logic but i am unable to get the correct answer for the code.

[Duthomhas]

Chef can never feed all his robots, according to the instructions given you, unless he has exactly two robots and M = 1.

Now that I am looking at it again, I am sure that we have misunderstood something about the assignment. Have you asked your professor for clarification? Do you have examples of successful N>2?

[cire]

well i made my code according to the above logic but i am unable to get the correct answer for the code.

Your calculation of k is not correct. (And neither is Duoas' above. The calculation of k is dependent on the value of M and Duoas lost track of that somewheres.)

For simplicity, let's say N=10 and M=2.

I'm going to go out on a limb here and say that "indices" refer to the values of the array indexes for each index in the array, so numbering should begin at 0.

The original row of robots looks like:

 0 1 2 3 4 5 6 7 8 9

After the M robots are moved, the indices of the original row follow this pattern:

 2 3 4 5 6 7 8 9 0 1

(So note that for index 0 in the modified row of robots, the robot is identified as having the index 2 in the original unmodified row.)

You begin with the first robot in the modified row (k is 0).

 k 
 0 1 2 3 4 5 6 7 8 9
 *

And if we juxtapose the indexes of the robots in the original row:

 0 1 2 3 4 5 6 7 8 9 
 *
 |
 2 3 4 5 6 7 8 9 0 1 

We can see that k will be 2, so our updated row of robots looks like:

     k
 0 1 2 3 4 5 6 7 8 9
 *   *
     |
 2 3 4 5 6 7 8 9 0 1

And then k will be 4:

         k
 0 1 2 3 4 5 6 7 8 9
 *   *   *
         |
 2 3 4 5 6 7 8 9 0 1

And then k will be 6, 8, and wrap around to 0 again which already has a cupcake.

You could use two arrays and do this literally as described but if one can see the relationship between M and k that isn't necessary.

The next value of k is simply (k + M)%N when you're dealing with the modified row of robots.

[Duthomhas]

Ah, you are right. I had misread the assignment that Chef would rearrange the robots at each interval, but he only does it once.

Thanks!

[ne555]

For the small testcase (n<1e5) you can simulate, but for the big one (n<1e9) you'll probably exceed the time limit.
Try to find first a relationship between N and M that'll tell you if you can fill the whole array.

Take by instance N=6, you can solve it with M={1,5} but fail with M={0,2,3,4}