LCKALI - Editorial

Links

Division1
Division2
Division3

Setter : Ronels Macwan

Testers : Samarth Gupta , Manan Grover

Difficulty
Medium

Prerequisites
Dynamic Programming, greedy.

Problem

Given a string M, and two strings, we have to tell whether those can appear
as non-overlapping subsequences of M. We also have D queries, where we can append a digit or erase a digit from the end of any of the strings.

Quick Explanation

Try to use a two dimensional dp, where dp_{i,j}{} (i is the length of Aryan’s number and j is the length of Ali’s number) represents the smallest index of M (0 based indexing here), where both of the strings (Ali and Aryan’s numbers) can have a non-overlapping subsequence. If dp_{i,j} < N , we have “yes” as the answer and “no” otherwise.

To handle updates in length of string, can be done as follows: If the length of one of the strings decreases (suppose i to i-1), we already have calculated the answers for the previous states, so no need to worry about this. To handle an update where the length increases (suppose i to i+1), we only have to calculate the dp_{i+1,t} where 0 \leq t \leq j , all other states are already calculated. This will be done in O(len) time where len is length of numbers of Aryan or Ali. Overall complexity fits in the time limit.

Explanation

We are a string (Magical Number ) M of size N.
We are also given two other strings, the numbers of Aryan and Ali (which are empty initially). We process D queries. In each query, we either append a digit or erase a digit of one of the strings.

Suppose we don’t have any queries. Just a single string M, and two strings assume them to be s,t. How can we check whether s,t can be obtained as disjoint subsequences of M?

Here’s how. We will use dynamic programming for this. We will create a dp matrix, where dp_{i,j} gives us the minimum index of M, where both strings s,t can be obtained as disjoint subsequences.

Before going to the transitions, let us make another array jump, where jump_{pos,d} gives the minimum index among {pos,pos+1,...N-1} , which have the digit d at their positions. This can be easily built in O(10*N) time. This array will be used later to make computations faster.

Let’s do the transitions part. Suppose we have calculated the values of dp till some valid i,j , i.e all values till dp_{i,j} are calculated. Suppose we want to calculate dp_{i+1,j}. This can be done as follows:

dp[i+1][j] = min ( jump[ dp[i][j] + 1 ][ s[i] ] , jump[ dp[i+1][j-1] + 1 ][s[j-1]])
We have used 0 based indexing here. If dp[i][j] < N, we can form disjoint subsequences, no otherwise.
Now we are clear about the transitions part. How to handle the queries ? (Assume
current length of Aryan’s and Ali’s numbers to be i,j throughout).

First lets see how to handle erase type queries.So either we have to check dp_{i-1,j} or dp_{i,j-1} , both are already calculated, hence we can easily answer them in O(1) time.

Now comes the append type queries. Here the transitions will remain same as shown above. But if you go updating all the states, it will take O(len^{2}) per query (len is length of strings ), hence will TLE. But do we really need to calculate all the states ? NO.

Suppose Aryan’s number’s length increases (i to i+1). Then we only need to
calculate dp_{i+1,t} , where 0 \leq t \leq j. All other previous states are known already and don’t undergo any change. So, we can answer each query in O(len) time or O(1000) calculations per query. This will fit in the time limit.

Setter’s Code:

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



#define        all(x)        x.begin(),x.end()
#define        pb            push_back
#define        ff            first
#define        ss            second
#define        ar            array
#define        vi            vector<int>
#define        F(i,a,b)      for(i=a;i<b;++i)
#define        NL            cout<<"\n";
#define        INF           1e17+25
#define        pii           pair<int,int>
#define        fast          ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define        pll           pair<ll,ll>




mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int getRand(int l, int r)
{
    uniform_int_distribution<int> uid(l, r);
    return uid(rng);
}


typedef long long ll;
typedef long double ld;
const ll mod=1e9+7;
//const ll mod = 998244353LL;
const ld PII = acos(-1);

ll fpow(ll a, ll b) {

    ll res=1;
    while(b>0) {
        if(b&1)
            res=(res*a);
        a=(a*a);
        b>>=1;
    }
    return res;
}


const int N = 5e5+3;
int dp[1002][1002];
int jump[N][10];
string cur[2];




void solve(){
    
    int n,i,q;
    cin >> n >> q;

    assert(n>=1 && n<=5e5 && q>=1 && q<=5e4);

    cur[0]="";
    cur[1]="";

    string s;
    cin >> s;


    assert((int)s.size()==n);

    for(i=0;i<n+2;i++){
        for(int j=0;j<10;j++){
            jump[i][j]=n;
        }
    }

    for(i=0;i<=1001;i++){
        for(int j=0;j<=1001;j++){
            dp[i][j]=n;
        }
    }


    for(i=n-1;i>=0;--i){
        for(int j=0;j<10;j++){
            if(s[i]-'0'==j) jump[i][j]=i;
            else jump[i][j]=jump[i+1][j];
        }
    }
    
    dp[0][0]=-1;


    while(q--){
        string type;
        cin >> type;

        if(type=="append"){
            char y;
            string to;

            cin >> to >> y;

            if(to=="Aryan"){
    cur[0]+=y;
    int s1 = cur[0].size(),s2 = cur[1].size();

    assert(s1<=1000 && s2<=1000);

    for(i=0;i<=s2;++i){
        dp[s1][i]=n;    
       dp[s1][i] = min(dp[s1][i], jump[ dp[s1-1][i] + 1 ][y-'0'] );
       if(i) dp[s1][i] = min(dp[s1][i], jump[ dp[s1][i-1] +1 ][cur[1][i-1]-'0']);
    }
            }

            else{
                assert(to=="Ali");
     cur[1]+=y;
     int s1 = cur[0].size(),s2=cur[1].size();

     assert(s1<=1000 && s2<=1000);

     for(i=0;i<=s1;i++){
        dp[i][s2]=n;
        if(i)
        dp[i][s2]=min(dp[i][s2],jump[ dp[i-1][s2] +1 ][cur[0][i-1]-'0']);

        dp[i][s2]=min(dp[i][s2], jump[ dp[i][s2-1] +1  ][y-'0'] );
    }
           }

        } 

        else {
            assert(type=="erase");
            string to;
            cin >> to;

            if(to=="Aryan"){
                assert(!cur[0].empty());
                cur[0].pop_back();
            }

            else{
                assert(to=="Ali");
                assert(!cur[1].empty());
                cur[1].pop_back();
            }

        }

        int s1 = cur[0].size(),s2 = cur[1].size();

        assert(s1<=1000 && s2<=1000);

        cout << (dp[s1][s2] < n ? "YES\n" : "NO\n");

    } 
}
   

signed main(void)     
{

    fast;

   

    #ifndef ONLINE_JUDGE
      freopen("input.txt","r",stdin);
      freopen("output.txt","w",stdout);
      freopen("error.txt","w",stderr);
    #endif

    cout<< setprecision(12) << fixed;

    

    int CASES=1;
  // cin >> CASES;
    
    for(int i=1;i<=CASES;i++){
        solve();
    }


   
    
}


Tester’s Code:

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

long long readInt(long long l, long long r, char endd) {
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true) {
        char g=getchar();
        if(g=='-') {
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g&&g<='9') {
            x*=10;
            x+=g-'0';
            if(cnt==0) {
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);
 
            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd) {
            if(is_neg) {
                x=-x;
            }
            assert(l<=x&&x<=r);
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l, int r, char endd) {
    string ret="";
    int cnt=0;
    while(true) {
        char g=getchar();
        assert(g!=-1);
        if(g==endd) {
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt&&cnt<=r);
    return ret;
}
long long readIntSp(long long l, long long r) {
    return readInt(l,r,' ');
}
long long readIntLn(long long l, long long r) {
    return readInt(l,r,'\n');
}
string readStringLn(int l, int r) {
    return readString(l,r,'\n');
}
string readStringSp(int l, int r) {
    return readString(l,r,' ');
}
 
void readEOF(){
    assert(getchar()==EOF);
}

int main() {
	// your code goes here
	int t = 1;
	while(t--){
	    int n = readIntSp(1, 5e5);
	    int q = readIntLn(1, 5e4);
	    string str = readStringLn(n, n);
	    for(auto j : str)
	        assert('0' <= j && j <= '9');
	    str = " " + str;
	    vector<vector<int>> dp(1001, vector<int>(1001, n + 1));
	    // dp[i][j] -> min index if first 'i' of Aryan and first 'j' of Ali can be formed from str
	    vector<vector<int>> nxt(n + 3, vector<int>(10, n+1));
	    // nxt[i][j] denotes occurrence of 'j' in str[i..N];
	    nxt[n][str[n] - '0'] = n;
	    for(int i = n - 1 ; i >= 1 ; i--){
	        for(int j = 0 ; j <= 9 ; j++)
	            nxt[i][j] = nxt[i+1][j];
	        nxt[i][str[i] - '0'] = i;
	    }
	    dp[0][0] = 0;
	    int len_Ali = 0, len_Aryan = 0;
	    string Ali = " ", Aryan = " ";
	    for(int i = 0; i < q; i++){
	        string op = readStringSp(1, 10);
	        assert(op == "append" || op == "erase");
	        string name;
	        int d;
	        if(op == "append"){
	            name = readStringSp(1, 10);
	            d = readIntLn(0, 9);
	        }
	        else{
	            name = readStringLn(1, 10);
	        }
	        assert(name == "Aryan" || name == "Ali");
	        if(op == "append"){
	            if(name == "Aryan"){
	                len_Aryan++;
	                assert(len_Aryan <= 1000);
	                Aryan += (char)('0' + d);
	                dp[len_Aryan][0] = nxt[dp[len_Aryan - 1][0] + 1][d];
	                dp[len_Aryan][0] = min(dp[len_Aryan][0], n + 1);
	                for(int j = 1 ; j <= len_Ali ; j++){
	                    dp[len_Aryan][j] = min(nxt[dp[len_Aryan - 1][j] + 1][Aryan.back() - '0'], dp[len_Aryan][j]);
	                    dp[len_Aryan][j] = min(nxt[dp[len_Aryan][j - 1] + 1][Ali[j] - '0'], dp[len_Aryan][j]);
	                    dp[len_Aryan][j] = min(dp[len_Aryan][j], n + 1);
	                }
	            }
	            else{
	                len_Ali++;
	                assert(len_Ali <= 1000);
	                Ali += (char)('0' + d);
	                dp[0][len_Ali] = nxt[dp[0][len_Ali - 1] + 1][d];
	                dp[0][len_Ali] = min(dp[0][len_Ali], n + 1);
	                for(int j = 1 ; j <= len_Aryan ; j++){
	                    dp[j][len_Ali] = min(nxt[dp[j][len_Ali - 1] + 1][Ali.back() - '0'], dp[j][len_Ali]);
	                    dp[j][len_Ali] = min(nxt[dp[j - 1][len_Ali] + 1][Aryan[j] - '0'], dp[j][len_Ali]);
	                    dp[j][len_Ali] = min(dp[j][len_Ali], n + 1);
	                }
	            }
	            cout << (dp[len_Aryan][len_Ali] <= n ? "YES" : "NO") << '\n';
	        }
	        else{
	            if(name == "Aryan"){
	                assert(len_Aryan > 0);
	                Aryan.pop_back();
	                for(int j = 0 ; j <= 1000 ; j++)
	                    dp[len_Aryan][j] = n + 1;
	                cout << (dp[--len_Aryan][len_Ali] <= n ? "YES" : "NO") << '\n';
	            }
	            else{
	                assert(len_Ali > 0);
	                Ali.pop_back();
	                for(int j = 0 ; j <= 1000 ; j++)
	                    dp[j][len_Ali] = n + 1;
	                cout << (dp[len_Aryan][--len_Ali] <= n ? "YES" : "NO") << '\n';
	            }
	        }
	    }
	}
	readEOF();
}

Time Complexity:
O(len) per query. Hence O(len \cdot D) for all queries. Building takes O(10 \cdot N) time. Hence O(N + len \cdot D) overalll. ( 0 \leq len \leq 1000 )