Only 1 test case correct

#1

My solution: https://ide.codingblocks.com/s/458571

Question: https://online.codingblocks.com/app/player/178555/content/173738/4939/code-challenge

Getting correct answer while compilation and Test-Case 1, but getting wrong answers for Test-Case 0,2,3.

Where am I going wrong?

#2

hello @mohaktrivedi
greedy approach will work in this problem becuase nimit is also playing optimally. so when nimit turns will come, he will also try to play wisely and try to maximize his score or minimize piyush score.
so what step nimit will take is also important. also picking always local maximum doesnt ensure that overall sum will be maximum.

refer this for clarity->
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.

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;
}
#3

@aman212yadav I haven’t learned Greedy Algo yet, however, I have clearly understood your approach. Thanks for helping.
But, how did you come to know that local maxima won’t help?

#4

the approach that u r using is greedy. the approach that i proposed is a brute force recusive its not greedy.
…

by running ur code on hidden cases.

#5

How can one determine that local maxima won’t help, without being able to see the test-cases?

#6

…

in this problem it we can observe following that our steps will also affect our oppopent steps and vices a versa.

so if we are picking current maximum then it doesnot means that our opponet score will be getting minimised.
it may happen that due to our local optimal step the opponet is now able to score more.

running over various cases is one way to prove incorrectnes of greedy

1 Like
#7

Alright. Thanks for clearing my doubt.

#8

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.