You are not logged in. Please login at www.codechef.com to post your questions!

×

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

View Content

Tester's solution

View Content

Editorialist's solution

View Content

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

This question is marked "community wiki".

asked 13 Mar, 18:25

taran_1407's gravatar image

6★taran_1407
4.0k31104
accept rate: 22%

edited 13 Mar, 19:20

admin's gravatar image

0★admin ♦♦
19.8k350498541


Can anyone explain this line

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

link

answered 14 Mar, 08:10

mayank612512's gravatar image

2★mayank612512
1
accept rate: 0%

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.

(15 Mar, 06:34) taran_14076★

@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}

link

answered 14 Mar, 08:39

iamabjain's gravatar image

4★iamabjain
1506
accept rate: 6%

@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.

link

answered 14 Mar, 11:03

yrus98's gravatar image

2★yrus98
1
accept rate: 0%

@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

link

answered 14 Mar, 16:31

mugathi_pa's gravatar image

2★mugathi_pa
11
accept rate: 0%

edited 14 Mar, 16:33

@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) iamabjain4★
1

@iamabjain Thanks a lot :D

(15 Mar, 12:19) mugathi_pa2★

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.

link

answered 14 Mar, 17:07

pankajm2's gravatar image

3★pankajm2
2
accept rate: 0%

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

(15 Mar, 00:42) iamabjain4★

What was being tested in test case #5 ?

link

answered 14 Mar, 17:19

gurditsbedi's gravatar image

2★gurditsbedi
1
accept rate: 0%

@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) iamabjain4★

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

link

answered 14 Mar, 22:55

iamshubhamrock's gravatar image

3★iamshubhamrock
211
accept rate: 0%

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

(16 Mar, 09:53) mcsinyx3★

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

link

answered yesterday

prasadram126's gravatar image

2★prasadram126
121
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,220
×1,191
×724
×148
×75
×4

question asked: 13 Mar, 18:25

question was seen: 2,155 times

last updated: yesterday