PROBLEM LINK:Practice Setter: Abhinav Jain 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
EXPLANATIONIf 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 ComplexityTime 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 Tester's solution Editorialist's solution Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)
This question is marked "community wiki".
asked 13 Mar, 18:25

@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} answered 14 Mar, 08:39

@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 * (n1) / 2. answered 14 Mar, 11:03

@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 answered 14 Mar, 16:31
@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.
(15 Mar, 00:40)

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. answered 14 Mar, 17:07
@pankajm2 Simple and elegant approach without involving bitmasking. Good going!
(15 Mar, 00:42)

What was being tested in test case #5 ? answered 14 Mar, 17:19
@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. :)
(15 Mar, 00:44)

This can also be simple approach for this problem https://www.codechef.com/viewsolution/23524184 answered 14 Mar, 22:55
Mine is even simpler (33 LoC of C): https://www.codechef.com/viewsolution/23376938
(16 Mar, 09:53)

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 answered yesterday
