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)const ll LINF = 0x3f3f3f3f3f3f3f3f;
int n;
vector<int> a;
vector<vector<ll> > f;
ll magic(ll L = 0, ll R = n - 1) {
if (f[L][R] != -LINF) return f[L][R];
if (L >= R + 1) return f[L][R] = 0;
if (L >= R - 1) return f[L][R] = max(a[L], a[R]);
ll A = a[L] + min(magic(L + 2, R - 0), magic(L + 1, R - 1));
ll B = a[R] + min(magic(L + 1, R - 1), magic(L + 0, R - 2));
return f[L][R] = max(A, B);
}
int main()
{
cin >> n;
a.resize(n);
f.assign(n, vector<ll>(n, -LINF));
ll sum = 0;
for (int &t : a)
{
cin >> t;
sum += t;
}
ll x = magic(); /// Maximum Possible x can get
ll y = sum - x; /// Calculate the score of second player
cout << x - y;
return 0;
}
DP iterative - O(n^2)int main()
{
int n;
cin >> n;
vector<int> a(n);
vector<vector<ll> > dp(n, vector<ll>(n));
for (int r = 0; r < n; ++r)
{
cin >> a[r];
dp[r][r] = a[r]; /// (l = r) case
for (int l = r - 1; l >= 0; --l)
dp[l][r] = max(a[l] - dp[l + 1][r], a[r] - dp[l][r - 1]); /// either to take leftmost or rightmost element
}
cout << dp[0][n - 1];
}
Deque - O(n)int main()
{
int n;
cin >> n;
vector<ll> v(n);
for (int i = 0; i < n; ++i)
{
cin >> v[i];
/// Compress the array to bitonic a1 > a2 > ... > ak < ... < a[n - 1] < an
for (; i >= 2 && v[i - 2] <= v[i - 1] && v[i - 1] >= v[i]; i -= 2, n -= 2)
v[i - 2] += v[i] - v[i - 1];
}
/// Calculate result (x - y)
ll res = 0;
for (int l = 0, r = n - 1, t = 1; l <= r; t = -t)
res += t *((v[l] > v[r]) ? v[l++] : v[r--]);
cout << res;
return 0;
}
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 1Input:
3
1 1 1
Output:
3
Explain:
In three games, first player have 2 points and second player have 1 points
Example 2Input:
2
0 1
Output:
1
Explain:
In the first game the first player lose (0 < 1)
In the second game the first player win (1 > 0)
Example 3Input:
1
0
Output:
0
Explain:
In the only game, the first player have equal score to the second (0 = 0). So he lost
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)const int INF = 1e9;
int main()
{
int n;
cin >> n;
vector<int> a(n << 1);
vector<vector<int> > f(n << 1, vector<int>(n << 1, -INF));
for (int i = 0; i < n; ++i)
{
int x;
cin >> x;
a[i] = a[n + i] = x;
f[i][i] = f[n + i][n + i] = x; /// (l = r) case
}
for (int d = 1; d < n; ++d) /// (r - l = d)
for (int l = 0, r = d; r < a.size(); ++l, ++r) /// iterating over the array
f[l][r] = max(a[l] - f[l + 1][r], a[r] - f[l][r - 1]); /// either select leftmost or rightmost
int res = 0;
for (int i = 0; i < n; ++i)
{
int l = i + 1, r = i + n - 1;
if (a[i] - f[l][r] > 0) res++; /// a[i] is the first selected number
}
cout << res;
return 0;
}
Deque way - O(n^2)int main()
{
int n;
cin >> n;
vector<int> a(n);
for (int &x : a) cin >> x;
a.resize(n << 1);
for (int i = 0; i < n; ++i) a[i + n] = a[i];
vector<int> v(n - 1, false);
int res = 0;
for (int p = 0; p < n; ++p)
{
int m = n - 1;
for (int i = 0, j = p; i < m; ++i)
{
v[i] = a[j++];
/// Compress the array to bitonic a1 > a2 > ... > ak < ... < a[n - 1] < an
for (; i >= 2 && v[i - 2] <= v[i - 1] && v[i - 1] >= v[i]; i -= 2, m -= 2)
v[i - 2] = (v[i - 2] + v[i] - v[i - 1]);
}
/// Calculating (t = x + y)
int t = 0;
for (int i = p; i < p + n - 1; ++i)
if (a[i]) t++;
/// Calculating (d = x - y)
int d = 0;
for (int l = 0, r = m - 1, t = 1; l <= r; t = -t)
d += t * (v[l] > v[r] ? v[l++] : v[r--]);
int e = a[n - 1 + p]; /// first selected number
int x = (t - d) / 2; /// first player played after first selected
int y = (t + d) / 2; /// second player played after first selected
if (x + e > y) res++;
}
cout << res;
return 0;
}