farnabaz's blog

By farnabaz, 11 years ago, In English

I tried to solve LCS0 on SPOJ with O(r log n) algorithm, but i'm getting TLE, is there any linear algorithm for this problem??

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

| Write comment?
»
11 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I think there is no NLogN algorithm. Can you describe your solution or publish your code?

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

    The algorithm is based on converting LCS to LIS ,for conversion we do as follow
    first for each character c in A we make a list of index of occurrence of c in B in descending order for example if we have A=abababab and B=bcbb first character of A is a and a didn't occurs in B , second character of A is b the descending list of occurrence indexes is { 4,3,1} because b occurs in positions 1 and 3 and 4 , we should make this lists for each character of A

    a= {}  
    b={4 ,3 ,1}  
    a={}  
    b={4 ,3 ,1}  
    a= {}  
    b={4 ,3 ,1}  
    a={}  
    b={4 ,3 ,1}

    now we replace each character of A with new calculated list as follows and make A'
    A'={}{4,3,1}{}{4,3,1}{}{4,3,1}{}{4,3,1}=4,3,1,4,3,1,4,3,1,4,3,1
    now the LIS in A' is LCS of A and B

    • »
      »
      »
      11 years ago, # ^ |
      Rev. 4   Vote: I like it 0 Vote: I do not like it

      Algorithm described above must not get TLE it must get WA because algo is incorrect.There is no nlogn algo the fastest algo's complexity is O(n * ceil(m/log n)) (n >= m). Recurrence : dp[i][j] = max((a[i] == b[j]) * (dp[i — 1][j — 1] + 1), max(dp[i — 1][j], dp[j][i — 1])); We can notice that we need only two rows then we can store only array of size [3][50000]. Such solution must get AC.

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

        counter example: azabbgfhtuazargfhaza ppazassgfhjkgfhazasxvaza

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

          now lets run the algorithm on your counter example :

          if A=azabbgfhtuazargfhaza and B=ppazassgfhjkgfhazasxvaza then we shoul have

          a -> { 24, 22, 18, 16, 5, 3 }
          z -> { 23, 17, 4 }
          a -> { 24, 22, 18, 16, 5, 3 }
          b -> { }
          b -> { }
          g -> { 13, 8 }
          f -> { 14, 9 }
          h -> { 15, 10 }
          t -> { }
          u -> { }
          a -> { 24, 22, 18, 16, 5, 3 }
          z -> { 23, 17, 4 }
          a -> { 24, 22, 18, 16, 5, 3 }
          r -> { }
          g -> { 13, 8 }
          f -> { 14, 9 }
          h -> { 15, 10 }
          a -> { 24, 22, 18, 16, 5, 3 }
          z -> { 23, 17, 4 }
          a -> { 24, 22, 18, 16, 5, 3 }
          
          A'= { 24, 22, 18, 16, 5, 3 } { 23, 17, 4 } { 24, 22, 18, 16, 5, 3 } { } { } { 13, 8 } { 14, 9 } { 15, 10 } { } { } { 24, 22, 18, 16, 5, 3 } { 23, 17, 4 } { 24, 22, 18, 16, 5, 3 } { } { 13, 8 } { 14, 9 } { 15, 10 } { 24, 22, 18, 16, 5, 3 } { 23, 17, 4 } { 24, 22, 18, 16, 5, 3 }
          
          A'=24, 22, 18, 16, 5, 3, 23, 17, 4, 24, 22, 18, 16, 5, 3, 13, 8, 14, 9, 15, 10, 24, 22, 18, 16, 5, 3, 23, 17, 4, 24, 22, 18, 16, 5, 3, 13, 8, 14, 9, 15, 10, 24, 22, 18, 16, 5, 3, 23, 17, 4, 24, 22, 18, 16, 5, 3, 12

          now if you calculate the Length of Longest Strictly Increasing Subsequence of A' you get 12 same as a DP solution.i strongly suggest you to read the **Dan Gusfield ** book or if you don't like go for a better counter example and try your best!

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

            How would A' look like if A = aa...a(50000 times)?

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

      The reduction from LCS to LIS works only when at least one sequence hasn't repetitions. This problem can be solved in O(NM) time complexity using O(max(N,M)) memory complexity.