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
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.
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];
while (std::cin >> input_string)
int input_length = input_string.length();
double* midseries = new double[input_length + 1];
midseries = 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;
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;