The bottom-Up approach is almost correct!

#1

Hi!, In this question, I also tried the bottom up approach and submitted it on hacker-earth, but 3 test cases go wrong where everytime my ans is just one less than the actual answer. Please help me figure out my mistake. The link to my code is : https://ide.codingblocks.com/s/161343

#2

All you have to do is just find the lcs and then add k to the answer.

#3

I doubt your formula for example:
5 5 3
1 2 3 5 4
1 2 3 4 5
the lcs is 4 - (1235 or 1234).
You are saying ans should be 4 + 3 = 7, which is greater than 5. So if I need to bound it, I can say if lcs+k>min(n,m) then ans is min(n,m) - where n and m are sizes of first n sec array.

But for example:
8 7 3
1 2 3 5 6 7 4 8
1 5 6 3 2 4 7
The lcs is 1567 that is 4 and your ans is 4 + 3 = 7.
But I guess 3-ordered LCS will be 6 in this case.

#4

You are right, actually, I didn’t encounter some counterexample when adding k to LCS will not result in Longest LCS. Actually, I solved it just by adding k to LCS and got AC, that’s why I said that.
Its answer is 6.
Use the gap method.
I have implemented the bottom-up using the gap method.
You can refer to this for better understanding.

#5

Hi!!
I think my code is same as what you have written, just the style is different, can I know any faults in my code, because our comparisons are same, and also is the name “GAP method” any specific technique to solve dp problems?

Thanks for the code!

#6

Not a specific category just a fancy name.

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.