NAINAAAA's blog

LENGTH OF LONGEST COMMON SUBARRAY (NEED HELP) -
By NAINAAAA, history, 3 years ago, In English

Recenty i got stuck in a problem in which i was suppposed to figure out length of longest common subbarray among all rows of a given matrix(n*m) where each row contains permutaion of (1...m) integers .Can anytell how to approach this problem constraints n*m<=1e5 Thanks :)

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

Comments Comments (9)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Maybe you should sort, unique then hash each rows.

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

    sorting will change the order of permutaton so the ans will change :( i think u didnt get the problem right testcase:n=3,m=3 2 3 1 3 1 2 3 1 2 ans =2 ->{3,1}(common subarray)

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

By "B subarray of A" you mean some array B that is created from array A by continiously poping zero or more elements from it's right and left (but not from the middle)? By "common" you mean such two that subarrays that include the same distinct elements and sorted in the same order?

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

    If so, we could take any (zero) row and create mapping, so that map(matrix[0][i]) = i — this would give us a sorted row. Now we could check every row with this mapping — find all sorted sub-arrays in row and then find their intersection and compare which of them is longest.

    If its closer to sub-sequence, then we could have indices of numbers for n rows ( I[i][x] — index of number x in row i ). We could take every number from first row one by one, and check every string — what is the shortest length along all the longest sub-sequences created by putting corresponding index I[i][x] into initially empty i-th array, so this insertion preserves increasing order. (Just like in n*log(n) solution of longest increasing sub-sequence).

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

Well, here are three solutions, two of which treat the problem as "yet another string problem", and the last one is the simplest and problem-specific.

Solution with hashes: binary search over the length of the LCS + hashes. For the fixed length $$$L$$$, count the number of occurrences for each subarray of length $$$L$$$ (well, for hashes instead of actual subarrays). Since all the rows are permutations, all subarrays of a fixed length are unique in each row. Thus, the answer is at least $$$L$$$ if there is a hash for which the number of occurrences is $$$n$$$.

Solution with suffix structures: concatenate all the rows into a long string, separate the rows with different numbers. Then you can build a suffix array, compute the LCP array, and find the largest minimum over the subarrays of LCP with length $$$n$$$. Again, since rows are permutations, it will be the answer.

A simple solution that does not involve anything fancy: let's find what is the longest common subarray that starts with $$$1$$$. How to do it? Just check whether the next number after $$$1$$$ is the same in all rows. If it is the same, move to the next number. Do so, until we reach the end of some row or meet different numbers in a pair of rows. Now do the same for $$$2$$$. We may notice, that if we already accounted $$$2$$$ when we were processing $$$1$$$, then we do not need to process it: it will have a strictly smaller length since it is a suffix of a common subarray starting in $$$1$$$. On the other hand, if it turns out that, at some step of processing $$$2$$$, subarrays in all rows finish with $$$1$$$, then we already know the answer: we just need to add the result that we previously got for $$$1$$$ to what we have found for $$$2$$$.

It gives us the idea of a simple DP: $$$dp[x]$$$ is the longest common subarray that starts with $$$x$$$. If the number after $$$x$$$ is not the same in all rows, then $$$dp[x]=1$$$. Otherwise, $$$dp[x] = dp[y]+1$$$, where $$$y$$$ is the number that follows $$$x$$$ in every row. DP can be computed recursively.

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

    Thank youu so muchh for such a clear and lovely explanation !! :)

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

Abe cheater kitna cheat krogi.. ghatiya log, this problem is from hackerearth solution contest that is ongoing

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

https://codeforces.me/contest/1043/problem/D

→ Reply