I have faced this problem in my unofficial national team selection test and i have been trying to solve it for days to no avail... Hope someone could help me :(
Given an integer array of length n (n <= 100000). Alberto and Brendaly play a game on it. On each turn the player picks a number from one of the 2 ends of the sequence. Alberto goes first. Both players wants to maximize their total score by the end of the game. If they both play optimally, whats the total score Alberto gets? all elements in array are not larger than 1e9.
Thank you!
Auto comment: topic has been updated by Jarjit_sigh (previous revision, new revision, compare).
Its a pretty standard dp problem.You will find the exact same problem in dp set of leetcode. I explain a bit.All you have to do is to while its Alberto's turn you will try to maximize your answer while at Brendaly turn you will try to minimise your score .
Won't the dp states require the start and end points of the array. Like dp[i][j] represents the answer for the range i to j. It will be O(n^2). How to do it in O(n)?
this ^
Afaik there is a n*logn solution for this prob, but i never got around to actually reading it. sorry
Constraints for a[i]?
added, but its not important anyway
I was about the comment the interval dp solution , but then I noticed the constraints . If anyone knows a better solution than O(n^2) it'd helpful . But here goes an O(n^2) dp solution let's score_a be the maximum score that alberto can get and score_b be maximum score that brandely can get . If both play optimally alberto wants to maximize the
score_a - score_b, while brandely wants to minimize it ( i.e maximizescore_b - score_a) now let dp[l][r] be the maximum value of score_a — score_b while playing on the range [l,r] if this range contains only one element ( i.el==r) thedp[l][[r] = array[l]else Alberto the choose either the first element from the range in which case brandely gets to choose from the range [l+1,r] and alberto can choose the last element then brandely choose from [l ,r-1] thus the dp transition is:dp[l][r] = max( a[l] — dp[l+1][r] , a[r] — dp[l][r-1] ) ;and the result would
(sum + dp[1][n])/2. Since sum contains the value ofscore_a + score_b.Solution in $$$O(n)$$$ (proved by AC, I'm not so sure about the correctness)
If $$$a_{i-1} \leq a_{i} \geq a_{i+1}$$$, and a player chooses the index $$$i \pm 1$$$, the next two optimal moves are choosing respectively the indices $$$i$$$ and $$$i \mp 1$$$. Hence, these values can be replaced with a single value $$$a_{i-1} - a_i + a_{i+1}$$$. Repeat until you don't have such "peaks". Then, choosing greedily the maximum value works.
Is n even?
If n is even then the person who plays first will always win.(If values of A[i] are such that their are no draws) Because the person who plays first can take either all the odd position elements or the even position elements and one of them should be greater than another one.
Why Downvotes?
Is my solution not correct when n is even or people at codeforces are unable to digest the fact that newbie can answer this?
Guys at least give me a reason for downvote.
Its hurting me since what i have written is true.
I haven't downvoted you, but my guess is that you just answered the question that wasn't really asked. The problem statement requires calculating the maximized total score, rather than only figuring out who wins.
Because you answered the wrong question, that's why.
I believe this problem was covered in an Algorithm's Live video.
This is the link to the paper about the problem written by the guy in the video: PDF
There is an algorithm named "Termity" that can solve this in $$$O(N)$$$ time or $$$O(N log N)$$$ time. Link to the paper is: https://www.mimuw.edu.pl/~idziaszek/termity/termity.pdf