OptimalGameStrategy-I (COIN-GAME PROBLEM-Recursion)

[anuragdeol2017 (Anurag Deol)]

My thought process is:-

Coins value is given as: 1, 2, 3, 4. Now if Piyush picks coin 4. Nimit will either pick 1 or 3. In order to maximize value won by Piyush, we consider the case, where Nimit picks coin 1. Now Piyush picks coin 3. So at the end of the game, Piyush won value 7.

But the answer is 6. Why is that so? Did i understand the question wrongly?

[aman212yadav (Aman Yadav)]

hello @anuragdeol2017

@anuragdeol2017

Did i understand the question wrongly?

yeah …

@anuragdeol2017

Nimit will either pick 1 or 3. In order to maximize value won by Piyush, we consider the case, where Nimit picks coin 1.

why would nimit pick 1 ,he is opponent of piyush so he will also try to score as much as he can .

At each instance we would need to consider two possibilities that we can pick the first as well as the last element of the remaining array. Both these possibilities give rise to two more possibilities depending on the other player. Since the second player plays optimally and try to minimise our score. So overall we have two possibilities at each instance.
For the first possibility , where we could pick the first element , the other player will pick the next element from the side that would minimise our total score.
Similarly , for the second possibility , where we can pick the last element , the other player would still pick the next element from the side that would minimise our total score.
We entertain both these cases and take the maximum result of the two and return that result.
We take two pointer variables , say ‘i’ and ‘j’ which each represent the starting and the ending point of the remaining array currently in consideration. We work till the two pointers cross each other.

ll optimalGame(ll i,ll j){
    if(i > j){
        return 0;
    }

    // Consider both the possibilities. You can pick either the first or the last coin.
    // Since the opponent plays optimally , we would get the minimum of the remaining coins for each choice.
    ll pickFirst = coins[i] + min( optimalGame(i+2,j) , optimalGame(i+1,j-1) ) ;
    ll pickLast = coins[j] + min( optimalGame(i,j-2) , optimalGame(i+1,j-1) ) ;

    // Pick the max of two as your final result
    ll ans = max(pickFirst,pickLast);

    return ans;
}

[aman212yadav (Aman Yadav)]

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

[proceedpossibly3136_2ce94a7ae36c854a (Philips Reyes)]

@aman212yadav

At each instance we would need to consider two possibilities that we can pick the first as well as the last element of the remaining array. Both these possibilities give rise to two more possibilities depending on the other player. Since the second player plays optimally and try to minimise our score. So overall we have two possibilities at each instance.
For the first possibility , where we could pick the first element , the other player will pick the next element from the side that would minimise our total score.
Similarly , for the second possibility , where we can pick the last element , the other player would still pick the next element from the side that would minimise our total score.

Within every case, we’d have to examine two options: the first and final member of the remaining array. Both of these alternatives result in two further alternatives, which are dependent on the other player. Since the second player plays effectively, we want to keep our score as low as possible. As a result, we have two options in each case. For the first option, when we might choose the first component, the other player will choose the free steam wallet codes following thing from the side that would reduce our overall score the least. Similarly, in the second scenario, when we may choose the final ingredient, another player will select a new thing from the side that would reduce your aggregate ranking.