ahmed_nabiil's blog

Longest Increasing Subsequence with some changes
By ahmed_nabiil, history, 4 years ago, In English

I wonder how to solve this question

you have array of size n where 1 <= n <= 100 and 1 <= t <= 10^7 where every element of the array is less than 10^3 the array size is n*t and for every index > n -----> array[i] = array[i-n] you only given n elements for example if n = 3 and t = 2 and the given array is {1,2,3} so you should calculate the LIS for {1,2,3,1,2,3}

what is the longest increasing subsequence? any idea !?

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

»
4 years ago, # |
  Vote: I like it +30 Vote: I do not like it

Since there are at most 10^3 elements in the LIS, you only need to repeat the array 10^3 times. So now the array has at most 100 * 10^3 = 10^5 elements, and you can solve for the LIS normally.

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

    Okay thank you

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

    What happen if LIS is not strictly increasing?

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

    n is 100 so you need to repeat maximum 100 times

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

    I think Hd7 is right

    suppose the example n = 3 and t = 100 and for simpelecity lets say arr[i] < 3

    if array = {1,1,2}

    then your answer wiil be LIS of 1,1,2,1,1,2,1,1,2 which is 7 + 100-3 = 104

    but the actuall answer is 100*2 = 200 as we can take 1,1 from every sequence of t

    → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

Compress $$$A$$$, and let $$$M=min(N, A)$$$. Now you have $$$O(MNlogM)$$$.

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

Any idea if there is duplicates ?

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

solution for longest nondecreasing subsequence. (let's still call it LIS)

call copy of array good if there are at least $$$2$$$ unequal elements in LIS from this copy. then there are at most $$$n$$$ good copies. and if most frequent element of array occurs $$$x$$$ times in it, then from every bad (not good) copy, there will be at most $$$x$$$ elements in LIS, and we can always position bad arrays in such a way that there are exactly $$$x$$$ elements from it in LIS, so if answer for $$$n$$$ copies is $$$A$$$, then answer for $$$t$$$ copies (if $$$t>n$$$) will be $$$A + (t-n)\cdot x$$$.

→ Reply