CHEFING - EDITORIAL

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Aditya Dimri
Tester: Alexey Zayakin and Yash Chandnani
Editorialist: Taranpreet Singh

DIFFICULTY:

Simple.

PREREQUISITES:

Basic Data structures.

PROBLEM:

Given N dishes each represented by a string of lowercase characters, each character representing a different ingredient, find out the number of special ingredients. A special ingredient is an ingredient which is present in all dishes.

QUICK EXPLANATION

  • Initially, all characters are considered special.
  • For every string, we can mark the characters not present in the string as non-special. Hence, the characters marked special after considering all strings are the required set of characters.

EXPLANATION

The problem is really simple. We just need to check for each character from ‘a’ to ‘z’ whether this character is present in all strings or not.

This can be done in many ways, such as

  • For each character, iterate over all strings and check if this character is present in all strings. If yes, increment the answer by one. The final value of the answer is the number of special ingredients.
  • Maintain a special integer array of size A being the size of the alphabet, and for every unique occurrence of a character in the string, increase the character position in the array by one. The final answer is the number of characters, which have special array value equal to N.

The method which can be a learning experience is, by using bitmasks. Let us represent each character by a bit. Initially, all bits are set. Now, we represent each string as a bitmask, corresponding bit on for each character present in the string. Can you figure out the bitwise operation required here?

Click to view

We need to preserve only the bits which are set in both masks. This is what AND operation does.

Time Complexity

Time complexity is O(|S|) per test case.

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution
Tester’s solution
Editorialist’s solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :slight_smile:

1 Like
2

btw I get AccessDenied if I click on solutions

3

Easy to understand…

code

#include
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t–)
{
string s;
long int i,ans=0,j,c=0,n;
cin>>n;
map<char,int>m;
map<char,int>::iterator it;
for(i=0;i<n;i++)
{
cin>>s;
for(j=0;j<s.length();j++)
if(m[s[j]]==c)
m[s[j]]++;
c++;
}
for(it=m.begin();it!=m.end();it++)
if(it->second==c)
ans++;
cout<<ans<<endl;
}
return 0;
}

1 Like
4

nice logic…!!!

1 Like
5

How to understand this written logic , Actually , I’m new to DSA . Can you plz suggest me some tips and help me to understand above logic.

6

My Logic is given Below -
#include <bits/stdc++.h>
using namespace std;

int main() {
int t;
cin>>t;
while(t–)
{
int n,m , ch[26]={0} , counter=0;
cin>>n;
m=n;
while(n>0)
{ cin.ignore();
string s;
cin>>s;
for(int i=0 ; i < s.length() ; i++)
{
int idx; char cha = s.at(i);

            idx = cha - 'a';
            if(ch[idx]==abs(n-m))
            {
                ch[idx]++;
            }
        }
        n--;
    }
    
    for (auto i : ch) {
        if(i==m)
        counter++;
    }
    cout<<counter<<"\n";
}
return 0;

}

7

What is wrong with my code? It passes sub task 0 and 6, but gives WA in others-

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

int main()
{
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    int t;
    cin>>t;
   while(t--){
    int n;
    int finsum=0;
    int sum=0;
    cin>>n;
    int minin=0;
    int minl=10e5;
    string arr[n];
    for(int i=0;i<n;i++){
        cin>>arr[i];
        if(arr[i].length()<minl){
            minl=arr[i].length();
            minin=i;
        }
    }
    for(int i=0;i<minl;i++){
        sum=0;
        for(int j=0;j<n;j++){
            if(j==minin){
                continue;
            }for(int k=0;k<arr[j].length();k++){
                if(arr[j][-1]==arr[minin][i]){
                    sum++;
                    break;
                }else if(arr[minin][i]==arr[j][k]){
                    sum++;
                    break;
                }
            }if(sum==n-1){
                finsum++;
            }
            }
            
        }
    cout<<finsum<<'\n';
   }
   

    return 0;
}