In MAY19B contest, in the second question MATCHS, I got WA on all test cases except test case #0. Did I miss out on something in my code? Here’s my solution: CodeChef: Practical coding for everyone.
1 Like
What was your approach, It wil be better for us to debug your code if you will share your approach too.
The server is down too, so cant open the link u provided. 
untill the server starts working, Come on do share your approach
I would find out the larger number of 2 and subtract the largest multiple of the smaller number from it. Then I’d repeat it until either of the two numbers is 0. I’d keep a count of how many times the whole procedure occurred. Since Ari starts first, if the count is odd, Ari wins, else Rich wins.
while(t--)
{
ulli n, m;
cin>>n>>m;
ulli count = 0;
while (n>0 && m>0)
{
++count;
if (max(n, m) == n)
n -= ((n/m) * m);
else
m -= ((m/n) * n);
}
if (count%2 == 0)
cout<<"Rich"<<endl;
else
cout<<"Ari"<<endl;
}Yes this is the place where you did the mistake its not always the largest multiple of the smallest number which will be removed from the larger one. Both of them will try to win and the player who gets (n/m)>1 first will win the match for sure
where n is the larger number and m is the smaller number.
Can you please elaborate a bit more on it, I’m not quite getting it.
I also had this problem. according to your logic you must have thought that we do not always remove the largest integer K such that k = m / n (with m greater than n). but that’s not always the case. in some cases it is better to withdraw less.
look at that Nim - Wikipedia
use cout<<fixed<<setprecision(1)<<res<<endl;
where res is your result.
Because it is given in the problem the absolute error must be less then 10^-6.
You are probably talking about WTBTR and not MATCHS.
Yes Let me expalin this with a case
9 88
according to you
ari-------rich
9,7-------7,2
2,1-------1,0
Rich wins accoding to your code
Now according to my code
ari-------rich
9,16-------9,7
7,2-------2,1
1,0 --------------------And ari wins the game.
1 Like
One problem though. Rich would remove 4 matches instead of 6 resulting in 3,2 instead of 2,1 since that would be the optimal choice for Rich.
In example… Rich… 7,2…means they can take pile from either one of the two piles block…
check case 10,4
if ari takes 8 out -> 2,4 now rich can take 4 out and wins
BUT ARI CAN WIN IF PLAYED OPTIMALLY
ari can take out 4 in first turn -> 6,4
now rich has only one move ie to take 4 out of 6 -> 2,4
now ari can remove 4 from second pile and win
i think your approach will say rich will win
1 Like
Find forced and control moves
For example
6,4 only move that can be made is to subtract 4 from 6, looks like a forced move.
13,4 is a control move
A player in this position can take other pile in further move or give it to other player and make the next move forced.
For example if Ari gets 13,4 there are two choices:-
- 13,4 to 5,4 Ari , 5,4 to 1,4 Rich(forced), then Ari gets next move
- 13,4 to 1,4 Ari , Rich gets next move(forced, else Rich gets control and that can’t happen if Ari wants to win)
By this observation the player who gets the control move wins.
1 Like
in my code there is some mistake but output is what you have got in this testcase
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t --> 0)
{
long long int n,m,c=1,f=0,f1;
cin>>n>>m;
if(n==m){
cout<<“Ari\n”;
c=-1;}
else{
while(true)
{
if(n<m)
{
f=m/n;
f1=f;
//cout<<“f val=”<<f<<endl;
if(m%n!=1)
{
m=m%n;
//cout<<“m val=”<<m<<endl;
if(m==0)
break;
c++;
}
else if(m%n==1){
// cout<<“valur check=”<<m-((–f)*n)<<endl;
if(f>1){
m=m-((–f)*n);}
else
m=m%n;//cout<<“m in else if val=”<<m<<endl;
//cout<<“m val=”<<m<<endl;
if(m==0)
break;
c++;
}
}
else if(m<n)
{
f=n/m;
// cout<<“f val=”<<f<<endl;
if(n%m!=1)
{
n=n%m;
//cout<<“when m is small n=”<<n<<endl;
//cout<<“n val=”<<n<<endl;
if(n==0)
break;
c++;
}
else if(n%m==1){
if(f>1)
n=n-((–f)*m);
else
n=n%m;
// cout<<“n val=”<<n<<endl;
if(n==0)
break;
c++;
}
}
}
}
if(c!=-1&&c%2==0)
cout<<“Rich\n”;
else if(c!=-1)
cout<<“Ari\n”;
}
return 0;
}
how we get to know it is the right move that we are taking at that position .in my code i try to force rich to take only one factor value and remaining are taken by Ari so if at last only 1 factor remains the one who will take it will win.
like 22 ,4 -> 8,7 -> 1,7 Ari wins.
How do we know what the controlled and forced moves are?
Sry for late reply.
Firstly a move in this question is removing X stones where X meets the requirements.
A move where a user has no option but only one choice is forced move in general.
Here at 6,4 you can only remove only 4 stones from pile of 6 whether the user likes it or not.
A move where a user has multiple choices to make that move is control move in general.
Here at 13,4 user can choose to either move 4, 8 or 12 stones from pile of 13 as these are divisible by 4.
If I got a control move I would try not to give my opponent a lot of options for futher moves using this move i.e. all moves of my opponent are forced and all control moves are mine if I get the first control move.
You can practice another problem like this
very similar