Блог пользователя farnabaz

Spoj LCS0
Автор farnabaz, 12 лет назад, По-английски

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??

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
12 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
      ← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        counter example: azabbgfhtuazargfhaza ppazassgfhjkgfhazasxvaza

        → Ответить
        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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!

          → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить