Editorial for Valentine's Day '19 J3 - Love!


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Rimuru

For 30\% of the points, we can, very easily, brute force the problem with 4 nested for loops, the first loop representing a position of l, the second defining a position of o, the third loop as the position of v, and the last loop representing the position of a letter e. From there, we can iterate over all position that have l, o, v, e, and keep track with a counter.

In the worst case where \left | S \right | \le 100 (3rd batch), we will have 25 l's, 25 o's, 25 v's, and 25 e's, where \mathcal O(25 \times 25 \times 25 \times 25) = \mathcal O(25^4) = \mathcal O(390\,625).

The implementation for the first 30\% of the points should look somewhat like this:

for(int i=0; i<(int)s.size(); i++) {
    for(int j=i+1; j<(int)s.size(); j++) {
        for(int k=j+1; k<(int)s.size(); k++) {
            for(int p=k+1; p<(int)s.size(); p++) {
                string check = "";
                check += s[i];
                check += s[j];
                check += s[k];
                check += s[p];
                if(check=="love") cnt++;
            }
        }
    }
}

Time complexity: \mathcal{O}(N^4)


From here, there are actually 2 ways to score 100\% of the points on this problem, but as one way (without the author's knowledge) was published here, we will go over the intended solution.

We can count the number of e's that are positioned in front of each v, the number of v's that are positioned in front of each o, and the number of o's that are positioned in front of each l, and track a total of this.

In total, this will take \mathcal O(4) memory and a time complexity of \mathcal O(N), implying we loop backwards.

Implementation is as follows:

for(int i=(int)s.size()-1; i>=0; i--) {
    if(s[i]=='e') ecnt++;
    else if(s[i]=='v') vcnt += ecnt;
    else if(s[i]=='o') ocnt += vcnt;
    else if(s[i]=='l') lcnt += ocnt;
}

One other thing to watch out for is the last case, where there are 2500 l's, 2500 o's, etc., where N = 10\,000. This is because the solution would be 2500^4, which is far too large for the int data type. (Sorry about it everyone, it was funny to see people WA on it…)

Time complexity: \mathcal O(N)


Comments

There are no comments at the moment.