• [deleted]
    + 0 comments
    int mex(set<int>mset)
    {
        int m=0;
        while(mset.find(m)!=mset.end())
        m++;
        return m;
    }
    
    
    int grundy(string &s,int ci)
    {
        //cout<<s<<endl;
        if(dp.find(s)!=dp.end())
        {
            return dp[s];
        }
        if (ci==0) {
            dp[s] = 0;
            string t = s;
            //cout<<s<<endl;
            //reverse(s.begin(), s.end());
            //dp[t] = 0;
            return 0;
            }
        if (ci == 1) {
          dp[s] = 1;
          string t = s;
          //cout<<s<<endl;
          //reverse(s.begin(), s.end());
          //dp[t] = 1;
          return 1;
        }
        int n=s.length();
        set<int>mset;
        for(int i=0;i<n;i++)
        {
            if(s[i]=='X')
                continue;
            if (s[i] == 'I') {
              s[i] = 'X';
              int ans = 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';
                int ans=grundy(s,ci-2);
                mset.insert(ans);
                s[i]='I';
                s[i+1]='I';
            }
            
        }
        dp[s]=mex(mset);
        return dp[s];
    }
    
    
    
    string isWinning(int n, string config) {
        /*
         * Return WIN or LOSE depending on whether you will win
         */
        int c=count(config.begin(),config.end(),'I');
        bool ans=(bool)grundy(config,c);
        vector<string>arr(2);
        arr[0]="LOSE";
        arr[1]="WIN";
        return arr[ans];
    }
    

    I am using a game theory based approach here but still getting timed out. Could someone please help ?