Part of list:

[EXPT] Indraneel's Experiment

[EXPT] Indraneel's Experiment

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.

Read more…(137 words)

Mark as completed

Part of lists:

Previous

[AVERAGE] Average

Next

[PYRAMID] Indraneel's Pyramid

About the author:

Sai Vineet

Loading…

Have a question? Ask here…

Post

Part of list:

[EXPT] Indraneel's Experiment

About the author

Sai Vineet

Ready to join our community?

Sign up below to automatically get notified of new lists, get **reminders** to finish ones you subscribe to, and **bookmark** articles to read later.

Continue with Facebook

— OR —

Your Full Name

Email address

I have an account. Log in instead

By signing up, you agree to our Terms and our Privacy Policy.