MAXLCS - Editorial

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)

Why it is showing TLE in 1st test case if this is implemented using dp with memoisation ?

1 Like

Can anybody tell me what’s wrong with this code? It gives TLE on test case 5 and 6.

My approach:

  • I try to take the lcs of the prefix and the suffix of s.
  • We move forward towards right for prefix and towards left for suffix.
  • Initially, the prefix substring starts at index 0 and suffix substring starts at index n - 1.
  • If these indexes touch or cross each other we return 0 because any index element can not be a part of both the prefix and the suffix.
int solve1(int i , int j , string s , vector<vector<int>> &dp) {
    if(i >= j)
        return 0;
    
    if(dp[i][j] != -1)
        return dp[i][j];

    if(s[i] == s[j])
        return dp[i][j] = 1 + solve1(i + 1 , j - 1 , s , dp);
            
    return dp[i][j] = max(solve1(i + 1 , j , s , dp) , solve1(i , j - 1, s , dp));
}

void solve() {
    int n;
    cin >> n;

    string s;
    cin >> s;

    vector<vector<int>> dp(n , vector<int>(n , -1));
    int ans = solve1(0 , n - 1 , s, dp);
    cout << ans << endl;
}
2 Likes

You’re passing string s by value, pass it by reference instead.

Please link your code if you want to know what’s wrong with it, it’s not really possible to debug otherwise.

I assume you’re talking about your latest TLE submission, which is this one.
It gets TLE because of the memset, since you’re resetting a 5000\times 5000 array upto 1000 times which is more than 10^{10} operations.

Can someone tell what’s wrong with my code , I think its covering all the required cases still I got WA

#include <bits/stdc++.h>
using namespace std;

int main() {
	long long int t;
	cin>>t;
	while(t--){
	  int n;
	  cin>>n;
	  string s;
	  cin>>s;
	  
	  int count = 0,count2 = 0,count3 = 0;
	  int i = 0,j = n-1;
	  
	  while(i < j){   //checking from right side
	    if(s[i] == s[j]){
	      count++;
	      i++;
	      j--;
	    }
	    else{
	      i++;
	    }
	  }
	  
	  i = 0;j = n-1;
	  while(i<j){         //checking from left side
	    if(s[i] == s[j]){
	      count2++;
	      i++;
	      j--;
	    }
	    else{
	      j--;
	    }
	  }
	  
	  for(i = 0;i<n/2;i++){
	  	if(s[i] == s[n-i-1]){
	  		count3++;
	  	}
	  }
	  
	  count = max(count,count2);
	  count = max(count,count3);
	  
	  cout<<count<<endl;
	}
	return 0;
}

“There is a string SS, on which Alice and Bob play a game. Alice starts first and then they alternate moves.”, from this problem statement one feels that division of string S happens at median and both Alice and bob as equal length string if S is even or one less if S is odd

a simple Ans (length of longest palindromic subsequence) / 2

I’m not considering this step in the explanation:

    • dp[i][j] is the maximum of the above three values.

Submission: CodeChef | Competitive Programming | Participate & Learn
My code is still accepted.

It means dp[i-1][j-1]+1 is always greater than max(dp[i-1][j],dp[i][j-1]) when a[i-1]==b[j-1].

This is nothing but regular LCS.

Am I missing something? I couldn’t think of any test case which contradicts my thinking. So, is checking for max lcs at each step not really required? Someone clarify it for me please.

In the provided test case 2, how can the longest common subsequence(lcs) of 2 strings “abc” and “adc” be 2?
shouldn’t it be 1 as lcs is just ‘a’ and ‘c’

Can anyone help me in this regard?

What you are thinking is longest common substring (contiguous). Subsequence is not necessarily contiguous, it is just the order which matters

for “abc” and “adc”, longest common substring is “a” or “c”, and longest common subsequence is “ac”, skipping all the letters which are not common.

2 Likes

Thanks a lot for your answer.

why passing strings without reference in the lcs function gives TLE in test case 5 and 6 but passing strings with reference in the lcs function gets accepted?

passing string without reference code

passing string with reference code