JAIN - EDITORIAL

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 <bits/stdc++.h>
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<char,lli > 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";
    #endif
 
 
  return 0;
} 

Tester’s solution

Click to view
#include <iostream>
#include <stdio.h>
#include <string.h>
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. :slight_smile:

2 Likes

Can anyone explain this line

long ans = (f[31]*(f[31]-1))/2;

@mayank612512 , this line counts all the possible meals prepared by pair dishes which contains all the vowels.

eg: three dishes contains all the vowels
aeiou
aoieiou
aeeiioou

So, total possible combinations would be 3. Which can be derived by the formula 3*4/2 {Sum of N natural numbers}

@mayank612512 , f[31] represents the last permutation where all the vowels are present in the string. So from this group, we can select both dishes to prepare the meal. The number of ways in which it can be done is nC2 = n * (n-1) / 2.

@iamabjain, I divided each input into contains and notContains variables with the vowels they contains.
I am mapping each similar contains value and incrementing its count. if map does not has its value then i am pushing it into map and keeping in combinations array and incrementing count.
For each notContains string of value, I am going through combinations and finding there occurence in map.
4 test cases are accepted 5 th is showing WA.
below is link to my code
https://www.codechef.com/viewsolution/23444092

can i know whats wrong with my approach

thanks

1 Like

what I did was I took a hashmap and represent all different combinations of vowels as key and their count as values. Then I loop over the hashmap to find which two of them contains “aeiou”, if I found one then I took product of their values. And if a string is “aeiou”, then it will form pair with all other strings.

What was being tested in test case #5 ?

This can also be simple approach for this problem
https://www.codechef.com/viewsolution/23524184

Hi admin,
i have implemented same “setter” solution in C, but i am getting WA. Can you check it please
below is my solution in c

https://www.codechef.com/viewsolution/23632008

@mugathi_pa
, Your code’s logic is absolutely correct. The only thing wrong here is which is making the fifth testcase is the datatype of your ans. It should be long datatype instead of int.
When you use int datatype , overflow occurs and your code is giving WA.

@pankajm2
Simple and elegant approach without involving bitmasking. Good going!

@gurditsbedi ,
In the 5th testcase file, the answer was lying in the range of long datatype.
If anyone had used int datatype , then an overflow would have occured, which is why the result for fifth test case was WA.

Just change the datatype of your answer variable to long. And it will give you an AC. :slight_smile:

f[31] is number of strings which have all vowels present. For example aeiou.

We have total f[31]*f[31] pairs of them, but it include pairs (i,i) which we know are f[31]. So, Number of pairs = f[31]*f[31] - f[31]. Now the pairs we found are ordered, but we need unordered, so divided by two.

@iamabjain Thanks a lot :smiley:

1 Like

Mine is even simpler (33 LoC of C): https://www.codechef.com/viewsolution/23376938