CRZYSUBSTR Editorial

editorial
, , ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Bruce Wayne
Tester: Abhinav Sharma, Utkarsh Gupta
Editorialist: Pratiyush Mishra

DIFFICULTY:

2126

PREREQUISITES:

Dynamic Programming, Strings

PROBLEM:

Gotham City is the home of Batman, and Batman likes to keep his people together.

There are N houses in the city. The resident of the i^{th} house is of type A_i. It is known that people of the same type are friends and people of different types are not friends.

To maintain peace, Batman can do the following type of operation:

  • Choose indices i and j (1\leq i \le j \le N) and reverse the substring A[i,j].

Determine the length of the longest range of friends after applying at most k operations on the string for all 0 \le k \le N.

EXPLANATION:

First let’s see how we can increase the length of substrings having same character by the reversal operation as given in the question.
For a string say, s and for character say, x, we first take the longest and 2nd longest substrings having all characters as x. We are taking the longest and 2nd longest since we want to maximize the length of the substring formed in the given operation. Say they are at position i_1 and i_2 with length l_1 and l_2. Assuming i_1 is less than i_2, we can just reverse the substring s[i_1....i_2 - 1] to get substring of length (l_1+l_2) having all x. We can keep repeating this operation till we get the longest substring that contains all the x that are present in string s. Also we would observe that the number of operations required to get the above longest substring would be the number of substrings of x in the original string which would be always less than n, i.e the length of the string s.

Now coming back to this question, what we can do is repeat the operations as defined in the above paragraph for each character from a to z and for each operation take the length of the maximum possible substring that can be formed among a to z as our answer for that operation.

TIME COMPLEXITY:

O(NlogN), for each test case.

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s Solution

1 Like
2

Can someone please tell me why this solution is giving TLE.

void solve(int test_case){
    ll n ; cin >> n ; 
    string s; cin >> s;

    vector<pair<char,ll>> compress; compress.pb({s[0], 1});

    for(ll i = 1 ; i < n ; i++){
        if((*(--compress.end())).first == s[i]){
            (*--compress.end()).second++;
        }else{
            compress.pb({s[i], 1});
        }
    }

    map<char, vector<ll>> m;

    map<char, ll> lele;

    for(auto x : compress){
        m[x.f].pb(x.s);
        lele[x.f]++;
    } 

    for(auto &x: m){
        sort(rev(x.s));
        for(ll i = 1 ; i < lele[x.f]; i++) x.s[i] += x.s[i-1];
    }

    ll ans = 0;
    for(ll i = 0 ; i <= n ; i++){
        for(auto x: m){
            if(i < lele[x.f]){
                ans = max(ans, x.s[i]);
            }
        }       
        cout << ans << " "; 
    }

    cout << endl;

}
3

Instead of using a map, try hashing by making an array of vectors. The time complexity of map operation is O(log n), and the array is O(1).

1 Like
4

Thanks for answering, but

  1. Map would take log(n) time, which should pass in the given time limits
  2. I also used unordered map along with normal hash as well as custom hash, which didn’t work either as it should take O(1) per operation
5

In an ideal case, an unordered map takes O(1), that’s correct. But it’s not always the case. Please refer to Blowing up unordered_map, and how to stop getting hacked on it - Codeforces

According to my experience, I have seen multiple cases when my map (ordered/unordered) implementation gave TLE but vector implementation gave AC.
I would suggest that whenever you know what keys the map is going to have and its contiguous => use a vector, as it ensures O(1)

1 Like
6

Yeah, I agree but some solutions I saw, implemented exactly the same thing even using priority queue and maps
link 1
link 2

and also in this submission : link , I have used unordered_map along with the custom hash from the blog you mentioned, still giving TLE.

It would be great if I can get the test-case for which it is failing.

7

Here is the test case 12: JustPaste.it - Share Text & Images the Easy Way

1 Like
8

The page is no longer available…

9

What is wrong with my approach/code? Test cases 1,2,17,19 are giving WA.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	// your code goes here
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
	int cases;
	cin>>cases;
	while(cases-- > 0){
	    int n;
	    cin>>n;
	    string s;
	    cin>>s;
	    if(n==1){
	        cout<<"1 11\n";
	        continue;
	    }
	    int ans=1,len=1,maxx[26]={0};
	    for(int x=0;x<n-1;x++){
	        maxx[s[x]-'a']++;
	        if(s[x]==s[x+1]) len++;
	        else len=1;
	        ans=max(ans,len);
	    }
	    len=1;
	    maxx[s[n-1]-'a']++;
	    int m=0,c=0;
	    for(int i=0;i<26;i++){
	        if(maxx[i]>m){
	            m=maxx[i];
	            c=i;
	        }
	    }
	    vector<int> v;
	    for(int i=0;i<n-1;i++){
	        if(s[i]==(char)(97+c)){
	            if(s[i]==s[i+1]) len++;
	            else{
	                v.push_back(len);
	                len=1;
	            }
	        }
	    }
	    if(len>1 || s[n-1]==(char)(97+c)) v.push_back(len);
	    sort(v.begin(),v.end());
	    int temp=0,i;
	    for(i=v.size()-1;i>=0 && v.size()-1-i<=n;i--){
	        temp+=v[i];
	        if(temp>ans) cout<<temp<<" ";
	        else cout<<ans<<" ";
	    }
	    for(;v.size()-1-i<=n;i--) cout<<temp<<" ";
	    cout<<"\n";
	}
	return 0;
}

Thanks in advance.

10

Updated, Please convert the test case into the appropriate input format.

11
  • Did you try to see if there is any difference in the logic of your code vs the correct code?
  • Did you try making test cases and your solution vs the correct solution to see where your code fails?

Try debugging more.

12

It should not be giving TLE according to the constraints, IDK why it is, but one suggestion for next time: Please don’t keep bottleneck constraints like these…as you can see the basic motive to solve the problem was achieved, was even able to implement it but it TLEd for an unknown reason and I lost my rating.