lnzva's blog

By lnzva, history, 7 years ago, In English

Could anyone suggest some problems which utilize Dilworth's theorem? Thanks in advance :)

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +7 Vote: I do not like it

MDOLLS on SPOJ uses Dilworth's theorem.

»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

The classical O(N lg N) algorithm for longest increasing subsequence (LIS) can be seen as an application of Dilworth's Theorem. See here: http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/

»
7 years ago, # |
  Vote: I like it +6 Vote: I do not like it
»
7 years ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

Another good problem (Dilworth's on longest increasing subsequence) is Cow Jog from USACO December 2014.