Optimal Game Strategy 87655

#1

https://ide.codingblocks.com/s/54951
one test case not passed

#2

Hi Aastha,
Consider the following input:
4
8 15 3 7
Expected output: 22
Your output: 15

#3

Hey Aastha, as you are not responding to this thread, I am marking your doubt as Resolved for now. Re-open it if required.

Please mark your doubts as resolved in your course’s “Ask Doubt” section, when your doubt is resolved.

#4

i could not figure out my mistake so could not respond.

#5

Hey Aastha, in that case you can respond that you still didn’t get this… Otherwise, how will we know if your doubt was resolved or not.

#6

Hi Aastha, you’re using greedy approach in this. You’re choosing the locally optimal solution at every step i.e. you’re choosing the maximum valued coin at every step. This approach will not provide us the globally optimal solution always like in the case I mentioned earlier. You need to think of some other logic that will always give the optimal solution.

#7

Since you needed help in the logic, here is the algo:
(1) Count the sum of all coins that are odd-numbered. (Call this X)
(2) Count the sum of all coins that are even-numbered. (Call this Y)
(3) If X > Y, take the left-most coin first. Choose all odd-numbered coins in subsequent moves.
(4) If X < Y, take the right-most coin first. Choose all even-numbered coins in subsequent moves.
(5) If X == Y, you will guarantee to get a tie if you stick with taking only even-numbered/odd-numbered coins.

#8

thanks. now it’s resolved

#9

But in the question, it isn’t mentioned that we need globally optimum value. It is just two players trying to get the max value.

#10

Hi Hardik, yes, it is not mentioned in the question. You have to think of the right approach. The two players have to get the max value. Now, there are different approaches that you can apply to solve this problem. You can pick up the max of the two coins on left and right side everytime. But when you’ll try to apply this logic to some sample inputs, you will find that it doesn’t give the most optimal solution always.Then you try to apply some other algorithm to find the optimal solution. That’s how you develop your logic.