Optimal Game Strategy-1

#1

Just 1 test case is giving wrong answer.

#2

Hi @saarthakrox29, please share your code so i can check

#3 
#include<iostream>
#include<algorithm>
#include<string>
#include<stdio.h> 
#include<stdlib.h>
#include<cstring>
#include<math.h>
#include<vector>
#include<time.h>
using namespace std;
typedef long long int ll;
ll findmax(ll a[],int n,int l,int h,ll m,int i)//m is piyush's total,i is the turn no.
{
	if(l>h)//Base case
	{
		return m;
	}
	if(i%2==0)//Nimit selects the bigger of 2
	{
		if(a[l]>a[h])
		return findmax(a,n,l+1,h,m,i+1);
		else
		return findmax(a,n,l,h-1,m,i+1);
	}
	return max(findmax(a,n,l+1,h,m+a[l],i+1),findmax(a,n,l,h-1,m+a[h],i+1));
}
int main() {
int n,i;
ll a[35];
cin>>n;
for(i=0;i<n;i++)
cin>>a[i];
ll p=findmax(a,n,0,n-1,0,1);
cout<<p;
return 0;
}`Preformatted text`
#4

@saarthakrox29,you are thinking of greedy approach i.e. taking the bigger of two, there might be some cases when this approach fails eg imagine this is nimit turn and the coins present are
[5 4 8 6 ] then according to your code nimit will choose 6 as 6>5 and piyush will be left with [5 4 8] thus he can choose 8 , now if nimit would have chosen 5 then piyush would be left of [4 8 6] thus piyush have option of 4 and 6 . thus we can see that nimit is better of choosing 5

so , what can be the approach ??
we would need an optimal solution for this. 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 othe

refer to below code : -

in case of any doubt feel free to ask :slight_smile:
if u got the answer then mark your doubt as resolved

Optimal game strategy-1
#5

Thank you, i thought that the opponent was picking using greedy approach as the question only mentioned about piyush picking optimally