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)$$$
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
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 ?
Comments (0)
