4
\$\begingroup\$

Problem

I have \$N\$ words. For each valid \$i\$, word \$i\$ is described by a string \$D_i\$ containing only lowercase vowels, i.e. characters 'a', 'e', 'i', 'o', 'u'.

We check the number of strings \$D_i\$ and \$D_j\$ which, when concatenated into a new string \$M\$, contain all 5 vowels. What is the total number of (unordered) pairs of words such that when concatenated, they contain all the vowels?

Input

  • The first line of the input contains a single integer \$T\$ denoting the number of test cases. The description of \$T\$ test cases follows.
  • The first line of each test case contains a single integer \$N\$.
  • \$N\$ lines follow. For each valid \$i\$, the \$i^{th}\$ of these lines contains a single string \$D_i\$.

Output

For each test case, print a single line containing one integer - the number of concatenated words that contain all vowels.

Test Case

3
aaooaoaooa
uiieieiieieuuu
aeioooeeiiaiei

Output

2

Constraints

  • \$1≤T≤1,000\$
  • \$1≤N≤10^5\$
  • \$1≤|D_i|≤1,000\$ for each valid \$i\$
  • the sum of all |\$D_i\$| over all test cases does not exceed \$3⋅10^7\$

I have written some code but I want to optimize it:

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

int main()
{
  int t;
  cin>>t;
  while(t--)
  {
    int n;
    cin>>n;
    vector<string> v;
    long long  con_s[n];
    for(int i=0;i<n;i++)
    {
      string s;
      cin>>s;
      con_s[i]=0;
      for(int j=0;j<s.length();j++)
      {
        con_s[i] = con_s[i] | (1<<(s[j]-'a'));
      }
    }
    long long complete = 0;
    complete = (1<<('a'-'a')) | (1<<('e'-'a')) | (1<<('i'-'a')) | (1<<('o'-'a')) | (1<<('u'-'a'));
    // cout<<complete;
    int count = 0;
    for(int i=0;i<n-1;i++)
    {
      for(int j=i+1;j<n;j++)
      {
        if((con_s[i] | con_s[j])==complete)count++;
      }
    }
    cout<<count<<"\n";
  }
  return 0;
}

Can you please suggest a more optimized solution...

\$\endgroup\$
  • \$\begingroup\$ Welcome! As it's written, your code is a little difficult to understand, particularly with the bit shifting. My suggestion is to use more informative variable names. Short one-letter variable names are good for loops and writing quick code, but they make it very difficult for others (even yourself) to review your code later on. I'd also recommend moving some of the code out of main and into functions. \$\endgroup\$ – AleksandrH Mar 3 '19 at 14:17
  • \$\begingroup\$ Is the "T" variable the number of tests, or something else? I don't see it mentioned in the description of the problem. \$\endgroup\$ – Austin Hastings Mar 3 '19 at 17:01
  • \$\begingroup\$ @AustinHastings yes, T is the number of testcases. Can you help me solve this ? \$\endgroup\$ – AnonymousJoe Mar 3 '19 at 17:07
  • 1
    \$\begingroup\$ @AleksandrH Please put all suggestions for improvements in answers, not comments. \$\endgroup\$ – 200_success Mar 3 '19 at 19:01
7
\$\begingroup\$

Your Code:

  1. Don't use <bits/stdc++.h>, it's unportable and inefficient. See "Why should I not #include <bits/stdc++.h>?" for the details.

  2. Don't use using namespace std;, that namespace just isn't designed for it. See "Why is “using namespace std” considered bad practice?" for more background.

  3. Invest in some better names. Being too parsimonious there hurts, even though brevity is a virtue.

  4. Format your code consistentently.

    • Sometimes you have space around binary operators (other than comma, which only should be followed by a space), sometimes you forget.
    • Add a space after ; when it isn't followed by the next line, meaning a loop's head.
    • Also add a space after #include, for, if, and while.
    • You don't have to use a block for single statements, but please don't put them on the same line, at the least separate them with a space.
  5. C++ does not have VLAs. Just use a std::vector instead.

  6. While in general, keeping the scope of a variable minimal is a good idea, there are exceptions. One of them is efficiency. Always spinning up a new std::string means being unable to re-use the buffer. Not that you really need the whole string at once, anyway.

  7. One reason you should minimise a variables scope, is that it allows you to initialise it to the proper value, instead of leaving it uninitialised or, horrors of horrors, adding a spurious dummy-initialisation.
    That also allows you to avoid writing the type (Almost Always auto), and making it const or even constexpr.

  8. There are compound-assignment-operators for most binary operators. Like a |= b for a = a | b. Using them leads to shorter, more readable code.

  9. When you want to output a single character, why not use a character-literal? It's potentially even slightly more efficient.

  10. return 0; is implicit for main(). Take it or leave it, but be aware.

The Algorithm:

Your algorithm uses \$O(\#characters+\#words^2)\$ time and \$O(max\_word\_length + \#words)\$ space.

An optimal algorithm only needs \$O(\#characters+2^{\#vowels})\$ time and \$O(2^{\#vowels})\$ space:

  1. For every word:
    1. Set the bits for all the vowels contained.
    2. Increment the count on the indicated bin.
  2. For every vowel:
    1. Iterate the bins containing words with that vowel.
    2. Add the count to the respective bin without that vowel.
  3. For all bins: Multiply the count in the bin with the count in the complementary bin, and add that.
  4. Subtract twice the count in the bin for words containing all vowels. Those account for all self-pairings.
  5. The answer is half the calculated number, as we counted double.

Exercise for the attentive reader: Save half the multiplications this algorithm uses.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ The optimal algorithm is only optimal for a very small number of vowels. As soon as you combine multiple alphabets (Latin, Cyrillic, Hangul, Latin with accented letters), \$2^v\$ quickly becomes quite large and inefficient. \$\endgroup\$ – Roland Illig Mar 10 '19 at 8:38
  • \$\begingroup\$ @RolandIllig Sure, unicode has a ginormous repertoire. \$\endgroup\$ – Deduplicator Mar 10 '19 at 10:44
4
\$\begingroup\$

I'm no C++ guru, but some things jump out at me:

  1. Your coding style is very dense, which makes it hard to read and review. I'd suggest that you switch to a style that doesn't make you pay for each time you add a space. Code like this:

    cin>>t;
    while(t--)
    

    Just isn't as easy to read as code like this:

    cin >> t;
    while (t--)
    

    The little things make a difference! And even if you're in some kind of "shortest code" context, I think you should still write it long, and then compress it once you have it working.

  2. The first for loop in your while loop is concerned with reading and parsing the input strings. I believe you should break that into a separate function. What's more, I think you should make a slight change to your data storage as @Deduplicator suggested: instead of just using the bits located at (1 << (vowel - 'a')), at some point you should compress the bits down into the range 1<<0 .. 1<<4.

  3. I believe that the description says "(unordered) pairs" and means that if two strings, A and B, can be concatenated to meet the requirements, they only count once, as in set{A, B} and not twice, as in pair(A,B), pair(B,A). So, as @Deduplicator suggested, if you "bin" your words - that is, categorize them according to the trait "which vowels are present", then you can represent a bin with just an integer (how many words are in the bin). So you would then cross-match every bin with every other bin to determine whether the binned words can successfully pair, and add an appropriate number to the count.

With that in mind, a successful solution would look something like this:

for each input word:
    scan the word for vowels, recording which vowels were found
    classify the found vowels into a small integer with bits 0..4 set
    use the small integer as the "bin" number for that word
    increment the count for that bin#

This should be \$O(n \cdot s)\$ on the number of words, n, and the length of the words, s, in time. The only optimization would be to break out of the scanning loop if you match every single vowel, since further scanning gains you nothing. The code will require storage for the input, but compiles everything down to a single bin number, so the storage will be from \$O(1)\$ to \$O(s)\$ depending on how you implement the code. The bin numbers are members of a fixed set, so their counts will be \$O(2^5)\$ regardless, which simplifies to \$O(1)\$.

Now since matched pairs of words only count one time, you can loop "upwards" when generating combinations:

for each bin 0 .. 2^5 - 1
    for each higher bin (looping upwards here):
        if the two bins match
            the count of word pairs is # in bin-1 * # in bin-2
            add the count to the total count of matchable pairs

This should be \$O(n^2)\$ on the number of bins (not words!), which is a constant. You can't optimize much, except that bins with counts of zero won't contribute anything so can be skipped.

At this point you have your answer and just need to print it out.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.