CHEALG Editorial

PROBLEM LINK:

Practice
Contest

Tester: Roman Bilyi
Editorialist: Hussain Kara Fallah

PROBLEM EXPLANATION

Saeed was teaching a string compression algorithm. This algorithm finds all maximal substrings which contains only one character repeated one or more times (a substring is maximal if it we cannot add one character to its left or right without breaking this property) and replaces each such substring by the string “cK”, where K is the length of the substring and c is the only character it contains. For example, “aabaaa” is compressed to “a2b1a3”.

Saeed wanted to check if the students understood the algorithm, so he wrote a string S on the board and asked the students if the algorithm is effective on S, i.e. if the string created by compressing S is strictly shorter than S. Help them answer this question.

DIFFICULTY:

Easy

CONSTRAINTS

1 \leq |N| \leq 10^6

EXPLANATION:

Now this is a straight forward implementation task. We need to perform the algorithm and check the length of the result.

First, let’s break our string into maximal contiguous substrings of identical characters. (a substring is maximal if we cannot extend it from left or right without breaking the identical characters property). We can do this by a simple loop.

Let’s keep 2 iterators. The first iterator always starts a new substring. Initially, it starts from the beginning of the string, now let’s move with our second iterator forward while we have identical characters (keeping their count as well). After we arrive at a new character, it means our substring is finished, and we move our first iterator to the character we stopped at (the new substring start) and we keep extracting substrings until our main string is exhausted.

Now for each processed substring, it would increase our compressed string length by F(substring\,length)+1 where F(x) is the length of integer x.

Let’s take an example “aabaaa”, it would be broken into “aa”,“b”,“aaa” so the length of compressed string would be F(2)+1+F(1)+1+F(3)+1=6.

After finishing we compare our compressed string length to the original and that’s it. Check implementation for better understanding.

Editorialist solution
#include <bits/stdc++.h>
using namespace std;
int main() {
    int T;
    cin >> T;
    while (T--) {
        string str;
        cin >> str;
        int ans = 0;
        for (int j = 0; j < str.size();) {
            int i , l = 0;
            for (i = j; i < str.size() && str[j] == str[i]; i++)
                ++l;
            while(l > 0){
                ans++;
                l /= 10;
            }
            ans++;
            j = i;
        }
        if (ans >= str.size()) puts("NO");
        else puts("YES");
    }
} 
Tester Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
    int T;
    cin >> T;
    while (T--) {
        string str;
        cin >> str;
        int ans = 0;
        for (int j = 0; j < str.size();) {
            int i , l = 0;
            for (i = j; i < str.size() && str[j] == str[i]; i++)
                ++l;
            while(l > 0){
                ans++;
                l /= 10;
            }
            ans++;
            j = i;
        }
        if (ans >= str.size()) puts("NO");
        else puts("YES");
    }
} 
1 Like

Simple Python Solution
The extra character ‘P’ is used for padding.

t = int(input())
while(t>0):
    ts = input()
    ts += 'P'
    es = ""
    count = 1
    for i in range(len(ts)-1):
        if(ts[i] == ts[i+1]):
            count += 1
        elif(ts[i] != ts[i+1]):
            es += ts[i]
            es += str(count)
            count = 1

    if(len(es) < (len(ts) -1)):
        print("YES")
    else:
        print("NO")
    t -= 1
1 Like

https://www.codechef.com/viewsolution/28531011

Why is this code giving WA for the first subtask ??

aaaaaaaaaabcdefgh

This test case fails brother. I haven’t gone through your code though.

2 Likes

Isn’t the answer for the testcase YES ??

No - it’s one of the sample testcases, dude :slight_smile:

1 Like

Why WA for this ??

Consider the testcase:

1
aaacc
1 Like

while(t>0){
String s=br.readLine();
s+=’ ';
String res="";
int count=1;
for(int i=0;i<s.length()-1;i++){
if(s.charAt(i)==s.charAt(i+1))
count++;
else{
res+=s.charAt(i)+count;
count=1;
}
}
if(res.length()<(s.length()-1))
System.out.println(“YES”);
else
System.out.println(“NO”);
t–;

whats wrong here??

i am not getting where i am wrong. can any one please help me out of this problem.
my code :

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

int main() {
long long int t,i,j,n,arr[26];

cin>>t;
while(t--)
{   string a,b="";
    for(i=0;i<26;i++)     
    arr[i]=0;
    cin>>a;
    for(i=0;i<a.length();i++)
    arr[a[i]-'a']+=1;
    
    for(i=0;i<26;i++)
    {
        if(arr[i]>0)
        {
          b=b+'i'+to_string(arr[i]);
          
        }
    }
    if(b.length()<a.length())
    cout<<"YES\n";
    else
    cout<<"NO\n";
}

// your code goes here
return 0;

}

Consider the testcase:

1
ccabbcabab
1 Like

bro isme jo a10 bn rh hga uski length 3 le ji rha hgi bcoz it is a string

cook your dish here

num=int(input())
while num>0:
stri=input()
b=""
i=0
num=num-1
while i<len(stri):
b=b + stri[i]
n=stri.count(stri[i])
b=b + str(n)
i=i+n
if len(b)<len(stri):
print(“YES”)
else:
print(“NO”)

can you tell me why is EOF occurring here?

#include <bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(0); cin.tie(0);
typedef long long int ll;
int main() {
    fastIO;
    ll T;
    cin>>T;
    while(T--)
    {
        string S,compressed="";
        cin>>S;
        map<char,int>count;
        vector<char>x;
        vector<char>lc{'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
        for(int i=0;i<S.length();i++)
        {
            x.push_back(S[i]);
        }
        for(int i=0;i<x.size();i++)
        {
            if(x[i]==x[i+1])
            {
                count[x[i]]++;
            }
        }
        for(auto it=count.begin();it!=count.end();it++)
        {
            count[it->first]++;
            // cout<<it->first<<" "<<it->second<<endl;
            compressed+=it->first;
            compressed.append(to_string(it->second));
        }
         int lengthcompressed=compressed.length();
         int lengthcompared=S.length();
         if(lengthcompared>lengthcompressed)
         {
             cout<<"YES"<<endl;
         }
         else
         {
             cout<<"NO"<<endl;
         }
        //  cout<<compressed;
         x.clear();
         count.clear();
    }
  
    
	
	return 0;
}

What’s wrong in this coding?

First thing that jumps out: you’ve got an out-of-bounds access here:

            if(x[i]==x[i+1])
1 Like
#include <bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(0); cin.tie(0);
typedef long long int ll;
int main() {
    fastIO;
    ll T;
    cin>>T;
    while(T--)
    {
        string S,compressed="";
        cin>>S;
        map<char,int>count;
        vector<char>x;
        vector<char>lc{'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
        for(int i=0;i<S.length();i++)
        {
            x.push_back(S[i]);
        }
        for(int i=0;i<x.size();i++)
        {
            for(int j=i+1;j<x.size();j++)
                if(x[i]==x[j])
                {
                count[x[i]]++;
                 }
        }
        for(auto it=count.begin();it!=count.end();it++)
        {
            count[it->first]++;
            // cout<<it->first<<" "<<it->second<<endl;
            compressed+=it->first;
            compressed.append(to_string(it->second));
        }
         int lengthcompressed=compressed.length();
         int lengthcompared=S.length();
         if(lengthcompared>lengthcompressed)
         {
             cout<<"YES"<<endl;
         }
         else
         {
             cout<<"NO"<<endl;
         }
        //  cout<<compressed;
         x.clear();
         count.clear();
    }
  
    
	
	return 0;
}

NOw?

It gives the wrong answer for the sample testcase - try debugging with that :slight_smile:

What about now?

#include <bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(0); cin.tie(0);
typedef long long int ll;
int main() {
    fastIO;
    ll T;
    cin>>T;
    while(T--)
    {
        string S,compressed="";
        cin>>S;
        map<char,int>count;
        vector<char>x;
        vector<char>lc{'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
        for(int i=0;i<S.length();i++)
        {
            x.push_back(S[i]);
        }
        for(int i=0;i<x.size();i++)
        {
            for(int j=0;j<lc.size();j++)
                if(x[i]==lc[j])
                {
                    // int counter=0;
                    count[x[i]]++;
                }
        }
        for(auto it=count.begin();it!=count.end();it++)
        {
            // count[it->first]++;
            // cout<<it->first<<" "<<it->second<<endl;
            compressed+=it->first;
            compressed.append(to_string(it->second));
        }
         int lengthcompressed=compressed.length();
         int lengthcompared=S.length();
         if(lengthcompared>lengthcompressed)
         {
             cout<<"YES"<<endl;
         }
         else
         {
             cout<<"NO"<<endl;
         }
        //  cout<<compressed;
         x.clear();
         count.clear();
    }
  
    
	
	return 0;
}

CHEALG Editorial - #12 by ssjgz :slight_smile: