Optimal Game Strategy-I 1

#1

#include<bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fast std::ios::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define clr0(a) memset((a), 0, sizeof(a))
#define clr1(a) memset((a), -1, sizeof(a))
#define srtin1 cin.ignore ( std::numeric_limitsstd::streamsize::max(), ‘\n’ );
#define strin2 getline(cin, text);
#define ll long long
#define test cout<<“archit\n”
#define debug(x) cout<<x<<" "
#define debug1(x) cout<<x<<"\n"
#define debug2(x,y) cout<<x<<" “<<y<<”\n"
#define debug3(x, y, z) cout<<x<<" “<<y<<” “<<z<<”\n"
#define pb push_back
#define pi pair<int,int>
#define fi first
#define si second
#define mod (ll)1000000007
#define mxn 1000005
#define ordered_set tree<int, null_type,less, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
//using namespace boost::multiprecision;
using namespace __gnu_pbds;
int main()
{
int n; cin>>n;
ll* arr = new lln;
for(int i=0;i<n;i++){
cin>>arr[i];
}
int i=0,j=n-1;
int flag=1;
ll piyush,nimit;
piyush=nimit=0;
while(i < j){
if(flag){
piyush +=max(arr[i], arr[j]);
if(arr[i] > arr[j]){
i+=1;
}
else{
j-=1;
}
}
else{
nimit+=max(arr[i], arr[j]);
if(arr[i] > arr[j]){
i+=1;
}
else{
j-=1;
}
}
flag^=1;
}
//debug2(i, j);
debug(piyush);
return 0;
}
whi this is giving WA

#2

Hi @archit_18
You are employing a greedy technique. That is , checking only for local maximum and not aiming for the global maximum.

Try this testcase :
4
2 3 7 4

Using your greedy technque ,
Player 1 picks 4
Player 2 picks 7
Player 1 picks 3
Player 2 picks 2

Player 1 Score = 4 + 3 = 7
Player 2 Score = 7 + 2 = 9

Since our goal was to make sure that Player 1 wins, the greedy technique fails

If we were not inclined to use the greedy technique and had played optimally like this
Player 1 picks 2 (Even though its lesser of 2 & 4)
Player 2 picks 4
Player 1 picks 7
Player 2 picks 3

Player 1 Score = 2 + 7 = 9
Player 2 Score = 4 + 3 = 7

Player 1 wins.
This problem has been discussed in detail in the last video of the Dynamic Programming section with its recursive function and detailed explanation.
Please refer to it.

#3

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.