Блог пользователя lnzva

Автор lnzva, история, 7 лет назад, По-английски

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

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

MDOLLS on SPOJ uses Dilworth's theorem.

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

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