Doubt in understanding the question

#1

for the given example 1 2 3 4
the and should we 7 . here how I am thinking do correct if I am wrong—

  1. piyush goes first and picks 4
  2. next boy goes second and if it picks 1
  3. then piyush would pick 3 and have 7 as the maximum value…right?
OPTIMAL GAME STRATEGY-I
#2

Hello @aryaman.kumar26,

It is a tricky question.
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
image721×315 4.4 KB

  1. 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.

#3

sir i have not seen the complete answer as i want to solve by myself . But are you saying that as it is a game both piyush and nimit want to collect maximum value. That means if piyush picks 4 then nimit would pick 3 as it is maximum among rest

#4

or nimit can choose the leftmost coin as well

#5

No @aryaman.kumar26,

Piyush will play to win.
While nimit will choose so that piyush will end up with minimum score.

#6

but sir ye to tabhi ho payega na jab nimit maximum choose kre from the option he has

#7

No @aryaman.kumar26,

Not always.
The present selection depends upon the future selection also.
So, he will select something that will make some loss to piyush in future selection.

#8

to mtlb hme dono casse lekr chlna padega
nimit jb km wala choose larega aur jb jyada wala

#9

Haan @aryaman.kumar26 , ki which one will cost Piyush a loss.

#10

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.