CIRCLEGAME - Editorial

PROBLEM LINK:

Practice
Div-3 Contest
Div-2 Contest
Div-1 Contest

Author: Vishesh Saraswat
Tester: Istvan Nagy
Editorialist: Harshikaa Agrawal

Difficulty:

Easy

Prerequisites:

Modular Arithmetic, Dynamic Programming (not necessary)

Problem:

There are N elements in a circle, 1 to N. The following operations are done N−1 times

  • Start at the lowest index
  • From there M−1 steps are taken.
  • The index that’s reached is removed from the circle.

The last element remaining after N−1 operations is the winner. Given an M and X, Output the winner for 1 player, 2 players, 3 players, …, X players.

Explanation:

For N ≤ X, consider
f(N) = M \bmod N, if M \bmod N \neq 0
f(N) = N, if M \bmod N = 0

f(N) gives the position of the index that is reached (removed) after the operation occurs once out of the N-1 times. This means we can now compare it to when the game is played with N-1 players.

Consider winner from N players as g(N).

If g(N-1) < f(N), it means that g(N) would be the same as that of g(N-1). This is because if you remove a player that was ahead of g(N-1), the difference won’t affect the winner for a circle of N players.

However if g(N-1) \geq f(N), that means the circle has changed and g(N) will be g(N-1) + 1. We will take the base case as g(1) = 1 because 0 operations will be performed in this case.

Time complexity:

O(X) for each test case

Setter’s Solution

Setter's Solution
#include "bits/stdc++.h"
using namespace std;
/*
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
*/

#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sz(x) (int)(x).size()

using ll = long long;
const int mod = 1e9+7;

void solve(int tc) {
    int m, x;
    cin >> m >> x;
    vector<int> ans(x+1);
    auto get = [=] (int num) {
        if (m%num==0)
            return num;
        return m%num;
    };
    ans[1] = get(1);
    for (int i = 2; i <= x; ++i)
        ans[i] = (get(i) > ans[i-1] ? ans[i-1] : ans[i-1] + 1);
    for (int i = 1; i <= x; ++i)
        cout << ans[i] << " ";
    cout << '\n';
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int tc = 1;
    cin >> tc;
    for (int i = 1; i <= tc; ++i) solve(i);
    return 0;
}

Tester’s Solution

Tester's Solution
#include <iostream>
#include <algorithm>
#include <string>
#include <cassert>
#include <vector>
using namespace std;

#ifdef HOME
#define NOMINMAX
#include <windows.h>
#endif

long long readInt(long long l, long long r, char endd) {
	long long x = 0;
	int cnt = 0;
	int fi = -1;
	bool is_neg = false;
	while (true) {
		char g = getchar();
		if (g == '-') {
			assert(fi == -1);
			is_neg = true;
			continue;
		}
		if ('0' <= g && g <= '9') {
			x *= 10;
			x += g - '0';
			if (cnt == 0) {
				fi = g - '0';
			}
			cnt++;
			assert(fi != 0 || cnt == 1);
			assert(fi != 0 || is_neg == false);

			assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
		}
		else if (g == endd) {
			assert(cnt > 0);
			if (is_neg) {
				x = -x;
			}
			assert(l <= x && x <= r);
			return x;
		}
		else {
			//assert(false);
		}
	}
}

string readString(int l, int r, char endd) {
	string ret = "";
	int cnt = 0;
	while (true) {
		char g = getchar();
		assert(g != -1);
		if (g == endd) {
			break;
		}
		cnt++;
		ret += g;
	}
	assert(l <= cnt && cnt <= r);
	return ret;
}
long long readIntSp(long long l, long long r) {
	return readInt(l, r, ' ');
}
long long readIntLn(long long l, long long r) {
	return readInt(l, r, '\n');
}
string readStringLn(int l, int r) {
	return readString(l, r, '\n');
}
string readStringSp(int l, int r) {
	return readString(l, r, ' ');
}

int main() {
#ifdef HOME
	if (IsDebuggerPresent())
	{
		freopen("../in.txt", "rb", stdin);
		freopen("../out.txt", "wb", stdout);
	}
#endif
	int T = readIntLn(1, 1'000);
	int sumX = 0;
	for (int tc = 0; tc < T; ++tc)
	{
		int M = readIntSp(1, 1'000'000'000);
		int X = readIntLn(1, 10'000);
		sumX += X;
		int lastWinner = 1;
		printf("1 ");
		for (int N = 2; N <= X; ++N)
		{
			int first = M%N;
			if (first == 0)
				first = N;
			if (first <= lastWinner)
				lastWinner++;
			printf("%d ", lastWinner);
		}
		printf("\n");
	}
	assert(sumX <= 500'000);
	assert(getchar() == -1);
}

Editorialist’s solution:

Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

int main() {
int t;
cin>>t;
while(t--)
{
   int m, x;
   cin>>m>>x;
   int ans[x+1];
   ans[1] = 1;
   if(x > 1)
   {
      for(int i = 2; i <= x; i++)
      {
          int temp;
          if(m%i != 0)
          {
              temp = m%i;
          }
          else
          {
              temp = x;
          }
         
          if(temp > ans[i-1])
          {
              ans[i] = ans[i-1];
          }
     
          else
          {
              ans[i] = ans[i-1]+1;
          }
      }
     
   }
   
   for(int i = 1; i <= x; i++)
   {
       cout<<ans[i]<<" ";
   }
   cout<<"\n";
}
return 0;
}
10 Likes

can anyone say where my code is failing?

#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t–){
int m,n;
cin>>m>>n;
if(m==1){
for(int i=1;i<=n;i++){
cout<<n<<" “;
}
cout<<endl;
}
else if(m==2){
for(int i=1;i<=n;i++){
cout<<1<<” “;
}
cout<<endl;
}
else if(m%2!=0){
for(int i=1;i<=n;i++){
if(i<=m-1){
cout<<i<<” “;
}
else{
cout<<m-1<<” “;
}
}
cout<<endl;
}
else{
for(int i=1;i<=n;i++){
if(i<=m-2){
cout<<1<<” “;
}
else{
cout<<2<<” ";
}
}
cout<<endl;
}
}
}

2 Likes

It is like a modified version of the famous josephus problem ?

I was unable to handle the edge case when m%n == 0. Hehe. Nice problem

This is my solution, not sure where I made a mistake… any corrections would be appreciated

#include <bits/stdc++.h>

using namespace std;

void solve(){
	int64_t n,x;
	cin >> n >> x;
	if(n - 1 == 0){
		for(int i = 0;i<x;++i){
			cout << i + 1;
			if(i != x - 1)cout << " ";
		}
	}
	else if(n-1 == 1){
		for(int i = 0;i<x;++i){
			cout << 1;
			if(i != x - 1)cout << " ";
		}
	}
	else if((n-1)&1 == 1 && n != 1){
		for(int i = 1;i<=x;++i){
			if(i < n-1){
				cout << 1;
			}
			else{
				cout << 2;
			}
			if(i != x)cout << " ";
		}
	}
	else{
		for(int i = 1;i<=x;++i){
			if(i < n){
				cout << i;
			}
			else{
				cout << n-1;
			}
			if(i != x)cout << " ";
		}
	}
	cout << "\n";	
}

int main(){
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL);
	int64_t test;
	cin >> test;
	while(test--){
		solve();
	}
}

@s_h_a_z_a_m your answer will come correct for m=even but for cases like m=9 x=11 its wrong
your output - 1 2 3 4 5 6 7 8 8 8 8
expected - 1 2 2 3 3 4 5 6 6 6 6

2 Likes

Nice problem statement !!

Here is a thought process :

lets consider a small case where we have 7 person and m is 4

  • For 1 person ans = 1
  • For 2 person ans = 2

Now lets observe closely for 3
-After a single operation, we see that 2 is eliminated.
-Now we have 2 persons left 1,3 and we know that ans[2] = 2 but here since 2 was eliminated the person ahead of 2 will win.

  • For 3 person ans = 3

Now for 4 persons
-After a single operation, we see that 1 is eliminated.
-Now we have 3 persons left 2,3,4 and we know that ans[3] = 3 if started from 1 since we start from 2 now that answer should be 3+1 = 4

  • For 4 person ans = 4

Now for 5 person
-After a single operation, we see that 5 is eliminated.
-Now we have 1,2,3,4 left and this is exactly same as 4 person left. so the answer is nothing but same as answer that we had 4.

  • For 5 person ans = 4

  • Now for all the cases we first need to find the first person to be eliminated which can be done via modulo;

first_eliminated = m%x + 1
Now just try to find a how our current answer is influenced by the first person to be eliminated and the remaining people.

Hope this helps.

13 Likes

https://www.codechef.com/viewsolution/56316819
Solution using pbds(ordered_set) :sweat_smile:,might be overkill.
but setter solution is more clean.

1 Like

This really clears it up for me. The setters did a good job setting a nice problem with a neat little editorial. However, an example always helps.

2 Likes

#include
using namespace std;

int main() {
int t;
cin>>t;
while(t–)
{
long long int m , x;
cin>>m>>x;
if(m==1)
{
for (int i = 0; i < x; i++) {
cout<<i+1<<" ";
}
}
else if(m==2)
for (int i = 0; i < x; i++) {
cout<<"1 ";
}
else if(m%2==0)
{
for (int i = 0; i < x; i++) {
if((i+1)<=(m-2))
cout<<"1 ";
else
cout<<"2 “;
}
}
else
{ long long int p=1;
for (int i = 0; i < x; i++) {
if((i+1)<(m-1))
cout<<p++<<” “;
else
cout<<p<<” ";
}
}
cout<<endl;
}

return 0;

}
why im getting wrong answer , can anybody explain

DP solution in java-
https://www.codechef.com/viewsolution/56358486

bro can u paste yr code link.

Here you go - Link.

Thanks Mayank, exactly what I was looking for.

nice explanation. one thing I guess we are moving m-1 times in a turn, while in the explanation we seem to be moving m times clockwise.

1 Like

really how do you know that?

pbds meaning?

policy based data structure(ordered_set)
https://www.geeksforgeeks.org/ordered-set-gnu-c-pbds/

1 Like

thanks bro :slight_smile:

1 Like