vishaaaal's blog

Asymptotic bound on number of Longest Increasing Subsequences.
By vishaaaal, history, 3 years ago, In English

Consider an array of length $$$n$$$ and we want to count the number of increasing subsequences such that their length is the maximum among all different increasing subsequences in this array(obviously the count can be more than 1). What will be the asymptotic bound on our answer?
In other words, what is the order of our answer? Is it $$$O(n)$$$ or $$$O(nlogn)$$$ or $$$O(n^2)$$$?
Consider all the elements in the array distinct. Can we also expand the same solution for arrays with multiple occurrences of elements?

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

»
3 years ago, # |
← Rev. 3   Vote: I like it +17 Vote: I do not like it

Not sure about the upper bound but one can construct a case that has $$$N^{\frac{\sqrt N}{2}}$$$ LIS which is much higher than the bounds mentioned in the blog.
For $$$N=16$$$, such example is 4,3,2,1,8,7,6,5,12,11,10,9,16,15,14,13.

It can be generalised for $$$N=L*L$$$ with $$$L^L$$$ distinct LIS. This permutation is the permutation which has $$$min(max(LIS len,LDS len))$$$ which is atleast $$$\sqrt N$$$ a direct consequence of dilworth theorem. Generalised construction was mentioned in last Edu'C discussion.

Also one can easily change the array $$$a_i$$$ with non-distinct elements to the one with distinct elements by just using tuple $$$(a_i, i)$$$ for comparison.

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

Note that an increasing subsequence is an independent set in a graph corresponding to the array, with an edge between vertices $$$i < j$$$ if and only if $$$a[i] \geq a[j]$$$. It is well-known that there can be at most $$$3^{n/3}$$$ inclusion-maximal independent sets in any graph on $$$n$$$ vertices, and it is possible to achieve this bound with a sequence like 3,2,1,6,5,4,9,8,7,12,11,10 etc.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I understand that the bound will come $$$x^{n/x}$$$ if we partition the array into like $$$x$$$ length blocks and in the same fashion as in the example you gave. But what is inclusion-maximal independent set? Could you please elaborate?

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

      It means maximal with respect to the subset-inclusion relation $$$\subseteq$$$ among independent sets, i.e. $$$S$$$ is an inclusion-maximal independent set iff it is independent and there is no strict superset $$$T \supsetneq S$$$ which is also independent.

      Note that a largest or longest object will be inclusion-maximal, but not necessarily vice versa.

      → Reply
»
3 years ago, # |
  Vote: I like it -19 Vote: I do not like it

Problem with similar requirement : Tower Game

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

    The post author's problem means we have to minimize the count of LIS in an array as each time we are removing the LIS from current array. ok looking at the downvotes even providing a problem which requires to find minimum no. of LIS present in an array and similar thing is asked by the author is a crime now on codeforces :) Learnt the lesson :)

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hey, please don't get me wrong. But the problem you've mentioned is actually different than what I had asked.
      I wanted to find the bound on the number of LIS in the array (in some problem, I was thinking if I could find all the LISs). And then I was stuck at this thought.

      No doubt I appreciate your mention :).
      Everyone gets downvotes (sometimes for no good reason). Just let it go.

      → Reply