Need to optimize the solution for a variant problem of Deque L — Atcoder DP contest

Revision en4, by SPyofgame, 2020-09-13 12:44:38

Original Problem

In this problem. The statement give you a deque of $$$n$$$ number. There are two players take turn alternately. In one turn, they can select either leftmost or rightmost element and remove it, and earn $$$x$$$ points where $$$x$$$ is the removed number. They play until the deque is empty. Lets $$$X, Y$$$ are the scores of the first player and the second. Find the maximum $$$X - Y$$$ when they play optimally

We can use dynamic-programming to solve it in $$$O(n^2)$$$ or we can improve upto $$$O(n\ polylog(n))$$$ using data-structure like Treap and fully-optimized by deque in linear $$$O(n)$$$

Recursive DP - O(n^2)
DP iterative - O(n^2)
Deque - O(n)

Variant Problem

Then, I come to a problem, here is the statement.

There is a cycle of $$$n (n \leq 10^4)$$$ binary number $$${a_1, a_2, \dots, a_n}$$$ and ($$$a_i \in {0, 1}$$$) First player take a random number, lets say $$$a_p$$$ then remove it and gain $$$a_p$$$ points The second player take a number which is consecutive with last number removed ($$$a_p$$$) — select either $$$a_{p - 1}$$$ or $$$a_{p + 1}$$$ (notice that $$$a_1$$$ and $$$a_n$$$ is consecutive) They start to play alternately until there are no number left and they plays optimally

The question is in each game where as the first player select the number $$$a_p$$$, $$$p \in [1, n]$$$. How many games did the first player have more score than the second player

Example 1
Example 2
Example 3

I try to use dp to solve it in $$$O(n^2)$$$ but I dont know how to optimize by using deque and only come up to an $$$O(n^2)$$$ solution. Can someone suggest me a better algorithm ?

Dynamic programming - O(n^2)
Deque way - O(n^2)
Tags deque

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English SPyofgame 2020-09-13 12:44:38 19
en3 English SPyofgame 2020-09-13 12:32:37 493
en2 English SPyofgame 2020-09-13 12:25:16 51
en1 English SPyofgame 2020-09-13 12:08:59 6185 Initial revision (published)