nhtrnm's blog

[Problem] Number of LIS
By nhtrnm, history, 8 years ago, In English

The other day in COCI Round #3 I didn't solve the problem Zoltan. Turns out the problem involved counting the # of LIS (longest increasing subsequence) in an array. I never coded this before and wanted to ask Codeforces community to verify that what I do is correct.

My idea is the following:

FindNumberOfLIS(nums):
    len is an array where len[i] is the length of LIS that ends at nums[i]
    cnt is an array where cnt[i] is the number of such LIS that end at nums[i]
    for i in [1..n]:
        let maxlen be the maximum len[j] for j in [1..i-1] and nums[j] < nums[i]
        let sumcnt be the sum of cnt[j] for j in [1..i-1] and nums[j] < nums[i] and len[j] == maxlen
        then len[i] is clearly maxlen+1 and cnt[i] = sumcnt
    return cnt[j] associated with maximum len[j]

The algorithm above is O(n2). If not for the constraint nums[j] < nums[i] we could have used segment tree. Therefore what I do is sort the initial nums into sortednums and create a segment tree relative to sortednums. Now on each step I would find maxlen and sumcnt in my segment tree from 1 to position of nums[i] in sortednums. In the end I return the sumcnt on the entire segment tree.

Can anyone tell me if it's correct? And if possible, tell me how you deal with duplicates since they are pretty annoying.

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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by nhtrnm (previous revision, new revision, compare).

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

Yes, the O(N2) idea is correct. You can change it a little bit, so that the segment tree idea is more intuitive and can handle dublicates. Instead of storing the length and count for each index, you should store them for a number. At each step len[i] will be the LIS ending at a number with value i. Similarly, cnt[i] will be the number of these LISes. When you are at the i-th index, just loop from 1 to nums[i] - 1 and update the length and count for nums[i]. In order to speed this up, let's use a segment tree, where the i-th leaf contains len[i] and cnt[i]. Each internal node will store the maximum length of a LIS, len, in its subtree and the number of these LISes (cnt).

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Yeah so I was on the right track, thank you!

    I also found out a non-segment-tree solution using two binary searches on each step. If you are interested, the link is here.

    → Reply