GRANAMA - Editorial

PROBLEM LINKS

Practice

Contest

DIFFICULTY

CAKEWALK-SIMPLE

PREREQUISITES

Simple Math

PROBLEM

A pair of strings R and S is called granama if each letter ‘a’ - ‘z’ is used the same number of times in both R and S. However, Chef mistakenly considers them as granama if there are no letters which are used in R but not used in S (or vice-versa).

Determine whether Chef correctly classified two strings R and S as granama or not granama.

QUICK EXPLANATION

The answer is NO if both R and S have the same set of letters and there is at least one letter which is used different number of times in R and S. Otherwise, the answer is YES.

EXPLANATION

The most intuitive way to solve this problem is to simulate both methods of classifying whether a pair of strings is granama: the correct method and Chef’s wrong method. If both methods return the same answer, output “YES”, else output “NO”.

read(R, S)
if correct_method(R, S) = wrong_method(R, S):
    println("YES")
else:
    println("NO")

Correct Method

There are several ways to implement the correct method.

  • Use two tables: freqR[26] and freqS[26]. Populate the tables with the frequencies of letters 'a' - 'z' in R and S. The answer is "YES" if and only if the frequency of each letter is equal in both R and S.
    function correct_method(R, S):
        for i = 0; i < length(R); i++:
            freqR[R[i] - 'a']++
        for i = 0; i < length(S); i++:
            freqS[S[i] - 'a']++
        res = "YES"
        for i = 0; i < 26; i++:
            if freqR[i] ≠ freqS[i]:
                res = "NO"
        return res
    
  • Sort both R and S based on their letters. If they become equal, the answer is "YES", otherwise "NO".

Chef’s Wrong Method

Chef will consider a pair of strings as granama if they have the same set of letters. Therefore, we can use two boolean tables: usedR[26] and usedS[26]. For each letter in R and S, mark it as used in the corresponding table. The answer is “YES” if and only if the flag of each letter is equal in both R and S.

function wrong_method(R, S):
    for i = 0; i < length(R); i++:
        usedR[R[i] - 'a'] = true
    for i = 0; i < length(S); i++:
        freqS[S[i] - 'a'] = true
    res = "YES"
    for i = 0; i < 26; i++:
        if usedR[i] ≠ usedS[i]:
            res = "NO"
    return res

Concise Solution

The above method suffices to get Accepted on this problem. However, there is a concise solution mentioned in the Quick Explanation section based on a clever observation. The proof is left as an exercise for the readers.

SETTER’S SOLUTION

Will be provided soon.

TESTER’S SOLUTION

Can be found here.

3 Likes

#include
#include
#include

using namespace std;

char temp[26],temp1[26];
int i,j,k=0,p=0,m,n;

int chef_granama(char r[],char s[])
{
m=strlen®;
n=strlen(s);

if(strcmp(r,s)==0)
    return 1;

else
{
    int flagk,flagp;
    char c;
    for(int i=0; i<m; i++)
    {
        flagk=0;
        c=r[i];
        for(int j=0; j<k; j++)
        {
            if((k>0)&&(c==temp[j]))
            {
                flagk=1;
                break;
            }
        }
        if(flagk==0)
            temp[k++]=c;
    }
    temp[k]='\0';
    for(int i=0; i<n; i++)
    {
        flagp=0;
        c=s[i];
        for(int j=0; j<p; j++)
        {
            if((p>0)&&(c==temp1[j]))
            {
                flagp=1;
                break;
            }
        }
        if(flagp==0)
            temp1[p++]=c;
    }
    temp1[p]='\0';
    if(strspn(temp,temp1)!=k)
        return 0;
    else if(strspn(temp1,temp)!=p)
        return 0;
    else return 1;
}

}
int actual_granama(char r[],char s[],int cg)
{
if(cg==0)
return 0;
else
{
int flagk,flagp;
int freq[26],freq1[26];
char c;
for(int i=0; i<k; i++)
{
c=temp[i];
freq[c-‘a’]=0;
for(int j=0; j<m; j++)
{
if(r[j]==c)
freq[c-‘a’]++;
}
}
for(int i=0; i<p; i++)
{
c=temp1[i];
freq1[c-‘a’]=0;
for(int j=0; j<n; j++)
{
if(s[j]==c)
freq1[c-‘a’]++;
}
}
for(int i=0; i<k; i++)
{
flagk=0;
c=temp[i];
if(freq[c-‘a’]==freq1[c-‘a’])
;
else
{
flagk=1;
break;
}
}
if(flagk==0)
return 1;
else
return 0;
}
}

int main()
{
int num,coun=0,cg,ag,*ans;
scanf("%d",&num);
ans=new int[num];
char r[26],s[26];
while(coun<num)
{
scanf("%s",&r);
scanf("%s",&s);
cg=chef_granama(r,s);
ag=actual_granama(r,s,cg);
cout<<cg<<ag;
if(cg==ag)
ans[coun]=1;
else
ans[coun]=0;
coun++;
k=p=0;
}
for(int i=0;i<num;i++)
{
if(ans[i]==1)
cout<<“YES\n”;
else cout<<“NO\n”;
}
}

can some1 tell me hwy i’m getting a wrong answr notice?
i executed it and got the right answer in my system.

please help me with the idea of creating the table

Can anyone tell me the test cases where this code is wrong ASAP?
#include
#include
using namespace std;

int main()
{
int t;
cin>>t;
while(t–){
string r,s;
int i,j,k,count=0;
int a[26], b[26];
cin>>r>>s;
for(i=0;i<26;i++){
a[i]=0;
b[i]=0;
}
for(i=0; r[i]!=’\0’; i++)
{
//cout<<r[i]<<" “;
a[r[i]-97]++;
}
for(i=0; s[i]!=’\0’; i++)
{
//cout<<r[i]<<” ";
b[s[i]-97]++;
}

int f=1,count1=0, count2=0, count3=0;
for(i=0; i<26; i++)
{
   if(a[i]==b[i] && a[i]!=0 && b[i]!=0)
    count1++;
   else if((a[i]!=0 && b[i]==0) || (b[i]!=0 && a[i]==0))
    count2++;
    else if(a[i]==0 && b[i]==0)
    count3++;

}

if(((count1 + count3) == 26) || ((count2 + count3) == 26))
cout<<“YES”<<endl;
else
cout<<“NO”<<endl;
}

}