# GRANAMA - Editorial

Practice

Contest

CAKEWALK-SIMPLE

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

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.