CODECRAFT 2015 REPLAY>>LOLOL PROBLEM

general
,
1

PLEASE TELL ME WHATS WRONG IN MY CODE…
code link:http://www.codechef.com/viewsolution/6075501
2

indent your code

3

atleast tell your logic, asking others to go through your code is not good!

4

Check your output for this string:

LOLOLOLO

It gives 9 as the answer while the answer is 10. However, I couldn’t understand much of the logic behind your code but think it’ll probably give TLE. I’d like t explain here approaches I used:

Basic brute force: Lets say I take an array dp[] where dp[i] denotes the number of subsequences of string LOL string s(lets say), range [1,i-1]( a smaller subproblem it is). Then, extend this string s by one more character. If this new character is ‘O’, then dp[i]= dp[i-1], since no new subsequences will be formed on adding ‘O’ to this existing string. If the new character added is ‘L’, then what we need to do? We need counts of all previous subsequences of ‘LO’ string in the range [1,i-1]. You get this point?(Comment if not, I’ll explain more if you want). Thus, we need the position of every ‘O’ in range [1,i-1], lets say one of such position is p and we now need the number of ‘L’ in range [1,p-1].

preprocess the string and store the number of L in range [1,i-1]
lastcount[n+1]={0}
if(str[0]=='L'):
 lastcount[0]=1;

for(i=1;i<n;i++):
  lastcount[i]=lastcount[i-1];
  if(str[i]=='L')
   lastcount[i]+=1;

for(i=1;i<n;i++)
{
  dp[i]= dp[i-1];
  if(str[i]=='L')  // extending the string by 'O' doesnt have any effect
  {
    int cnt=0;
    for(j=i-1;j>=0;j--)
    {
      if(str[j]=='O')
      cnt+= lastcount[j];
    }
  }
  dp[i]+=count;
}

ans=dp[n-1];

This is bound to give TLE. So, it can be optimized very easily. See this, a very easy implementation. So, think of DP style. Lets say we have an array dp[n+1][3] where dp[i][j] dentes the number of subsequences of string 2("LOL) in string str(input), range [1,i-1].

Then, for every i’th and j’th we have two possibilities. Either str2[j]==str[i] or the two are not equal.
So, we have:

for(i=0;i<=3;i++)
 dp[0][i]=0;

for(i=0;i<=n;i++)
 dp[i][0]=1;


for(i=1;i<=n;i++)
{
	for(j=1;j<=3;j++)
	{
		if(str[i-1]==str2[j-1])
		{
                    //extend the subsequence which matches the last (j-1)'th character in range [1,i-1]
                    
			dp[i][j]= dp[i-1][j-1];
		}
                    // this adds all the subsequences in the range [1,i-1] to keep the count in the end.
		dp[i][j]+= dp[i-1][j];
	}
}

Hope it clears, any doubts, you may ask in comments… :slight_smile: