3
\$\begingroup\$

I'm looking for an algorithm to make my code faster and better for big strings.

Problem link

Let the simple prettiness of a string be the count of vowels (I, E, A, O, U, Y) divided by the length of the string. Find the sum of the simple prettiness of all substrings of a given string (with precision within 1 part per million), where the input string may be up to 5∙105.

Let's say I have the following input:

IEAIAIO

The output should be like this:

28.000000

Second ex:

BYOB
5.833333

Third ex:

YISVOWEL
17.050000

My solution gives me Time Limited Exceeded on big strings.

#include <bits/stdc++.h>
using namespace std;
int main()
{

    string s;
    while (cin>>s)
    {

        long double sum=0.0;

        for (int i = 0; i < s.length(); i++)
        {
            for (int j = i+1; j <= s.length(); j++)
            {
                string ss=s.substr(i,j-i);
                //<<ss<<endl;
                long double len=0.0;
                for (int r = 0; r < ss.length(); r++)
                {
                    if(ss[r]=='I' || ss[r]=='E' || ss[r]=='A' || ss[r]=='O' || ss[r]=='U' || ss[r]=='Y' )
                        len++;
                }
                //cout<<"len = "<<len<<"\tss= "<<ss<<endl;
                long double len_ss=ss.length();
                sum+=(len/len_ss);
            }
        }
        cout<<fixed;
        cout << std::setprecision(6) << sum<<endl;

    }
return 0;

}
\$\endgroup\$
  • \$\begingroup\$ How "big" is the string when you get a runtime error? \$\endgroup\$ – David K Jan 31 '15 at 14:46
  • \$\begingroup\$ @DavidK ideone.com/zXGSHS check this out \$\endgroup\$ – CPlusProgrammer Jan 31 '15 at 14:49
1
\$\begingroup\$

Style

You probably don't care much about this but your style (spacing for instance) is not very consistent.

Making things easier to improve

You'll make your code much easier to improve if :

  • you have a way to measure performances
  • you have a way to ensure you don't screw it up.

You can do so by writing a few tests.

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

long double prettyness(const string & s)
{
    long double sum = 0.0;
    long double len_s = s.length();
    for (int i = 0; i < len_s; i++)
    {
        for (int j = i+1; j <= len_s; j++)
        {
            string ss = s.substr(i,j-i);
            long double len = 0.0;
            long double len_ss = ss.length();
            for (int r = 0; r < len_ss; r++)
            {
                if(ss[r]=='I' || ss[r]=='E' || ss[r]=='A' || ss[r]=='O' || ss[r]=='U' || ss[r]=='Y' )
                    len++;
            }
            sum += len/len_ss;
        }
    }
    return sum;
}

void stdio_tests()
{
    string s;
    while (cin>>s)
    {
        cout << fixed << std::setprecision(6) << prettyness(s) << endl;
    }
}

void unit_tests()
{
    long double res;
    res = prettyness("IEAIAIO");
    assert(res == 28);
    res = prettyness("BYOB");
    assert(5.83333 < res && res < 5.83334);
    res = prettyness("YISVOWEL");
    assert(17.04 < res && res < 17.06);
    res = prettyness("QWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNMQWERTYUIOPASDFGHJKLZXCVBNM");
    assert(79984 < res && res < 79985);
}

int main()
{
    unit_tests();
    return 0;
}

Improvements

I already got rid of the multiples calls to length() above. Let's try to make other improvements.

For a start, you don't need to use substr at all. You can simply try to be smart with string indices :

long double prettyness(const string & s)
{
    long double sum = 0.0;
    long double len_s = s.length();
    for (int i = 0; i < len_s; i++)
    {
        for (int j = i+1; j <= len_s; j++)
        {
            long double len = 0.0;
            for (int r = i; r < j; r++)
            {
                if(s[r]=='I' || s[r]=='E' || s[r]=='A' || s[r]=='O' || s[r]=='U' || s[r]=='Y' )
                    len++;
            }
            sum += len/(j-i);
        }
    }
    return sum;
}

Then, you can get rid of the multiple checks of the char value by storing the result in an array.

Also, you could make things much faster by storing cumulative sums of vowels so that you can get number of vowels in substring i..j by computing something like cum[j]-cum[i].

The code would be something like :

long double prettyness(const string & s)
{
    long double sum = 0.0;
    size_t len_s = s.length();
    long double cum[len_s + 1];
    cum[0] = 0;
    for (int i = 0; i < len_s; i++)
        cum[i + 1] = cum[i] + (s[i]=='I' || s[i]=='E' || s[i]=='A' || s[i]=='O' || s[i]=='U' || s[i]=='Y');
    for (int i = 0; i < len_s; i++)
        for (int j = i+1; j <= len_s; j++)
            sum += (cum[j]-cum[i])/(j-i);
    return sum;
}

This is much faster but I'm pretty sure there is a way to do better. For instance, substrings of same lengths could be considered together to perform a smaller number of divisions.

long double prettyness(const string & s)
{
    size_t len_s = s.length();
    double cum[len_s + 1];
    cum[0] = 0;
    for (int i = 0; i < len_s; i++)
        cum[i + 1] = cum[i] + (s[i]=='I' || s[i]=='E' || s[i]=='A' || s[i]=='O' || s[i]=='U' || s[i]=='Y');
    long double sum = 0.0;
    for (int l = 1; l <= len_s; l++)
    {
        long double tmp_sum = 0.0;
        for (int end = l; end <= len_s; end++)
        {
            tmp_sum += cum[end] - cum[end-l];
        }
        sum += tmp_sum/l;
    }
    return sum;
}

Then, some trick to compute the inside of the loop faster. Indeed, many indices cancel each other. At the end, you are down to some value that can be precomputed with another cumulative array :

long double prettyness(const string & s)
{
    size_t len_s = s.length();
    double cum[len_s + 1];
    cum[0] = 0;
    for (int i = 0; i < len_s; i++)
        cum[i + 1] = cum[i] + (s[i]=='I' || s[i]=='E' || s[i]=='A' || s[i]=='O' || s[i]=='U' || s[i]=='Y');

    double cum_cum[len_s + 2];
    cum_cum[0] = 0;
    for (int i = 0; i <= len_s; i++)
        cum_cum[i + 1] = cum_cum[i] + cum[i];

    long double sum = 0.0;
    for (int l = 1; l <= len_s; l++)
        sum += (cum_cum[len_s + 1] - cum_cum[l] - cum_cum[len_s - l + 1])/l;
    return sum;
}

You have a O(n) algorithm, that should be fast enough (and it is easy to see that better complexity cannot be achieved).

\$\endgroup\$
1
\$\begingroup\$

The contest has closed, so presumably nobody really needs a program to do this particular task any more. But that also means I can give some advice about how to make programs like this more efficient without concern about interfering with the contest, and perhaps the advice will be helpful when facing other problems.

Even without any new algorithm, the code in the question can be made to run a lot faster. Consider this line:

if(ss[r]=='I' || ss[r]=='E' || ss[r]=='A' || ss[r]=='O' || ss[r]=='U' || ss[r]=='Y')

It should be rather obvious that this line gets executed a lot, since it's in the innermost loop of three nested loops. Each character ss[r] is just a character from the original string, s[i+r], and each of these characters is compared to 'I', 'E', etc. many times. You can save a lot of execution time by "memoizing" these values; for example, make a boolean array is_vowel of size s.length() and set is_vowel[i] to true if s[i] is one of the six letters that count as vowels here. Then for each r in the inner loop, instead of testing six possible equalities you just need if (is_vowel[i+r]). With this one optimization, I was able to cut the running time of this program by about a factor of 3 regardless of the length of input.

A less obvious fact is that len++ takes longer to compute when len is of type long double than when len is an integer type. By declaring int len = 0; and only converting it to floating-point when it was time to divide it by the substring length, I reduced the running time by about 1/3 again, so it was between 1/5 and 1/4 of the original running time.

Optimizations like this should not be ignored, especially when they are so easy to do. But of course for this particular program, the real problem is that the running time for an input string of length n is asymptotically proportional to n^3. We can really speed it up dramatically if we can find an algorithm whose running time is asymptotically proportional to n^2 instead.

There are a couple of different ways to go about this. One way is to make the index of the outer loop be the length of the substrings that will be examined; that is, during the iteration when i is 3 you will consider all the substrings of length 3. Consider that each time a vowel appears as a character in one of those substrings, it adds 1/i to the final answer. Then consider how many times each character occurs in a substring of length i. The answer is 1 if i is the length of the input string, but for shorter substrings, characters other than the first or last can occur multiple times. You can figure out how many times that is by a simple formula without iteration. For each substring length, add up the number of appearances in substrings of that length for each vowel in the input string, then divide by the substring length and add it to the running total. I found it helpful to consider substrings up to half the input length in one loop and the rest in another loop, since the formula for number of appearances has to account for whether the first and last substring of that length would overlap.

An alternative approach is to compute how much a vowel in position i will add to the final answer. That is, what is the number of times it appears in substrings of length 1, plus 1/2 the number of appearances in substrings of length 2, and so forth (generally 1/k of the number of appearances in substrings of length k). There are a few different ways to compute the weights, some of which involve first making a list of sums of the form 1, 1+1/2, 1+1/2+1/3, etc. Either fill an array of the same length as the input string with "weights" of the characters at the corresponding positions in the input string, or write a function to compute the weight of the character at each position; then iterate through the input string, and each time you find a vowel add the weight at that position to the sum.

Either of these modified algorithms can easily be made to run in O(n^2) time.

The program below is a hybrid of precomputed arrays and on-demand calculation of the "weight" of a vowel. I believe this has O(n) running time. It is certainly the fastest program I've yet written for this problem, according to IdeOne, which clocked 0 running time for the given input of length 5925; hard to improve on that without longer input.

#include <iomanip>
#include <iostream>
#include <string>

double weight_at_position(int n, int length, double* midseries, double* tail)
{
  double weight = 0.0;
  int    p = (n < length / 2) ? n + 1 : length - n;
  // The first p - 1 terms are just 1/1, 2/2, 3/3, etc.
  weight = p - 1;
  // Add the terms whose numerator is p.
  weight += p * (midseries[length - p + 1] - midseries[p - 1]);
  // Add the last p - 1 terms
  weight += tail[p - 1];
  return weight;
}

int main()
{
  std::string input_string;
  while (std::cin >> input_string)
  {
    int  input_length = input_string.length();

    double* midseries = new double[input_length + 1];
    midseries[0] = 0;
    for (int i = 1; i <= input_length; ++i)
    {
      // midseries[i] = 1 + 1/2 + 1/3 + ... + 1/i
      midseries[i] = midseries[i - 1] + 1.0/static_cast<double>(i);
    }
    double* tail = new double[input_length/2 + 2];
    tail[0] = 0;
    for (int i = 1; i <= input_length/2 + 1; ++i)
    {
      // tail[i] = 1/N + 2/(N-1) + 3/(N-2) + ... + i/(N-i+1)
      tail[i] = tail[i - 1] + i/static_cast<double>(input_length - i + 1);
    }

    double sum = 0.0;
    for (int i = 0; i < input_length; ++i)
    {
      char c = input_string[i];
      if  (c=='I' || c=='E' || c=='A' || c=='O' || c=='U' || c=='Y')
      {
        sum += weight_at_position(i, input_length, midseries, tail);
      }
    }
    std::cout << std::fixed;
    std::cout << "Input length = " << input_length << std::endl;
    std::cout << std::setprecision(6) << sum << std::endl;
  }
}
\$\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.