SPOJ Emoticon challenge

Question

I tried this spoj problem and solved it using Dynamic Programming, but I was getting Time Limit Exceeded. The challenge is to count the number of occurrences of the subsequence "KEK" in each input string.

Some people in comments stated that they have done in O(n) time. I am getting no idea. can someone give me an idea? Here is my dynamic programming approach.

#include<bits/stdc++.h>
using namespace std;
int dp(string s,int in,int len,int pos){
    if(in == len){
        return 0;
    }
    if(pos == 0){
        if(s[in] == 'K'){
            return dp(s,in+1,len,1)+dp(s,in+1,len,0);
        }
        return dp(s,in+1,len,0);
    }
    if(pos == 1){
        if(s[in] == 'E'){
            return dp(s,in+1,len,2)+dp(s,in+1,len,1);
        }
        return dp(s,in+1,len,1);
    }
    if(pos == 2){
        if(s[in] == 'K'){
            return 1+dp(s,in+1,len,2);
        }
        return dp(s,in+1,len,2);
    }
}
int main(){
    int t;
    cin>>t;
    while(t--){
        string s;
        cin>>s;
        int l = s.size();
        int k = dp(s,0,l,0);
        cout<<k<<endl;
    }
    return 0;
}

Answer 1

You are re-copying the string parameter with every recursive call. That will eat up your time.

It appears that you are programming a state machine with three states.

The function has three branches for states 0,1,2 but have no common code (other than precondition checking) and you know the number when you make the call. So, make three separate functions.

The string knows its own size. You don’t need to pass that separately. The std::string_view is good at nibbling away from the ends, so use that and you don’t need to pass the in.

I suggest adding a static counter so you can see just how many recursive calls are being made!

Don’t write using namespace std;.

You can, however, in a CPP file (not H file) or inside a function put individual using std::string; etc. (See SF.7.)

---

Idea on how to do it in 𝒪(n)

int f (const std::string& s)
{
    std::vector<int> b;
    int n {0};
    for (auto c : s) {
       if (c=='E')  b.push_back(n);
       else if (c=='K')  ++n;
    }
    int sum {0};
    for (auto i : b)
        sum += i*(n-i);
    return sum;
}

The string is only gone through once. That is the key to making it 𝒪(n). Instead of recursion I push a value on a stack and keep going with the first half of the next go. After reaching the end of the string, pop each value and complete the calculation. (I did FIFO not LIFO but it doesn’t matter) You can see to convert this to recursion the call will go where the push_back is here, passing the rest of the string and n thus far. The suspended stack frame remembers the current n at that point. When the end of the string is reached and everything starts returning, it returns the total thus far and the final value of n; it adds its own term and returns to the prior.

To make it faster, use static buffer sizes (since you are told the maximum size of everything) and use a faster reading function too.

Answer 2

int dp(string s,int in,int len,int pos){

Where are the comments to explain the meanings of the variables? We're forced to reverse engineer them.

    if(in == len){
        return 0;
    }
    if(pos == 0){
        if(s[in] == 'K'){
            return dp(s,in+1,len,1)+dp(s,in+1,len,0);
        }
        return dp(s,in+1,len,0);
    }
    if(pos == 1){
        if(s[in] == 'E'){
            return dp(s,in+1,len,2)+dp(s,in+1,len,1);
        }
        return dp(s,in+1,len,1);
    }
    if(pos == 2){
        if(s[in] == 'K'){
            return 1+dp(s,in+1,len,2);
        }
        return dp(s,in+1,len,2);
    }
}

This is not dynamic programming. A dynamic programming approach to this problem must work on the following basis:

Given a structure S which summarises the prefix str, and the next character ch, we need to derive a structure S' which summarises the prefix str + ch.

We have some easy conclusions:

• S must provide us with the number of the desired subsequences, because at the end of the DP run we will only have S corresponding to the entire string. So it has a field which we can call kek.
• If ch is neither 'E' nor 'K' then S' = S.
• If ch != 'K' then S'.kek = S.kek.
• If ch == 'K', S must provide us with some way of knowing how much bigger S'.kek should be than S.kek. Obviously that must be the number of KEK subsequences ending with ch, which is the number of KE subsequences in str.

You should be able to carry this reasoning through to fill out the entire list of fields required in S and the logic to update them when reading an 'E' and when reading a 'K'.

Answer 3

You might be overthinking. The simple solution is:

int sum = 0;
for(int i=0;i<length;i++) {
    if (input[i] == 'E') {
        sum += numberOfKBefore[i] * numberOfKAfter[i];
    }
}

and the dynamic programing part is only to fill up the numberOfKSoFar array with counts of 'K'.