Where am i going wrong .PLZ HELP

#1

https://online.codingblocks.com/app/player/61753/content/77244/4939/code-challenge

#2

#include<bits/stdc++.h> #define ll long long using namespace std; ll game(ll *arr,ll sum,ll i,ll j){ if(i>j) return sum; if(arr[i]>=arr[j]){ sum+=arr[i]; i++; if(arr[i]>=arr[j]) i++; else j–; sum=game(arr,sum,i,j); } else{ sum+=arr[j]; j–; if(arr[i]>=arr[j]) i++; else j–; sum=game(arr,sum,i,j); } return sum; } int main(){ ll n; cin>>n; ll * arr = new ll[n]; for(int i=0;i<n;i++){ cin>>arr[i]; } ll sum=game(arr,0,0,n-1); cout<<sum; }

#3

Hello @kumarroyjayanta,

Please, share your code using Online Coding Blocks IDE:
STEPS:

  1. Paste your code at https://ide.codingblocks.com/
  2. Save it there.
  3. Share the URL generated.
#4
#5

Hello @kumarroyjayanta,

Comparing arr[i] and arr[j] are not sufficient alone to solve this problem.
Also, the opponent will make an optimal choice i.e. the pick that will minimize the amount collected by Piyush.

There are two choices:

  1. The user chooses the ith coin with value Vi: The opponent either chooses (i+1)th coin or jth coin. The opponent intends to choose the coin which leaves the user with minimum value.
    i.e. The user can collect the value Vi + min(F(i+2, j), F(i+1, j-1) )
    image
  2. The user chooses the jth coin with value Vj: The opponent either chooses ith coin or (j-1)th coin. The opponent intends to choose the coin which leaves the user with minimum value.
    i.e. The user can collect the value Vj + min(F(i+1, j-1), F(i, j-2) )
    image

Following is recursive solution that is based on above two choices. We take the maximum of two choices.

F(i, j) represents the maximum value the user can collect from
i’th coin to j’th coin.

F(i, j) = Max(Vi + min(F(i+2, j), F(i+1, j-1) ),
Vj + min(F(i+1, j-1), F(i, j-2) ))

Base Cases

F(i, j) = Vi If j == i
F(i, j) = max(Vi, Vj) If j == i+1

explanation:
Let’s understand this:
let the index at which the leftmost coin is available be l (initially 0)
and the index at which the rightmost coin is available be r (initially n-1)

  1. if piyush chooses l
    then in the next pick he will have two possible choices:
    (l-1,r-1): the opponent has selected the rightmost coin
    (l-2,r): the opponent has selected the leftmost coin.
    sum= arr[l]+min(fun(l-1,r-1),fun(l-2,r))
    opponent will choose something that will cause piyush to have minimum sum.

  2. if piyush chooses r
    then in the next pick he will have two possible choices:
    (l-1,r-1): the opponent has selected the leftmost coin
    (l,r-2): the opponent has selected the rightmost coin.
    sum= arr[r]+min(fun(l-1,r-1),fun(l,r-2))
    opponent will choose something that will cause piyush to have minimum sum.

Hope, this would help.
Give a like if you are satisfied.

#6

sir the algorithm i have applied is doing the same.can you give me example where i am going wrong

#7

Sure @kumarroyjayanta,

Example:
10
22 50 16 13 8 41 25 43 8 7
Expected Output:
154
Your Output:
79

Reason:
Choosing maximum value won’t let to the optimal solution.

Correct logic:

Hope, this would help.
Give a like if you are satisfied.

#8

yes sir got it.how togive like

#9

Hii @kumarroyjayanta,

There is a small heart shaped icon below my response.
Just click on it.
BTW, don’t forget to mark it as resolved.

1 Like