=================================

Hello Codeforces, my name is C137 and as I said before, I will continue writing regularly in this blog:

The idea is, every 7-10 days i am gonna select a problem that i really found it useful and interesting, and then i will talk about the way i solved this problem, with long editorial and analysis, by this way of sharing my thoughts i hope that grey, green and cyan contestants will benefit from it and learn something new, also i am hoping that top rated contestants will also add their notes to my solution, and suggest some more optimized code.

=================================

Today, I choose to you this dp problem, I really liked this problem because in the round I solved it in the last 23 minutes, and this helped me becoming blue for the first time, I hope you will like it:

P.S: if you are familiar with the basics of dynamic programing, then i strongly recommend you to try with this problem at least for one hour before reading this blog, otherwise as a start you should check this as it contains a description to the Longest common sub-sequence (LCS) problem .

Before I start, I would like to thank NourAlhadi for solving this problem after reading this blog, and adding his notes and suggestions to make it even more clear.

problem name: Alyona and Strings

Link: this

type: dp

Difficulty level: Medium

Short Description:

You are given two strings, and number K, you should find the length of the longest sub-string consisting of at most K groups of continuous characters.

Example:

Let the two strings be:

aabbcc

aadccc

and k = 2

the answer would be 4, and the sub-string is: aacc

Problem Analysis:

When you read such problem, the first thing that clicks to your mind is dp, there is a famous dp problem so familiar to this one, it's the Longest Common sub-sequence(LCS) so i knew i should start from LCS code, and I wrote the following code on a piece of paper:

int lcs(int i, int j){
	if(i==s1.length() || j==s2.length())return 0;
	int &ret=dp[i][j];
	if(ret!=-1)return ret;
	if(s1[i]==s2[j])return ret= 1+lcs(i+1,j+1);
	return ret=max(lcs(i+1,j) , lcs(i,j+1) );
}

Now, any dp problem could be solved easily if you can determinate three main things:

First, how to represent your state, like the LCS my state should be represented using my position in the first string, and my position in the second one, in addition this problem requires another parameter, its the number of remaining groups, so the state is:

[pos_first_string][pos_second_string][rem_groups]

Second, the end case of the cal function, also like the LCS my cal function should return 0 when i reach the end of one of the two strings, in addition, when i have no remaining groups, i should return 0, because i can't take any more characters, so:

if(i==s1.length() || j==s2.length() || rem_groups==0)return 0;

Now after i represented my state, decided when the cal function should stop, there is only one more thing to consider, how to move from state_a to state_b ??? I mean how to move from a state to another.

Now there are two cases to consider, if there is a common continues characters to take, or if there isn't. If there isn't any common continues characters, which means:

if(s1[i]!=s2[j]) return ret=max(cal(i+1 , j, rem_groups), cal(i, j+1 , rem_groups) );

either i move in the first string, or in the second one, and the number of remaining groups doesn't change.

Now, if there is a common group of length len then I should take it, and increase the answer by len, so i wrote:

if(s1[i]!=s2[j]) return ret=max(cal(i+1 , j,  rem_groups),cal(i, j+1 , rem_groups) );
else ret=len+cal(i+len, j+len, rem_groups-1);
return ret;

when i first saw this problem, there was only 23 minutes remaining in the round, so i was in a big hurry, and have no time to debug my code, I submitted it like this and got wrong answer on the pretests.

with short time remaining, i checked my code on some samples, and it gave me a wrong answer on the following sample:

1
axsss
acsss

my code was printing 1, but the answer is 3, taking sub-string "sss"

what was happening, is sometimes i shouldn't take the group, because perhaps there is longer group after it, so I wrote:

ret=max(cal(i+1 , j,rem_groups),cal(i      , j+1 , rem_groups) );
if(s1[i]!=s2[j])return ret;
else ret=max(ret,len+cal(i+len,j+len,rem_groups-1) );
return ret;

with five minuted remaining, i submitted my code, to get TLE on pretests, i was surprised, as my complexity is:

lenoffirststring * lenofsecondstring * k = 1000 * 100 * 10 = 1⁷

something small, and easily passes the pretests, however after a quick look at the code, i found that i forget in the cal function to write:

if(ret!=-1)return ret;

with three minutes remaining, i fixed the code, and got pretests passed, and finally got it accepted, after very interesting and nervous 19 minutes.

there are some things that i would like to talk about, while solving a dp problem, always check if you passed this state before, so you won't cal the same states multiple times, never forget to initialize your dp array with  - 1, and don't forget the return at the cal function, these are three common bugs at dp codes, that makes you sometimes hate your day.

=================================

This is all I can say for this problem, I hope you liked my analysis and you benefit from it, I am not gonna post my code, because I think you can code it now after reading the analysis, If there is still something unclear, then fell free to ask me in the comments below, or send me a message...

I will try to post the next blog about the next problem in the following week... Happy coding, and have a nice day :D

=================================