lax_99's blog

By lax_99, history, 9 months ago, In English,

Hello Codeforces community!

Problem Link : Link

I have a memoized solution for this problem. The issue here is that my complexity is : O(N^3), which leads me to TLE. All the editorials and blogs I have seen have used Bottom up approach and suffix sum to get it to O(N^2). But I'm not sure how to translate this idea to the memoized version.

int dpSol(int i, int level)
{
    if(i == n - 1)
        return 1;
    
    if(cache[i][level] != -1)
        return cache[i][level];
    
    if(arr[i] == 's')
    {
        int sum = 0;
        for(int j = 0; j <= level; ++j)
            sum = (sum + dpSol(i + 1, j)) % MOD;
        return cache[i][level] = sum;
    }
    return cache[i][level] = dpSol(i + 1, level + 1);
}

Any help will be appreciated! Thanks in advance.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you link the problem?

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You can't do it easily with recursion. Some people did it but it was quite hard to explain compared with the bottom up solution. If you still want the recursion solution see: 33679063

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I have the Same problem... https://codeforces.com/contest/909/submission/55870468 I didn't get how to apply prefix sum.