MGSTR121 - Editorial

PROBLEM LINK:

Practice
Div1
Div2
Div3

Setter: Ankush Chhabra
Tester: Manan Grover
Editorialist: Ajit Sharma Kasturi

DIFFICULTY:

EASY

PREREQUISITES:

Prefix sums

PROBLEM:

We are given a string of size N consisting of only uppercase letters. A K - magical string is that string which has the length of longest non-decreasing subsequence equal to K . Given queries of the form L, R we need to determine if the substring from L to R can be converted into a K - magical string by rearranging the characters. If multiple such strings exist, we need to output the lexicographically largest one possible.

QUICK EXPLANATION:

  • Let us calculate cnt_j which is the count of character j from L to R for every j from 1 to 26. This can be done by prefix sums.

  • Let max be the maximum element in cnt.

  • If R-L+1<K or max \gt K, no answe is possible.

  • Let T be the string in which all the characters in the positions from L to R are sorted in decreasing order.

  • If max =K, we can directly output T as our answer. Else max \lt K, in this case we reverse the last K chracters in T and output the modified T as our answer.

EXPLANATION:

Let us initially preprocess the array pref before answering queries. pref_{i,j} denotes the total number of characters equal to j^{th} uppercase alphabet for all the indices from 1 to i.

If R-L+1 \lt K, we clearly can’t have an answer as the size of a K- magical string must be atleast K.

Let us now consider R-L+1 \geq K.

Let us calculate cnt using pref where cnt_j is the total number of characters equal to j^{th} uppercase alphabet for all the indices from L to R. Let max be the maximum value in the cnt array.

Let us also consider string T which is all the character in the substring from L to R sorted in decreasing order.

Now consider the following three cases:

Case 1: \hspace{1 mm} max \gt K

  • In this case, we cannot have an answer. This is beacuse we have an alphabet which is repeated more than K times. Then, the maximum non-decreasing subsequence of any rearranged string will be more than K because we always have a non-decreasing subsequence consisting of only this alphabet which has size max \gt K.

Case 2: \hspace{1 mm} max = K

  • In this case, we can just output the lexicographically largest string possible i.e, T. This is because the maximum non-decreasing subsequence of T is the maxmimum count over all alphabets which is max = K.

Case 3: \hspace{1 mm} max \lt K

  • In this case we need to modify T to increasing the maximum non-decreasing subsequence from max to K and also keep T as lexicographically large as possible. We can go about it by simply reversing the last K positions of T. Then, the last K positions are non-dereasing thus changing the maximum size of non-decreasing subsequence to K.

TIME COMPLEXITY:

O(26 \cdot S + X) where S is the total number of queries overall all testcases and X is the the sum of (R−L+1) over all Q queries over all test cases.

SOLUTION:

Editorialist's solution
#include <bits/stdc++.h>
using namespace std;

int main()
{
     ios_base::sync_with_stdio(false);
     cin.tie(NULL);
     cout.tie(NULL);

     int tests;
     cin >> tests;

     while (tests--)
     {
          int n;
          cin >> n;

          string s;
          cin >> s;

          vector<vector<int>> pref(n, vector<int>(26));

          for (int i = 0; i < n; i++)
          {
               if (i)
                    for (int j = 0; j < 26; j++)
                    {
                         pref[i][j] = pref[i - 1][j];
                    }

               pref[i][s[i] - 'A']++;
          }

          int q;
          cin >> q;

          while (q--)
          {
               int l, r, k;
               cin >> l >> r >> k;

               l--;
               r--;

               if (r - l + 1 < k)
               {
                    cout << "No" << "\n";
                    continue;
               }

               int max_cnt = 0;
               for (int i = 0; i < 26; i++)
               {
                    if (l)
                         max_cnt = max(max_cnt, pref[r][i] - pref[l - 1][i]);
                    else
                         max_cnt = max(max_cnt, pref[r][i]);
               }

               if (max_cnt > k)
               {
                    cout << "No" << "\n";
                    continue;
               }

               cout << "Yes" << "\n";

               string t = s.substr(l, r - l + 1);
               sort(t.rbegin(), t.rend());

               if (max_cnt < k)
                    reverse(t.end() - k, t.end());

               cout << t << "\n";
          }
     }
}


Setter's solution
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define ff first
#define ss second
#define ii insert
#define mem(l,r) memset(l,r,sizeof(l))
#define sorta(a,n) sort(a+1,a+1+n)
#define sortv(v) sort(v.begin(),v.end())
#define revs(s) reverse(s.begin(),s.end())
#define fastio ios::sync_with_stdio(false), cin.tie(NULL);
const int N=1e5+5;
const int mod=1e9+7;
const ll int_max=1e18;
const ll int_min=-1e18;
#define rep(i,j,k) for(ll i=j;i<=k;i++)
#define repr(i,j,k) for(ll i=j;i>=k;i--)
using namespace std;
ll sum=0;
void solve()
{
 	ll n;
 	cin>>n;
 	assert(n>=1 && n<=100000);
 	vector<vector<ll>>prefix(n+2,vector<ll>(28,0));
 	string s;
 	cin>>s;
 	rep(i,0,n-1)
 	{
 		assert(s[i]>='A' && s[i]<='Z');
 	}
 	prefix[0][s[0]-'A']=1;
 	rep(i,1,n-1)
 	{
 		rep(j,0,25)
 		{
 			prefix[i][j]=prefix[i-1][j];
 		}
 		prefix[i][s[i]-'A']+=1;
 	}
 	ll q;
 	cin>>q;
 	assert(q>=1 && q<=100000);
 	while(q--)
 	{
 		ll l,r,k;
 		cin>>l>>r>>k;
 		assert(k>=1 && k<=n);
 		assert(l>=1 && l<=n);
 		assert(r>=1 && r<=n);
 		assert(l<=r);
 		l--;
 		r--;
 		ll sz=(r-l+1);
 		if(sz<k)
 		{
 			cout<<"No"<<'\n';
 			continue;
 		}
 		ll mx=0;
 		rep(i,0,25)
 		{
 			ll freq=prefix[r][i]-prefix[l][i]+((s[l]-'A')==i);
 			mx=max(mx,freq);
 		}
 		if(mx>k)
 		{
 			cout<<"No"<<'\n';
 			continue;
 		}
 		cout<<"Yes"<<'\n';
 		sum+=(r-l+1);
 		if(k==mx)
 		{
 			string ans;
 			rep(i,l,r)
 			{
 				ans+=s[i];
 			}
 			sort(ans.begin(),ans.end(),greater<char>());
 			cout<<ans<<'\n';
 			continue;
 		}
 		map<char,ll>freq;
 		rep(i,l,r)
 		{
 			freq[s[i]]++;
 		}
 		ll cnt=(sz-k);
 		for(char i='Z';i>='A';i--)
 		{
 			if(cnt==0)
 			break;
 			if(freq[i]>0)
 			{
 				cnt--;
 				cout<<(i);
 				freq[i]--;
 			}
 			if(freq[i]!=0)
 			i++;
 		}
 		cnt=k;
 		for(char i='A';i<='Z';i++)
 		{
 			if(cnt==0)
 			break;
 			if(freq[i]>0)
 			{
 				cnt--;
 				cout<<i;
 				freq[i]--;
 			}
			if(freq[i]!=0)
			i--;
 		}
 		cout<<'\n';
 	}
}
int main() {
    fastio
int t;
cin>>t;
while(t--)
{
    solve();    
}
	assert(sum>=0 && sum<=1000000);
}
Tester's solution
#include <bits/stdc++.h>
using namespace std;
int main(){
  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  int t;
  cin>>t;
  while(t--){
    int n;
    cin>>n;
    string s;
    cin>>s;
    int a[n][26];
    int cnt[26] = {};
    for(int i = 0; i < n; i++){
      for(int j = 0; j < 26; j++){
        a[i][j] = cnt[j] + (s[i] - 'A' == j);
        cnt[j] = a[i][j];
      }
    }
    int q;
    cin>>q;
    while(q--){
      int l, r, k;
      cin>>l>>r>>k;
      if(r - l + 1 < k){
        cout<<"No\n";
        continue;
      }
      l--;
      r--;
      int mx = 0;
      for(int i = 0; i < 26; i++){
        mx = max(mx, a[r][i] - a[l][i] + (s[l] - 'A' == i));
      }
      if(mx > k){
        cout<<"No\n";
      }else{
        cout<<"Yes\n";
        string temp = s.substr(l, r - l + 1);
        sort(temp.begin(), temp.end());
        if(mx == k){
          k = 0;
        }
        for(int i = r - l; i >= k; i--){
          cout<<temp[i];
        }
        for(int i = 0; i < k; i++){
          cout<<temp[i];
        }
        cout<<"\n";
      }
    }
  }
  return 0;
}

Please comment below if you have any questions, alternate solutions, or suggestions. :slight_smile:

Can anyone point me why this is getting TLE Solution: 52776491 | CodeChef? Thanks.

I would recommend you to pass string s by reference inside function solve()
Like :- void solve(string &s, int l, int r, int k, int p[][26]) .