Optimal game strategy 2

#1

it is not giving output

#2

Hello @chehakagrawal01

Here is the modified code

If you won’t be able to understand it, just let me know and I will explain it to you.

1 Like
#3

can u plz explain it and tell me mistake in my code

#4

Hello @chehakagrawal01

This is a long explanation but go through it, you will understand the approach.

Suppose that n is 6
First I calculated the answer for these sub-arrays
[1-2] [2-3] [3-4] [4-5] [5-6] (Here the length of each sub-array is 1 (gap = 1))
Then using these arrays I calculated the answer for these
[1-4] [2-5] [3-6] (Here the length of each sub-array is 3 (gap = 3))
Then using these arrays I calculated the answer for
[1-6] (Here the length of each sub-array is 5 (gap = 5))

GAP = 1
When there are only 2 elements i.e., gap = 1, it is trivial, we can either pick the first element or the second element

GAP = 3
[1-4] is calculated in this way
suppose we chose 4th element, now the opponent will chose from [1-3], the opponent will chose the element that will leave our profit from the rest of the array minimum for us

Let say that the opponent chose element 3, so now I can chose from [1-2] NOTE:- I have already stored this value.
If the opponent chose element 1, I can now chose from [2-3] ALREADY STORED
So the opponent will chose element 3 or element 1 in accordance with min( [1-2], [2-3] ) so as to minimize out profit from the rest of the array
similarly [2-5] and [3-6] are calculated

GAP = 5
[1-6] is calculated in this way
suppose we chose 6th element, now the opponent will chose from [1-5], the opponent will chose the element that will leave our profit from the rest of the array minimum for us

Let say that the opponent chose element 5, so now I can chose from [1-4] NOTE:- I have already stored this value.
If the opponent chose element 1, I can now chose from [2-5] ALREADY STORED
So the opponent will chose element 5 or element 1 in accordance with min( [1-4], [2-5] ) so as to minimize out profit from the rest of the array.

1 Like
#5

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.