We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
intmex(set<int>mset){intm=0;while(mset.find(m)!=mset.end())m++;returnm;}intgrundy(string&s,intci){//cout<<s<<endl;if(dp.find(s)!=dp.end()){returndp[s];}if(ci==0){dp[s]=0;stringt=s;//cout<<s<<endl;//reverse(s.begin(), s.end());//dp[t] = 0;return0;}if(ci==1){dp[s]=1;stringt=s;//cout<<s<<endl;//reverse(s.begin(), s.end());//dp[t] = 1;return1;}intn=s.length();set<int>mset;for(inti=0;i<n;i++){if(s[i]=='X')continue;if(s[i]=='I'){s[i]='X';intans=grundy(s,ci-1);mset.insert(ans);s[i]='I';//cout<<"BACK TO "<<s<<endl;}if((i+1)<n&&s[i]=='I'&&s[i+1]=='I'){s[i]='X';s[i+1]='X';intans=grundy(s,ci-2);mset.insert(ans);s[i]='I';s[i+1]='I';}}dp[s]=mex(mset);returndp[s];}stringisWinning(intn,stringconfig){/* * Return WIN or LOSE depending on whether you will win */intc=count(config.begin(),config.end(),'I');boolans=(bool)grundy(config,c);vector<string>arr(2);arr[0]="LOSE";arr[1]="WIN";returnarr[ans];}
I am using a game theory based approach here but still getting timed out. Could someone please help ?
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Bowling Pins
You are viewing a single comment's thread. Return to all comments →
I am using a game theory based approach here but still getting timed out. Could someone please help ?