PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: tejas10p
Testers: iceknight1093, rivalq
Editorialist: iceknight1093
DIFFICULTY:
1567
PREREQUISITES:
Dynamic programming
PROBLEM:
There is a string S, on which Alice and Bob play a game. Alice starts first and then they alternate moves.
- On her move, Alice picks a prefix of S, appends it to her string, and then removes this prefix from S
- On his move, Bob picks a suffix of S, appends its reverse to his string, and then removes this suffix from S
If they play optimally, what is the maximum possible value of the longest common subsequence of Aliceâs and Bobâs strings?
EXPLANATION:
The main observation to be made here is that, no matter how the moves are performed, Aliceâs final string will be some prefix of S and Bobâs string will be the (reversed) remaining suffix.
That is, Aliceâs string will be S[1\ldots i] and Bobâs string will be rev(S[i+1\ldots N]) for some 1 \leq i \leq N. Itâs not hard to see that every such pair of strings is achievable.
For convenience, let R denote the reverse of S.
Our task is then to compute the maximum value of LCS(S[1\ldots i], R[1\ldots j]) across all (i, j) such that i+j = N.
This is a rather standard problem that is solved using dynamic programming; in fact, we can simply use the exact same states as the classical longest common subsequence problem.
Let dp[i][j]
denote the longest common subsequence of the strings S[1\ldots i] and R[1\ldots j].
Then, there are three possible cases:
-
S_i is not a part of the LCS; in which case the answer is
dp[i-1][j]
-
R_j is not a part of the LCS; in which case the answer is
dp[i][j-1]
-
S_i and R_j are both part of the LCS; in which case the answer is
1 + dp[i-1][j-1]
- Note that S_i = R_j must hold for this case to be applicable.
-
dp[i][j]
is the maximum of the above three values.
The base cases are dp[i][0] = 0
and dp[0][j] = 0
.
Dynamic programming allows us to compute dp[i][j]
for every 0 \leq i, j \leq N in \mathcal{O}(N^2), after which the final answer is simply the maximum value of dp[i][j]
across all (i, j) such that i+j = N.
TIME COMPLEXITY:
\mathcal{O}(N^2) per testcase.
CODE:
Setter's code (C++)
#include <bits/stdc++.h>
#define maxn 5007
using namespace std;
int dp[maxn][maxn];
int main() {
//freopen("inp9.in", "r", stdin);
//freopen("inp9.out", "w", stdout);
int t;
cin >> t;
int sm = 0;
while(t--) {
int n;
cin >> n;
sm += n;
assert(sm <= 5000);
string s;
cin >> s;
string t = s;
reverse(t.begin(), t.end());
for(int i = 0; i < n; i++)
for(int j = 0;j < n; j++)
dp[i][j] = 0;
for(int i = 0; i < n; i++) {
for(int j = 0;j < n; j++) {
int now = (s[i] == t[j]), mx = 0, nc = 0;
if(i > 0) mx = max(dp[i - 1][j], mx);
if(j > 0) mx = max(dp[i][j - 1], mx);
if(i > 0 && j > 0) nc = dp[i - 1][j - 1];
dp[i][j] = max(nc + now, mx);
}
}
cout << dp[n - 1][n - 1]/2 << "\n";
}
}
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
s = '#' + input() + '!'
dp = [ [0 for _ in range(n+2)] for _ in range(n+2)]
for i in range(1, n+1):
for j in reversed(range(i+1, n+1)):
dp[i][j] = max(dp[i-1][j], dp[i][j+1])
if s[i] == s[j]:
dp[i][j] = max(dp[i][j], dp[i-1][j+1] + 1)
ans = max(dp[i][i+1] for i in range(1, n))
print(ans)