@ayush_7
Please tell me what do you mean by how finals core is maximised or minimised? Do you mean you are not able to predict the moves or did you not understand the logic in which they both move?
I will try to be as elaborate as possible.
Firstly, we are given a 2 sequences A and B. Now it is said that at any turn, k, player will choose a interval in A of length Bk. Meaning, in the sequences given in sample test, i.e.
Let A= 3 7 5 4 9 6 1 3
Let B = 6 3 1
In the first turn, 1st element of B is 6. This means Chef can choose a interval of length 6. Now, this means he can choose 6 continuous values of A. We must remember, the sum of all elements in interval adds to the score AND he wants to make score AS LARGE AS possible.
Meaning, if he choses from element 1 to element 6, i.e. 3,7,5,4,9,6 then score is sum of all these elements
Meaning, score = 3+7+5+4+9+6 = 34
Now, he wants to make the score AS LARGE as possible? How will this happen?
The score will be as large as possible if the sum of elements in it are as large as possible. And the sum would be greater if the value of elements in it are greater.
This means, he will chose an interval whose elements have maximum sum.
Lets see the choices of interval Chef has-
1. 3,7,5,4,6,9. Sum =34
2. 7 5 4 9 6 1 Sum = 32
3. 5 4 9 6 1 3 Sum = 28
No more 6 element interval is possible. Out of all the interval, interval “3 7 5 4 9 6” has maximum sum, hence Chef chooses it.
Score =34.
Now its Chefu’s turn. He wants to make score AS SMALL AS POSSIBLE, and we all know that the sum of elements of his interval would be SUBTRACTED from score. Also, he is restricted to choose his interval INSIDE Chef’s interval, as the problem clearly says that the interval of succeeding term should be completely inside the interval of preceding term.
So, interval for Chefu is “3 7 5 4 9 6” and he wants to minimize the score. For this, again, he needs an interval with highest sum. Upon inspection, we see that the interval “5 4 9” has highest sum among all the 3 element intervals possible. So Chefu chooses “5 4 9”
Score = 34-18=16.
Now it is Chefs turn. Remember, the problem said the chosen interval should be COMPLETELY inside the preceeding interval, so among “5 4 9” he cannot choose 5 and 9 since they are not “insides” but “at boundary”. It is clearly mentioned in problem statement that
l < u ≤ v < r,`
So he cannot choose 5 and 9, and he is only left with 4.So he chooses 4 and the game comes to end with score of -
Score=16+4=20
That being said, the entire problem is NOT limited to this. Finding maximum interval will perhaps clear only 1 subtask or two. Why? Because see here-
Let A= 3 7 5 4 9 6 1 3
Let B = 3 1
Now, the maximum sum interval is 4 9 6, which makes score 19. But in next turn Chefu chooses 9, reducing the score to mere 10.
However, if we choose 5 4 9, then final score would be 5+4+9-4 = 14, which is higher. I think dp is needed here for full score, which I sadly don’t know much atm.
However, I can give you a link to correct code-
Correct code
That’s all I can help dear, and yeah, thanks for correction.