Hello sir/ma’am,
in this question we have a constraint that no of coins are even, so i calculated the sum of coins at odd places and even places and the max of both will be the answer. But what if we have odd no of coins?? I could not think of any approach in the odd coins case. Could you please help me…
Optimal Game Strategy- I
Hi @priyanshi.agarwal3405
This question is only for even value of n. If n is odd then it is uncertain that either piyush get max or nimit get max coin value. For example :
suppose we have
1 8 3 4 1 (coins)
Then in every case possible nimit only will get the max coins.
Okay sir, but this year only Rubrik came in my college for hiring interns and the same question was asked but there both the cases have to be considered (i.e. Odd and even coins). So, in that case how should I proceed with the question??
Sir, could you please reply…
Hi @priyanshi.agarwal3405
See the approach you are using for even value of n is correct and for odd value n as far as i know i cant think of any optimal way to solve it thus I m marking your doubt for mentor attention. You will get the solution very soon.
@priyanshi.agarwal3405 @Aayush
Regret to inform you that your approach to solve the problem even with even no of coins is wrong.
Try this testcase :
10
10 7 4 3 9 8 1 6 2 5
Expected Output :
32
Your Output :
29
Explanation :
Your algo to take the sum of odd and even indexed elements simply gave the answer of 29 = 7+3+8+6+5 ( sum of odd indexed elements considering the 0 based indexing )
While the actual answer is obtained by playing optimally. The most important keyword in this entire problem is ‘optimal’ which is even a part of the name of the problem itself. Since it is given that both the players play optimally , it means that at each instance both the players will look to defeat their opponent by making the best possible choice available. Your algorithm does not take into account that part. The above game can be won with a score of 32 by playing optimally as :
Pick 10
Since the opponent plays optimally , he will pick 7.
From the remaining array - 4 3 9 8 1 6 2 5
Pick 5
Opponent will pick 4
Pick 3 from 3 9 8 1 6 2
Opponent picks 9
Pick 8 from 8 1 6 2
Opponent will pick 2 and you pick 6. Opponent picks 1.
Your Score = 10+5+3+8+6 = 32
Opponent Score = 7+4+9+2+1 = 23
You win.
Now you can clearly see why your algorithm fails since the answer we computed playing optimally is not actually either the sum of all odd indexed or even indexed elements. It is a mixture of both and that is what we expect. Both the players are allowed to pick either of end elements at all instances will not stick to a sequential one by one fashion to pick elements one after another from left to right or right to left.
As for odd no of coins , once you devise a solution for even no of coins , the same solution is guaranteed to work for odd no of coins as well and there is no regard for odd or even number of elements in it. It simply doesn’t matter.
This problem has been discussed in detail in the last video of the Dynamic Programming section with its recursive function and detailed explanation. Kindly refer to it to get a better idea.
Try writing its code and let me know if you need any further help with it.
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.
Hello sir, I wrote the code using Top Down DP. Still the answer for odd number of coins is coming wrong. Sharing my code link: https://ide.codingblocks.com/s/200097 Please tell what’s wrong with this…
Hi @priyanshi.agarwal3405 where are you testing your code, and for what test cases is it giving a wrong answer?
Ma’am i am testing my code on CB IDE, test case is- n=5, coins=2,3,7,8,1
@priyanshi.agarwal3405 what should be the output according to you? I cant seem to make a sum bigger than 10
Ma’am let’s say P1 chooses first, he chose 2 then P2 chose 3, then P1 7, P2 8, then finally only one coin is left and P1 choose that. Thus, P1 has (2+7+1)=10 and P2 has (3+8)=11. So answer should be 11.
@priyanshi.agarwal3405 this strategy seems to give the maxAns for the first player only, so you can try to modify such that it calculates answer for the second person as well and then print MAX of the two
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.
Hello Ma’am, I made the change. Could you please see to it now… Is this ok?? Or is there any other way ? https://ide.codingblocks.com/s/200097