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...

  • TIMUS - 1036 Lucky Tickets
    Link to the problem on Timus Online Judge First of all there are two kinds of input which the answer is zero, first if sum % 2 == 1 or se...
  • TIMUS - 1120 Sum of sequential numbers
    Link to the problem on Timus Online Judge The problem statement is completely straight forward with no hidden tricks :). Yeah yeah I know...
  • TIMUS - 1207 Median on the plane
    Link to the problem on Timus Online Judge  This is a Computational Geometry problem. No 3 points lie on the same line and this is a great...