lnzva's blog

Problems which utilize Dilworth's theorem
By lnzva, history, 6 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

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

MDOLLS on SPOJ uses Dilworth's theorem.

→ Reply
»
6 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/

→ Reply
»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

A problem from the third round of 2015 Facebook Hacker Cup

https://www.facebook.com/hackercup/problem/847639175277938/

Solution: https://www.facebook.com/notes/1056536891028878

→ Reply
»
6 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.

→ Reply