What is the approach to this problem?

[sk123]

https://www.codechef.com/MAY19B/problems/MATCHS

Ari and Rich are playing a pretty confusing game. Here are the rules of the game:

The game is played with two piles of matches. Initially, the first pile contains N matches and the second one contains M matches.
The players alternate turns; Ari plays first.
On each turn, the current player must choose one pile and remove a positive number of matches (not exceeding the current number of matches on that pile) from it.
It is only allowed to remove X matches from a pile if the number of matches in the other pile divides X.
The player that takes the last match from any pile wins.
It can be proved that as long as both piles are non-empty, there is always at least one valid move, so the game must end by emptying some pile. Both Ari and Rich play optimally. Determine the winner of the game.

Example Input
5
1 1
2 2
1 3
155 47
6 4

Example Output
Ari
Ari
Ari
Ari
Rich

I tried but only first testcase runs rest are all WA.
I am just asking the hint to this problem, not the code. Please help me out.

[salem c]

Yes, you begin with pencil and paper, and understand the nature of the problem.

This is an exercise in maths (specifically factorisation) as much as it is about programming.

So make sure you really understand the maths first.

[STD8C542]

// deleted //

[gauri33]

I got stuck for 3 days still not getting the right logic behind this question.My approach is similar than yours but in the loop i am doing n=n-m(n/m) or m=m-n(m/n) rather than taking mod.Please help

[salem c]

> I tried but only first testcase runs rest are all WA.
What's WA?

From the contest page
Constraints
1≤T≤10⁵
1≤N,M≤10¹⁸

Time Limit: 1 secs

[George P]

"What is the approach to this problem?"

That is kinda the point to having a code challenge, doing the work yourself. Cheating by getting all the answers from others doesn't help you to learn to code.

[notacoder]

but you can tell the way we should think about the problem

[nitesh111]

can anyone tell the sequence of moves for the input n = 197 m = 47
i am confused a lot

[neutralove]

ONE possible sequence is :

197 47
56 47 ( Ari )
9 47 ( Rich )
9 2 ( Ari )
1 2 ( Rich )
1 0 ( Ari )

So Ari wins. Note that there are more possible sequences resulting in the correct answer.

[nitesh111]

@neutralove why you are removing only 141 in first step
when you can remove 188..??

[neutralove]

Because that is the best choice, considering they both play optimally.
If Ari makes the choice to remove 188 and afterwards both of the players continue playing optimally the sequence will be :

197 47
9 47 ( Ari )
9 2 ( Rich )
1 2 ( Ari )
1 0 ( Rich )

Rich will win. However, Ari can't make that mistake, so he will win no matter what.
As I said, there are more possible answers, but I gave you the one with the minimal steps.

[dutch]

Your solution exhibits non-optimal play since you have Rich playing 1,2 when he could have instead played 3,2 and won the game. However, Ari can win by playing a little differently earlier.

197 47 

Ari  56 47
Rich  9 47    (forced)
Ari   9 11
Rich  9  2    (forced)
Ari   3  2
Rich  1  2    (forced)
Ari   1  0

[neutralove]

Indeed, my mistake.

[anup30]

>

What's WA?

Wrong Answer.

[Dum]

@anup30
yeah

[anup30]

well, i'm now trying the problem. this is how it looks at halfway. more code & some fix have to be done.

//https://www.codechef.com/MAY19B/problems/MATCHS
#include <iostream>
#include <vector>
using namespace std;

char call(int s, int b, char c){
	if(s==0) return (c=='A'?'A':'R');		
	//if(s==1) return (c=='A'?'R':'A');	
	vector<int> send_list;
	int mod=b%s;
	int rem=b/s;
	for (int i=0; i<rem; i++) send_list.push_back(mod+mod*i);
	mod=send_list.size();//reuse the variable
	for(int i=0; i<mod; i++){
		if(s<send_list[i]){
			cout<<c << " sends s,b= " << s << ", "<<send_list[i]  <<"\n";
			call(s,send_list[i],c=='A'?'R':'A');
		} 
		else{
			cout<<c << " sends s,B= " << send_list[i] << ", "<< s <<"\n";
			call(send_list[i],s,c=='A'?'R':'A');
		} 
	}		
//return 'M';	
}

int main(){	
	int s=47;
	int b=197;
	char c='A'; //sender
	cout << s << ", " << b << "\n";
	cout<< call(s,b,c);	
	
return 0;
}

[closed account 987k216C]

/*This is my approach, which is just hitting all the cases... it's giving AC for 1st subtask, but TLE for rest of the cases... can anyone tell me, Am i right in my approach, or should i rewrite the code in different strategy */
#include <bits/stdc++.h>
using namespace std;

#define pp long long int

bool do_me(pp n,pp m,bool x)
{
if(n%m==0)
return x;

if(x==1)
{
if(n/m>1)
return(do_me(m,n%m,x)|do_me(m,n%m,!x));
return(do_me(m,n%m,!x));
}

if(n/m>1)
return(do_me(m,n%m,x)&do_me(m,n%m,!x));
return(do_me(m,n%m,!x));
}

int main() {
// your code goes here
pp t;
cin>>t;

while(t--)
{
pp n,m;
cin>>n>>m;

if(do_me(max(n,m),min(n,m),1))
cout<<"Ari"<<endl;
else
cout<<"Rich"<<endl;
}
return 0;
}

[salem c]

@rahulrawat09
Use the [code][/code] tags when posting code.

#include <bits/stdc++.h>
using namespace std;

#define pp long long int

bool do_me(pp n, pp m, bool x)
{
  if (n % m == 0)
    return x;

  if (x == 1) {
    if (n / m > 1)
      return (do_me(m, n % m, x) | do_me(m, n % m, !x));
    return (do_me(m, n % m, !x));
  }

  if (n / m > 1)
    return (do_me(m, n % m, x) & do_me(m, n % m, !x));
  return (do_me(m, n % m, !x));
}

int main()
{
// your code goes here
  pp t;
  cin >> t;

  while (t--) {
    pp n, m;
    cin >> n >> m;

    if (do_me(max(n, m), min(n, m), 1))
      cout << "Ari" << endl;
    else
      cout << "Rich" << endl;
  }
  return 0;
}

> Am i right in my approach, or should i rewrite the code in different strategy
TLE (Time Limit Exceeded) really does mean your approach is wrong.

Codechef problems typically have a simple "brute force" solution which is easy to think of, and passes the smaller test cases, but scales badly to the larger test cases.

Then there is the really smart solution which requires a good deal of thinking on the part of the programmer, long before you get anywhere near opening your IDE and typing "int main".

[closed account 987k216C]

Did you solved this problem? @salem

[anup30]

salem c wrote:

Codechef problems typically have a simple "brute force" solution which is easy to think of

even the brute force solutions are not easy(unless you are a genius).