ghader's blog

problem related to LIS from oj.uz
By ghader, history, 5 months ago, In English

hello

i have been thinking on this problem for a long time link. i would be thankful if anyone has any ideas.

Tags lis
  • Vote: I like it
  • -1
  • Vote: I do not like it

»
5 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

I think I have an idea, although I haven't (and probably won't) implemented it yet.

Notice that we have the max length of an LIS being $$$O(\sqrt{N})$$$. Also, if we compress values, each one can also be bounded by $$$O(\sqrt{N})$$$. So, if we could; for each length; find the first moment in time when it's obtainable, we'd be done.

This is easy to do by making $$$\sqrt{N}$$$ different segment trees, each of length $$$\sqrt{N}$$$, and performing a regular LIS dp. Of course, you will need to turn the online problem into an offline one by preprocessing insertions, but this is farily straightforward to do.

The time complexity should be $$$O(N \log{N})$$$, where $$$N=\sum{a_i}$$$.

→ Reply
  • »
    »
    5 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    lis is not bounded by $$$O(\sqrt(N))$$$. the counter example is 1 2 3 4....n.

    → Reply
    • »
      »
      »
      5 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      That is not possible, since $$$\frac{n(n+1)}{2} = O(n^2) \gt 10^6$$$ (recall the bound on the sum of all potatoes). It is bounded by $$$O(\sqrt{n})$$$.

      → Reply
      • »
        »
        »
        »
        5 months ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        you are right. can you please elaborate more on the segment tree part?

        → Reply
        • »
          »
          »
          »
          »
          5 months ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          Yes, so you know how in regular LIS dp, we store the $$$\text{dp}[j]$$$ at $$$\text{st}[a[j]]$$$, right?

          We do something somewhat similar here. We make $$$O(\sqrt{n})$$$ different segment trees, say the $$$i$$$-th one is $$$\text{trees}[i]$$$. $$$\text{trees}[i]$$$ will store the minimum time (for each and every possible $$$a[j]$$$ value the LIS ends at) that a sequence of length $$$i$$$ is obtainable.

          Notice that we can do this, since $$$O(\sqrt{n} \times \sqrt{n}) = O(n)$$$. What would our transitions be? We'd iterate over elements ($$$a[j]$$$) in increasing order of index and set $$$trees[i][a[j]] = \min(\text{trees}[i][a[j]], \max(\text{time}[j], \text{trees}[i-1].\text{query}(1, a[i])))$$$.

          In simple words, we're just looking at all sequences of length $$$i-1$$$ and choosing the one with the minimum time. Of course, since we now include $$$a[j]$$$, we should take the max of this and $$$\text{time}[j]$$$ to get our new time.

          Notice that we only iterate $$$i$$$ from $$$1$$$ to $$$a[j]$$$ since a sequence of length longer than $$$a[j]$$$ will never have $$$a[j]$$$ as its $$$ \gt a[j]$$$-th element (the 'worst case' is $$$1,2,3,...$$$).

          Please ask if you have more questions! I don't know if I did the best job explaining, and I'd be happy to clear any further doubts.

          → Reply