time complexity issue

[cc046]

https://www.codechef.com/MARCH19B/problems/JAIN/

#include<bits/stdc++.h>
#define ll long long
using namespace std;
string finals(string s1,string s2)
{
return s1+s2;
}
bool trues (string s)
{
ll l,c1=0,c2=0,c3=0,c4=0,c5=0;
l=s.length();
for(int i=0;i<l;i++)
{
if(s[i]=='a')
{
c1++;
}
else if(s[i]=='e')
{
c2++;
}
else if(s[i]=='i')
{
c3++;
}
else if(s[i]=='o')
{
c4++;
}
else if(s[i]=='u')
{
c5++;
}
}
if(c1!=0&&c2!=0&&c3!=0&&c4!=0&&c5!=0)
{
return true;
}
else
{
return false;
}
}
int main()
{
ll t;
cin>>t;
while(t--)
{
ll n;
cin>>n;
string s[n];
for(ll i=0;i<n;i++)
{
cin>>s[i];
}
string s2;
ll count=0;
for(ll i=0;i<n;i++)
{
for(ll j=i+1;j<n;j++)
{
if(trues(s[i]+s[j])==true)
{
count++;
}
}
}
cout<<count<<endl;
}
return 0;
}
It gives TLE.
Efficient approach or reduces loop?

[ne555]

		for(ll i = 0; i < n; i++) {
			for(ll j = i + 1; j < n; j++) {
				if(trues(s[i] + s[j]) == true) {
					count++;
				}
			}
		}

n may be 1e5 and your approach test every pair, giving you O(n^2)
that's too much, and that kind of time complexity analysis is what you should do before coding.

hint: strings "a", "aaaaa" and "aaaaaaaaaaaaaaaa" are equivalent
same as "aeaeaeaeaeaeaeaeaeae", "ae", "aaaaaaaaaaaaaeeeeeeeeeeeeee"
you only care wether the vocal is present or not, so group equivalent strings and work with the groups

[cc046]

@ne555
I tried this method. This one also giving TLE . First I removed all the duplicates present in the string after that i checked vowels present in string.
In this, time complexity is also (n^n).

Thanks ne555

[ne555]

provide code, not a description.
the remove duplicates should be a O(n) operation (n being lenght of the string), you may do O(n lg n) which is still fine, or O(n^2) which is horrendous.

> In this, time complexity is also (n^n).
not n^n but n^2
and now `n' is 32, quite small

[cc046]

@ne555
time complexity is n^2
but n is 10^5
and we have n strings..... we checked for all the strings that vowels are present or not

[salem c]

For each string, compute this.

short stringCode(const string &s) {
  short result = 0;
  size_t len = s.length();
  for(size_t i=0 ; i < len && result != 0x1F ; i++)
  {
    if ( s[i] == 'a' ) result |= (1<<0);
    if ( s[i] == 'e' ) result |= (1<<1);
    if ( s[i] == 'i' ) result |= (1<<2);
    if ( s[i] == 'o' ) result |= (1<<3);
    if ( s[i] == 'u' ) result |= (1<<4);
  }
  return result;
}

If you then have two codes for two strings

short c1 = stringCode("ae");
short c2 = stringCode("iou");

Then

if ( (c1 | c2) == 0x1F ) {
  // it's a valid recipe
}

The rest is just working through the permutations.

[cc046]

string str(string s)
{
sort(s.begin(), s.end());
int n;
string res;
int k=0;
for( n = 0 ; n < s.length(); n++ )
{
if(k==0)
res[k++]=s[n];
else
{
if(s[n]==res[k-1])
continue;
else
res[k++]=s[n];
}
}
for(n=0;n<k;n++)
cout<<res[n]<<" ";

}
I used this function for removing duplicates.
Complexity is O(n log n).

[dhayden]

cc046, read what salem c wrote. Each recipe results in a code between 0 and 31. Count the number of recipes with each code. Then figure out the answer from the counts. I think the whole problem can be solved in O(n) time where n is the total number of characters in all the recipes. That's a lower bound too because it takes O(n) time just to read the recipes.

[wowisay]

even if we set stringcodes for this still we ll have to go through all n*n-1 permutations. and i guess still it will give you TLE

and if get the counts of all 31 codes ,wont it be tedious to get all the pairs manually

[dhayden]

even if we set stringcodes for this still we ll have to go through all n*n-1 permutations

No you won't.

and if get the counts of all 31 codes ,wont it be tedious to get all the pairs manually

Whether you're checking the pairs of 31 codes or N strings, it's the same sort of code. The difference is that it's a whole lot faster to check pairs of 31 codes (465 pairs) than 10⁵ strings (just under 5 billion pairs)

[ne555]

@OP: in your remove duplicate functions you are accessing `res' out of bounds

// http://www.cplusplus.com/reference/algorithm/unique/
sort(s.begin(), s.end());
s.erase(unique(s.begin(), s.end()), s.end());

> we checked for all the strings that vowels are present or not
I'll say it again, group equivalent strings and work with the groups
suppose that you've got these strings

"a"
"aaa"
"aaaaaaaaa"
"eiou"
"eiouuuuuuuuuuuuuu"

you may group it like this

"a" -> 3
"eiou" -> 2

now you do "a"+"eiou" -> valid
¿how many? 3*2 = 6

now for the grouping you may take salem c's binary code, or if that's too complicated, just use a std::map

[akash19jain]

This question seems to be from an ongoing contest.

[cc046]

@dhayden

> Each recipe result in a code beween 0 and 31

Number of recipe is n so we have n codes.
I didn't understand how can i figure out the ans from the counts or number of recipe.

[dhayden]

I didn't understand how can i figure out the ans from the counts or number of recipe.

Each recipe consists of a string of vowels. You're looking for pairs of strings that contain all the vowels between them.

So the only thing that matters about a particular recipe is whether it does or does not contain the various vowels. Let's encode that into a binary number:

4  3  2  1  0    Bit number
u  o  i  e  a    Corresponding letter

We'll set the bit to 1 if the letter is present and 0 if it is not.

Example: recipe aaeeeeaeaoae
This contains letters a, e, and o So the encoding is:

0  1  0  1  1

And 01011 in binary is 8+2+1=11 in decimal.

This is exactly the encoding that salem c's function does.

Now every recipe that contains only a,e and o will encode to 11. You can count those up. Let's suppose there 37 of them.

Those recipes lack letters u and i, so for Chef to like a meal, the other recipe must contain u and i. Suppose there are 82 recipies that contain only u and i. That means that all 37 recipes containing a,e, and o can combine with all 82 recipes containing u and i. That's a total of 37*82=3034 recipes.

Since any possible recipe encodes to a a 5-bit number, there are at most 2⁵=32 possible encodings. However, notice that encoding 0 means that none of the bits are set, which can only happen of the string is empty. So encoding 0 isn't possible. Therefore there are 31 possible encodings.

Back to the example. I showed that recipes with a,e, and o can combine with recipes with u and i, but those aren't the only recipes that they can combine with. For example, they can also combine with recipes that have a, i and u, or i, o, and u. In fact, they can combine with ANY recipe that contains i and u.

This where some binary operations come in handy. Once two recipes are encoded, it's easy to see if they combine to something tasty. You just have to see if they have all 5 bits set between them. And that's a simple binary or operation (| in C++).

So the algorithm is simple:
1. Encode the recipes to their corresponding number. Count up how many recipes encode to each number.
2. For each pair of encodings, if ORing the encodings together gives you all 5 bits set (i.e., if encoding1 | encoding2 == 31) then all combinations of those encodings are tasty. There are count1*count2 possible combinations of those counts.

So it takes O(n) time to encode the strings. Then it takes O(32*31) time to check each pair of encodings. So the overall time is O(n+32*31) = O(n+constant) = O(n).

The whole problem is just an exercise in the use of binary numbers.

[STD8C542]

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

short SCode(const string &s) {
    cout << s << endl;
  short z = 0;
  size_t l = s.length();
  for(size_t i=0 ; i < l && z != 0x1F ; i++)
  {
    if ( s[i] == 'a' ) z |= (1<<0);
    if ( s[i] == 'e' ) z |= (1<<1);
    if ( s[i] == 'i' ) z |= (1<<2);
    if ( s[i] == 'o' ) z |= (1<<3);
    if ( s[i] == 'u' ) z |= (1<<4);
  }
  cout << z << endl;
  return z;
}

int main()
{
    int t; long int n;
    cin >> t;
    while(t--){
        cin >> n;
        string a[n]; vector<short>x;
        for(int i = 0; i < n;i++){
            cin >> a[i];
            sort(a[i].begin(), a[i].end());
            a[i].erase(std::unique(a[i].begin(),a[i].end()), a[i].end());
            x.push_back(SCode(a[i]));
        }
        sort(x.begin(),x.end());
        long int sum = 0; int c1,c2;
        for(int i = 0; i < n-1 ; i+=c1){
                c1 = count(x.begin(),x.end(),x[i]);
            for(int j = i+1; j < n; j+=c2){
                c2 = count(x.begin(),x.end(),x[j]);
                if ((x[i] | x[j]) == 0x1F ) {
                        sum = sum + c1*c2;
                }
            }
        }
        cout << sum << endl;

    }
}

i'm getting wrong answer in this

[dhayden]

There's another thread that talks about this problem and the subtle "corner case" that we both missed.

[ne555]

the only thing that you should cout is the answer, remove lines 5 and 16
now for the erros in lines 35--43, i'll give you this testcase.

2
2
aeiou
aeioua
4
eio
eioe
au
eu

desired output:
1: {aeiou, aeioua}
2: {eio, au}, {eioe, au}
your output:
4
0

[STD8C542]

@dhayden

There's another thread that talks about this problem and the subtle "corner case" that we both missed.

i can't find it. can you give me the link to that thread? thanks

[STD8C542]

@ne555

the only thing that you should cout is the answer, remove lines 5 and 16

thanks. actually that was me testing my code sorry