__abs's blog

Related to CSES — Collecting Numbers
By __abs, history, 23 months ago, In English

Problem statement here. I understood the solution for this.

How to compute the minimum number of rounds required? (this is not asked in that question)

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Basically what you are asking is the minimum number of chains required to cover the whole array (a chain is an increasing sequence of numbers), which, by dilworth's theorem is equal to the length of the longest decreasing subsequence of the array. Finding the LDS, is just the opposite of finding the LIS (a standard DP problem).

→ Reply