yamin_7991's blog

By yamin_7991, history, 3 weeks 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  

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

MDOLLS on SPOJ uses Dilworth's theorem.

»
3 weeks 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/

»
2 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it
»
2 weeks 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.