Sunday, August 30, 2009

497 - Strategic Defense Initiative - UVA

dynamic programming - Longest Increasing Subsequence ( LIS ) - O( n^2 )...O( nLOG(n) )

This problem is a classic dynamic programming problem that if you are familiar with the type of the problem, you will solve it in less than 10 minutes.

I use O( nLOG(n) ) implementation of LIS, you can find an implementation of it at
http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence
at
Labels:

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)

USACO - Prime Palindromes

I just skimmed the problem statement and panicked of the high boundary of the input, but something inside told me don't worry everyth...

  • USACO - Prime Cryptarithm
    Prime Cryptarithm The following cryptarithm is a multiplication problem that can be solved by substituting digits from a specified set ...
  • USACO - Arithmetic Progressions
    Let's think about it, Have you noticed the small boundary of N & M, What can we do with this small boundary? Isn't producing al...
  • AvoidRoads - 2003 TCO Semifinals 4 - TopCoder
    Dynamic Programming The problem wants to know in how many ways one can reach destination ( cell[width][height] ) If there were no obstacle...