How to solve BAT2-SPOJ?
My idea is that you need to find all increasing subsequences from left (1->n), and all increasing subsequences from right (n->1). Since n can be <=100, this will take 2^100 time, which is too slow. How can it be done efficiently? Or am I thinking in the wrong direction?
I think so. You must find length of max increasing subsequence in array B. Array B = A + A, where A is array that we were given. It can be done in O(nlog(n))
5
5 4 2 3 1
The correct answer is 5 (5->4->1, 2->3).
Clearly you don't have enough time to enumerate all those sequences, so that direction won't lead very far. Note that instead of thinking that Catwoman moves from right to left in an increasing sequence, the problem doesn't change if she moves from left to right in a decreasing sequence.
Why is this helpful? Because now Batman and Catwoman are moving in the same direction, which should let you use a really well-known technique to construct both of their paths at the same time.
what is this algorithm ?
DP
I thought of finding the length of longest increasing subsequence and the length of longest decreasing subsequence but what if they have a common term ?
Could you please give more hints?
we can see that its finding disjoint increasing subsequence and longest decreasing subsequence used simple DP
dp[pos][x][y] = the longest increasing subsequence and decreasing subsequence, using elements 1..pos, and the last index of longest increasing is x, while the last index of longest decreasing is y
then dp[pos][x][y] is the max of the following:
I just ACed the problem using your logic,thanks a lot... But I submitted a recursive DP solution, Can someone provide me a bottom-up table method DP of this problem,thanks a lot!!
Can you please share your code, with some comments. And I am not getting what will be the base case in recursion.
Sure , CODE
Pardon me , the comments can be a little hard to read because of the indentation , but its still readable and I did my best explaining the DP in the code , If you dont get it , ask!
Found the error, fixed