Jarjit_sigh's blog

Hard problem :(
By Jarjit_sigh, history, 4 years ago, In English

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!

  • Vote: I like it
  • +50
  • Vote: I do not like it

Comments Comments (18)
| Write comment?
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Auto comment: topic has been updated by Jarjit_sigh (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it -40 Vote: I do not like it

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 .

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    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)?

    → Reply
»
4 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Afaik there is a n*logn solution for this prob, but i never got around to actually reading it. sorry

→ Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Constraints for a[i]?

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +2 Vote: I do not like it

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 maximize score_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.e l==r ) the dp[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] &mdash; dp[l+1][r] , a[r] &mdash; dp[l][r-1] ) ;

and the result would (sum + dp[1][n])/2 . Since sum contains the value of score_a + score_b .

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +58 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is n even?

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it -16 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Guys at least give me a reason for downvote.

        Its hurting me since what i have written is true.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +27 Vote: I do not like it

          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.

          → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Because you answered the wrong question, that's why.

        → Reply
»
4 years ago, # |
  Vote: I like it +17 Vote: I do not like it

I believe this problem was covered in an Algorithm's Live video.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is the link to the paper about the problem written by the guy in the video: PDF

    → Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply