Python solution, easy to understand


  • 14
    B

    Easy to understand baseline solution (not fast though), memorization is used to prune the search space.

        def canIWin(self, maxChoosableInteger, desiredTotal):
            """
            :type maxChoosableInteger: int
            :type desiredTotal: int
            :rtype: bool
            """
            if (1 + maxChoosableInteger) * maxChoosableInteger/2 < desiredTotal:
                return False
            self.memo = {}
            return self.helper(range(1, maxChoosableInteger + 1), desiredTotal)
    
            
        def helper(self, nums, desiredTotal):
            
            hash = str(nums)
            if hash in self.memo:
                return self.memo[hash]
            
            if nums[-1] >= desiredTotal:
                return True
                
            for i in range(len(nums)):
                if not self.helper(nums[:i] + nums[i+1:], desiredTotal - nums[i]):
                    self.memo[hash]= True
                    return True
            self.memo[hash] = False
            return False

  • 0
    P

    @bugdx Thanks for the idea. easy to understand for beginners like me.


  • 0
    A
    This post is deleted!

  • 0
    S

    Nice. The second player's state is described by

    if not self.helper(nums[:i] + nums[i+1:], desiredTotal - nums[i]):
    

    and the conclusion of which is used to determine the state of the first player, a smart solution.


  • 0

    I don't understand the logic below. Does it imply that a player could no number in a round?

            if (1 + maxChoosableInteger) * maxChoosableInteger/2 < desiredTotal:
                return False
    

  • 0
    S

    @jedihy That means even the sum of all available numbers is still smaller than the target, so it is impossible to win.


  • 0

    @SNSN2033 but in such a situation, the second player cannot win as well?


  • 0

    This is my code. I did not have the extra condition before and it cannot pass for test case like 5, 50.

    class Solution(object):
        def canIWin(self, maxChoosableInteger, desiredTotal):
            """
            :type maxChoosableInteger: int
            :type desiredTotal: int
            :rtype: bool
            """
            def helper(pool, target, visited):
                if pool in visited:
                    return visited[pool]
                if target <= 0:
                    return False
                    
                mask = 0x01
                for i in xrange(0, maxChoosableInteger):
                    if pool & mask == 0:
                        newPool = pool | mask
                        if helper(newPool, target - (i + 1), visited) == False:
                            visited[pool] = True
                            return True
                    mask = mask << 1
                visited[pool] = False
                return False
    
            # extra condition
            if (1 + maxChoosableInteger) * (maxChoosableInteger / 2) < desiredTotal:
                return False
            # extra condition
            
            if desiredTotal == 0:
                return True
            pool = 0
            visited = {}
            return helper(pool, desiredTotal, visited)
    

  • 0
    S

    @jedihy No he can't. But this problem only asks us "whether we can make player 1 win".


  • 0

    @SNSN2033 I expected that the DFS procedure can automatically count this situation. But it seems that I am wrong. Every posted solution check this condition at the beginning.


  • 0

    Hi @bugdx ,
    The cache does not include the desiredTotal, do we need more test case or there is a reason that your solution works?
    For example, say (maxChoosableInteger is 5 and desiredTotal is 10) these two cached values would have the same result even though they are different:

    1. cache['1,3,5'], desiredTotal 4 (2, 4 used)
    2. cache['2,3,4'], desiredTotal 4 (1, 5 used)

  • 0
    L

    Thanks. I didn't understand the other's solutions. But I understand yours.


  • 2
    B

    Hi, @yang2007chun .
    The memory is used to store the visited <State, Result> pairs, where the State is just the encoding of the current state and the Result is win or loss for current player to move. It's useful because if we meet a state again we don't need to search for the result of the state. For your question, there will be many caches have the same result because there are just 2 results (w or l) but there are many more possible states.

    Also, I just used remaining numbers to encode the state for two reasons:

    1. we do not need to encode the information of which player to move because for given set of numbers, if the parity of current state is the same as initial state, it's first player's turn. Otherwise it's the second player's turn.
    2. we do not need to encode the desiredTotal because it's the same for all states. It's like if we need to encode a Chess board we just need a list of remaining pieces and their positions and we don't need the board size since it's always 8 x 8 for all states.

    Hope this post will be helpful.


  • 0
    S

    How do we prove this algorithm has time complexity O(2^N)?


  • 0

    @seekerwu70 said in Python solution, easy to understand:

    How do we prove this algorithm has time complexity O(2^N)?

    The value 2^N comes from the number of states in this game. Note that a state of the game is completely determined by the still available numbers in the pool, which is a subset of the initial pool [1, N], where N = maxChoosableInteger, and the number of subsets is exactly 2^N.

    With memorization during DFS, it guarantees that we solve each state (i.e., sub-problem) of the game at most once (note that we could early return from DFS if e.g., desiredTotal is significantly small compared to sum of [1, N]). You can image each state is a node if a binary tree, root is the initial state and leaf is the base case for DFS to return. For base case, we solve it in O(1) time, obviously. And the DFS just passed lower level results back to upper level until back to the root. So the total time is the total number of nodes in a binary tree with maximum depth N, i.e., O(2^N).

    I have a post below to further explain the definition of a game state if you are interested:
    10-liner concise C++ beat 98.4% recursive solution with early termination check, no helpers (detailed explanation)


  • 0

    There should be another case for early termination which should be checked:

    • if the sum of total from initial pool [1, max] is equal to the desired total, then return max%2 directly.

    In this case, the order to pick number is totally irrelevant. Whoever picks the last number from pool wins, so first player wins iff there are odd count of integers in the pool initially.


  • 0
    W

    20
    210

    index out of range for the above test case


  • 0
    S

    @bugdx can you please explain a logic a little bit?

    What does self.memo[hash] contain? Why is it set to True in this loop

                if not self.helper(nums[:i] + nums[i+1:], desiredTotal - nums[i]):
                    self.memo[hash]= True
                    return True
    

    Also, when we reach this condition - what does it mean?

            if nums[-1] >= desiredTotal:
                return True
    

    Here is my stab at understanding this solution -

        def canIWin(self, maxChoosableInteger, desiredTotal):
            """
            :type maxChoosableInteger: int
            :type desiredTotal: int
            :rtype: bool
            """
    
            # if 1+2+3+....+maxChoosableInteger < desiredTotal, then no player can ever acquire desiredTotal, returning False
            if (1 + maxChoosableInteger) * maxChoosableInteger/2 < desiredTotal:
                return False
            self.memo = {}
            return self.helper(range(1, maxChoosableInteger + 1), desiredTotal)
    
        def helper(self, nums, desiredTotal):
            """
            :param num:              available number pool
            :param desiredTotal:  desired total for victory
            """
            hash = str(nums)
            if hash in self.memo:
                return self.memo[hash] # if number pool is already evaluated, return memoized answer
            
            if nums[-1] >= desiredTotal:   # if available number pool has desiredTotal (at the end? why?), then we're winning (what about self.memo? why not setting True here?)
                return True
                
            for i in range(len(nums)):
                # pick each number in the number pool, and see using that if we attain desired Total
                if not self.helper(nums[:i] + nums[i+1:], desiredTotal - nums[i]): # whats the meaning of this condition?? why is this  ( "not" self.helper())?
                    self.memo[hash]= True
                    return True
            self.memo[hash] = False
            return False
    

  • 0
    K
    This post is deleted!

  • 0
    K

    @parvez.h.shaikh I try to go through the detail and now I think i kind of get it.

                if not self.helper(nums[:i] + nums[i+1:], desiredTotal - nums[i]):
                    self.memo[hash]= True
                    return True
    

    the dict memo contain the available number we can choose and the target number we want to get.

         self.helper(nums[:i] + nums[i+1:], desiredTotal - nums[i])
    

    represent the state of the second player and if there exist one state that he is guarantees to loose, the first player can force a win assuming both players play optimally.

         self.helper(nums[:i] + nums[i+1:], desiredTotal - nums[i])
    

    here I think it means at some condition both player can't win.
    like [4,5,6,7] target = 9: if the first player choose 6 or 7, both player can't win, however, here we use the second player's state to determine the first player's result, if we set state as false, as I explain above, the first player will think he can win definitely. So we set this state as True.
    I am not sure if I am correct and I am new to python.
    Please correct me if i am wrong.


Log in to reply
 

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