WA in Game Theory 1

#1

Ques: https://hack.codingblocks.com/contests/c/547/1151
Code:
https://ide.codingblocks.com/s/55520

#2

I think , Grundy Topic is not clear to you. First of all, go through the videos again and try building your logics of how to solve Grundy Questions.
FOR 1 Pile:
if Grundy (n)==0 First Loose otherwise wins
FOR N piles having m1,m2,… stones
if Grundy(m1) ^ Grundy(m2) ^ Grundy(m3),… !=0 then First wins otherwise First loose.
and try to solve the questions again.

#3

I fixed the code and my confusion but now I am getting TLE
https://ide.codingblocks.com/s/55633

#4

you are not using optimized way to find divisors.
use MINSIEVE to find the divisors in O(1)

cccc
cccc1227×817 27.4 KB

#5


find the above code in this link

#6

but wouldn’t it only do Prime factorisation, while in the question all divisors are required.

#7

yes you are right. Let me check the code.

#8

in last you are calculating Grundy(m) n times line no 159
Use the property of xor
m^m^m^m…even times ans=0 and odd times ans=m.
to solve in O(1) for n stones

#9

https://ide.codingblocks.com/s/55641
Now WA
:confused:

#10

TLE toh khatam hua :stuck_out_tongue:

#11

Can you elaborate what is remove function is doing in your logic?

#12

Its just lying there, i replaced vector with a set to take care of repeated divisors :sweat_smile:

#13

I submitted the wrong code
the actual one is https://ide.codingblocks.com/s/55642
But surprise, still WA

#14

wrong Test case:
1
1 2 n=1 and m=2
answer is 1
your answer is 2

1 Like
#15

finally AC.
I was not putting 1 in the divisors set. Inserted 1 and AC
Thank you for ur time. :grin:

#16

hoof…Finally U got it. Cheers.
Ab tune iske alawa do doubts or daale h. ek baar unke code dobara check karle and agar submit nh hote toh we will debug.

1 Like
#17

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll table[1000004];

unordered_set calculatedivisors(long long n)
{
unordered_set tt;

for(ll i=2;i*i<=n;i++)
{
if(n%i==0)
{
    if(n/i!=i)
    tt.insert(n/i);
    tt.insert(i);
}
}
tt.insert(1);

return tt;

}
ll calculatemex(unordered_set Set)
{
ll Mex = 0;

while (Set.find(Mex) != Set.end())
	Mex++;

return (Mex);

}
int calculategrundy(int n)
{
if(n==0)
return 0;
if(n==1)
return 0;
if(table[n]!=0)
return table[n];
unordered_set s=calculatedivisors(n);
unordered_set ss;
for(auto i=s.begin();i!=s.end();i++)
{
ll x=*i;
ss.insert(calculategrundy(x));

 }
 ll xx=calculatemex(ss);
table[n]=xx;
return xx;

}

int main()
{ int t;
cin>>t;
while(t–)
{ memset(table,0,sizeof(table));

int n,m;
cin>>n>>m;
 ll ans=calculategrundy(m);
 if(n%2==0)
 cout<<"2"<<endl;
 else
 {
      if(ans==0)
	  cout<<"2"<<endl;
	  else
	  cout<<"1"<<endl;
 }

}
return 0;
}