Links
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 )