PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Abhinav Jain
Tester: Encho Mishinev
Editorialist: Taranpreet Singh
DIFFICULTY:
Simple
PREREQUISITES:
Maths. (Bitmasks would be an advantage)
PROBLEM:
Given N dishes, each dish being represented by string D_i consisting of lowercase vowels, Find all ordered pairs which can form a meal. Pair of dishes (i,j) can form a meal if D_i+D_j contains every vowel at least once.
QUICK EXPLANATION
- Repeated occurrences of a vowel doesn’t matter. In the end, each dish may be represented by a tuple of five boolean values, each stating whether a particular vowel is present or not.
- There are 2^5 = 32 tuples. We can count the frequency of each tuple in N dishes. Now, we can consider every pair of a tuple and if the union of this pair of tuple contains all vowels, we can pair any dish represented by the first tuple, with any dish represented by the second tuple.
- Edge case is the tuple representing the dishes with all vowels present. In this case, make sure to exclude the overcounted pairs (i, i).
EXPLANATION
If we simply iterate using two nested FOR loops, and generating all the possible pairs , that would result in a O(N*N) time complexity Solution which is very slow.
Since in the final meal, we only care about at least one occurrence of each vowel, repeated occurrences of any vowel don’t matter. So, we can remove repeated occurrences.
Now, Let us count the number of different type of dishes we can have, where each type differs only if one vowel is present in one dish while not present in another dish. Since there are five vowels, Number of types of dishes is just the size of the power set of set of vowels, which is 2^5 = 32.
So, We have divided the dishes into 32 categories. If two dishes belong to the same category, they contain the same set of vowels.
We can store each string as a bitmask . For example: Dish “aaeuua” is represented as 11001. So, Every Dish can be represented as a bit mask. So, they may vary from (00000) to (11111).
Now, Let’s try all pairs of sets present in power set one by one. If the union of any pair (i,j) of the set contains all vowels, All dishes categorized in the ith category can be merged with all dishes categorized in the jth category.
The number of pairs of such categories is just 32*32 = 1024 which we can try by brute force. Also, we need to take care not to pair a dish containing all vowels with itself. Also, Pair (i, j) and Pair (j, i) of dishes should be counted once only.
Bitmasks
All the categories we made above, were just bitmasks having 5 bits, ith bit on representing the presence of ith vowel in a dish. Union of two types of dishes is just the OR of bitmasks of both dishes. Checking if all dishes is present is equivalent to checking if all bit of union are set or not.
Hope this forms a nice introduction to bitmasks.
Time Complexity
Time complexity is O(N+4^C) per test case where C = 5 is the number of vowels.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution
Click to view
// Author : Abhinav Jain
// Institution: Jaypee Institute of information Technology
#include
using namespace std;
#define lli long long int
#define cases lli testcases;cin>>testcases; while(testcases--)
#define trace(x) cerr <' << #x << ':' << x << endl;
lli n;
lli freq[1 << 5];
map indxOf;
void input()
{
indxOf['a']=0;
indxOf['e']=1;
indxOf['i']=2;
indxOf['o']=3;
indxOf['u']=4;
memset(freq,0,sizeof(freq));
string str;
cin >> n;
for (lli i = 1; i <= n; ++i)
{
cin >> str; // aeiou
// 01234
lli mask = 0;
lli k=0;
while(k < str.length())
{
mask = mask|(1 << ( indxOf[str[k]] ));
++k;
}
freq[mask]++;
}
}
lli compute()
{
lli AC = 0;
for (lli bit1=0; bit1 <= 31; bit1++)
{
for (lli bit2 = 0; bit2 <= 31; bit2++)
{ if ( (bit1 | bit2) == 31)
AC+= (bit1 != bit2) ? 1LL * freq[bit1] * freq[bit2]:1LL * freq[bit1] * (freq[bit1] - 1);
}
}
return AC/2LL;
}
int32_t main() {
ios_base ::sync_with_stdio(false);
cin.tie(NULL);
cases
{
input();
lli AC = compute();
cout << AC << endl;
}
#ifndef ONLINE_JUDGE
cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n\n";
#endif
return 0;
}
Tester’s solution
Click to view
#include
#include
#include
using namespace std;
typedef long long llong;
int t;
int n;
char inp[1011];
int L;
int ctr[41];
int main()
{
int test;
int i,j;
scanf("%d",&t);
for (test=1;test<=t;test++)
{
llong ans = 0;
scanf("%d",&n);
memset(ctr,0,sizeof(ctr));
for (i=1;i<=n;i++)
{
scanf("%s",inp+1);
L = strlen(inp+1);
int mask = 0;
for (j=1;j<=L;j++)
{
if (inp[j] == 'a')
mask |= 1;
else if (inp[j] == 'e')
mask |= 2;
else if (inp[j] == 'i')
mask |= 4;
else if (inp[j] == 'o')
mask |= 8;
else if (inp[j] == 'u')
mask |= 16;
}
ctr[mask]++;
}
for (i=0;i<32;i++)
{
for (j=0;j<32;j++)
{
if (i > j)
continue;
if ( (i|j) == 31 )
{
if (i != j)
ans += (llong)ctr[i] * (llong)ctr[j];
else
ans += ( (llong)ctr[i] * (llong)(ctr[i]-1) ) / 2LL;
}
}
}
printf("%lld\n",ans);
}
return 0;
}
Editorialist’s solution
Click to view
import java.util.*;
import java.io.*;
import java.text.*;
//Solution Credits: Taranpreet Singh
public class Main{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int n = ni();
long[] f = new long[32];
for(int i = 0; i< n; i++){
String s = n();
int mask = 0;
for(int j = 0; j< s.length(); j++){
if(s.charAt(j)=='a')mask |= 1;
if(s.charAt(j)=='e')mask |= 2;
if(s.charAt(j)=='i')mask |= 4;
if(s.charAt(j)=='o')mask |= 8;
if(s.charAt(j)=='u')mask |= 16;
}
f[mask]++;
}
long ans = (f[31]*(f[31]-1))/2;
for(int i = 0; i< 32; i++)
for(int j = i+1; j< 32; j++)
if((i|j)==31)
ans+=f[i]*f[j];
pn(ans);
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
long mod = (long)1e9+7, IINF = (long)1e18;
final int INF = (int)1e9, MX = (int)2e3+1;
DecimalFormat df = new DecimalFormat("0.00000000000");
double PI = 3.1415926535897932384626433832792884197169399375105820974944, eps = 1e-8;
static boolean multipleTC = true, memory = false;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
int T = (multipleTC)?ni():1;
//Solution Credits: Taranpreet Singh
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
if(memory)new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
else new Main().run();
}
long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 
