Explanation of the question


  • 6
    D

    I did not understand what the question was asking exactly during the contest. I came up with multiple solutions based on what I thought was being asked, but they were all incorrect. Looks like I finally understood it. I wanted to clarify the question for people who may be confused like me.

    The setup should be easy to understand. p1 and p2 take turns in picking a number from the input array, either the first item or the last item. When an item is picked by one of the player, that item cannot be used anymore; you can imagine it being removed from the array.

    What made me confused was the part "... predict whether player 1 is the winner. You can assume each player plays to maximize his score." I was not sure what maximizing the score meant. Here is what it means.

    Let's say the initial array is [1, 5, 2]. It's p1's turn. p1 will pick either 1 or 2, but it wants to make sure that whichever one he picks will maximize his gain at the end. What if p1 picks 1? Now the array is [5, 2] and it's p2's turn to pick. p2 looks at the current array and thinks about how to maximize his gain at the end. Obviously, picking 5 will maximize his gains. So, p2 will pick 5, leaving 2 for p1. Resulting scores for p1 and p2 are 3 and 5 respectively. This one did not work out for p1.

    What if p1 picks 2 at the beginning? Then the array becomes [1, 5]. Again, p2 looks at the current array and thinks about how to maximize his gain at the end. Picking 5 will maximize his gains. So, p2 will pick 5, leaving 1 for p1. Resulting scores for p1 and p2 are 3 and 5 respectively. This one did not work out for p1 either. Those were the only two possibilities for game play. p1 can never win.

    What if the input array is [1, 5, 233, 7]? For this one, let me list all possibilities and explain which ones are valid and which ones are not.

    0_1485064722628_upload-5137006d-197e-47b8-92a3-276224ff6f97

    What clarified the question for me was realizing that in each step the current player takes a look at the current array as a whole and tries to make the best pick for maximizing it's gain (taking into consideration what the other player may do).

    I hope this helps someone.


  • 1
    Z

    @diver said in Explanation of the question:

    ... predict whether player 1 is the winner. You can assume each player plays to maximize his score.

    For short: they are both as smart as alphaGo.Therefore there is actually only one possible path in this decision tree.


  • 1

    Indeed, I had some struggling before fully understand the question.


Log in to reply
 

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