GRANAMA - Editorial

editorial
, , , , ,
1

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
2

#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”;
}
}

3

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

4

please help me with the idea of creating the table

5

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;
}

}