Hi!

I made a DP state similar to LCS where dp[i][j] indicates the length of the best subsequence possible using A[0..j] and B[0..j]. Then for each state I select an element from A[0..j-1] and try to find its complement in B using a map. See the code for more detail.

My solution: http://paste.fedoraproject.org/501744/12056421/

However this fails on all test cases except two giving me a depressing 20/100.

What is wrong with my DP? What other approaches are possible? This approach (if you assume all elements in B are distinct) becomes O(N^3 log N). If we don't assume all elements are distinct, we get ~= the same time (I guess?). I did not get any TLEs on the judge, and the worst time was 0.103s so that's a good sign.

Please help I've been stuck for an hour.