# CIRCLEGAME - Editorial

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

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) ,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

1 Like