farnabaz's blog

By farnabaz, 7 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

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

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

    O(RlogN) not O(NlogN), where R is a special parameter that can be bigger than MN, but in many cases it's small enough.
    the algorithm is mentioned in Algorithms on Strings, Trees and Sequences by Dan Gusfield

  • »
    »
    7 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

    • »
      »
      »
      7 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.

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

        The time complexity of the above algorithm is O(r logk) where r is a parameter that can vary and in worst case can be as bad as n*m and k is length of longest common subsequence of two string , so the worst case running time can be O(n*n*logn) but in many cases in real application r is small enough ,also the (theoretically) fastest algorithm for longest common subsequence runs in O(n log s + c log log min(c,mn/c)) developed by David Eppstein,and if you say that some algorithm is wrong you should show a counter example and if you can't go for proof !

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

        It's not all incorrect. There is a reduction from LCS to LIS: http://apps.topcoder.com/forums/?module=Thread&threadID=594064&start=0&mc=21#891898

        However this solution only works when at most one sequence has repetitions.

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

          The solution work when we calculate the Longest strictly Increasing subsequence

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

        counter example: azabbgfhtuazargfhaza ppazassgfhjkgfhazasxvaza

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

          I'm not sure your are computing LCS correctly, the LCS of your counter example with the following code is 12, same as my O(RlogN) algorithm, it's not a counter example for algorithm.

          int lcsLength(char X[],char Y[]){
              int m=X.length;
              int n=Y.length;
              int T[][]=new int[m+1][n+1];
              for(int i=0;i<=m;i++)
                 T[i][0]=0;
              for(int i=0;i<=n;i++)
                 T[0][i]=0;
              for(int i=1;i<=m;i++){
                 for(int j=1;j<=n;j++){
                   if(X[i-1]==Y[j-1])
                    T[i][j]=T[i-1][j-1]+1;
                   else
                    T[i][j]=Math.max(T[i-1][j],T[i][j-1]);
                 }
              }
              return T[m][n];
          }
        • »
          »
          »
          »
          »
          7 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!

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

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

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

              A=B=aa...(50000 times) is the worst case for this algorithm with O(n^2logn) running time and O(n^2) memory usage

    • »
      »
      »
      7 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.

»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

if some get AC in the question then please post the soltuion