why we do not need to differentiate two players?


  • 0
    S

    After seeing some code in discussion I came up with the following code and passed the judge. My question is: why we do not need to differentiate two players? That is, when we mark the elements in the map to true or false, how do we know it is true/false for the first or second player? Why it does not matter?

    class Solution {
    private:
        bool wins(unordered_map<int, bool> &map, int used, int maxChoosableInteger, int target)
        {
            // if the number combination have been calculated, return the result
            if (map[used]) return map[used];
            // if the number combination have not been calculated
            // if used is 10100, then 2, 4 have been chosen, while 1,3 are not
            // so we start from the beginning, if the number has not been chosen, then we examine this number
            for (int i = 1; i <= maxChoosableInteger; ++i)
            {
                int mask = 1 << i;
                // 1. if this number >= the target, then of course wins
                // 2. if this number < target, and we choose this number, then the choice is passed to the second player
                //    only when second player loses can the first player wins
                if ((mask & used) == 0 && (i >= target || !wins(map, mask | used, maxChoosableInteger, target - i)))
                {
                    // for the above situations, the first player wins, and we can mark the map
                    // we don't need to differentiate two players
                    return map[used] = true;
                }
            }
            return  map[used] = false;
        }
        
    public:
        // without pruning O(n!)
        // with pruning O(2^n)
        bool canIWin(int maxChoosableInteger, int desiredTotal) 
        {
            if (((1 + maxChoosableInteger) * maxChoosableInteger / 2) < desiredTotal) return false;
            unordered_map<int, bool> map;
            return wins(map, 0, maxChoosableInteger, desiredTotal);
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.