KRYP5 - Editorial


Author: Shivam Garg
Tester: Shiv Dhingra




DP , Merge Sort Tree


Given two arrays of strings, it is required to print the number of ways such that an equal-sized subarray can be extracted from both the arrays and satisfies certain LCS (Longest Common Substring) conditions.


If the conditions in the mentioned question are observed carefully, one will notice that we can
create a matrix X of size N*M, with X(i)(j) = (LCS(i,j)>=K).

The LCS of all the pairs can be found out easily via DP or Suffix Array.

Now, the matrix X is a binary-matrix.
From the conditions, it is quite evident that we need to find a square with the following structure -
alt text
This square will have 1s on all of its borders as well as on the 45-degree diagonal. Other elements can be 0/1.
In other words, we need to find the number of such squares possible in the given matrix.

Now, how to find this?
Well, the diagonals play an important role here. There are a total of N+M diagonals.
So, what we need to find out is-"How many square sub-matrices have their principal diagonal on this particular diagonal?"

alt text

The matrix in the above image is matrix X. We iterate over the diagonals and find how many such required squares lie on that diagonal.
For each (i,j), we compute DP1[i][j] where DP1[i][j] = min of continuous 1’s towards right, up and upward direction in diagonal.
DP1[i][j] is min ( continuous\hspace{1 mm} 1's\hspace{1 mm} towards \hspace{1 mm}right, towards \hspace{1 mm}up, towards\hspace{1 mm} upward \hspace{1 mm}direction \hspace{1 mm}in \hspace{1 mm}diagonal)
Also, we compute DP2[i][j] where DP2[i][j] = min of continuous 1’s towards left, down and downward direction in diagonal.

This can be accomplished using DP.

Now, for each diagonal, we compute RIGHT [ ] array and LEFT [ ] array. They can be obtained from above DP1 [ ] [ ] and DP2 [ ] [ ] VALUES.
RIGHT(i) will be the scope of the square with the bottom-left corner on this diagonal towards the right.
LEFT(i) will be the scope of the square with the top-right corner on this diagonal towards the left.

Now, all we need is that within the range of RIGHT(i), how many LEFT(i) occur such that LEFT(i) covers i.
In other words, let RIGHT(i) be A. Then, in the range j\in[i,i+A-1], how many LEFT(j) occur such that j-LEFT(j)+1 is less than or equal to i.

This can be solved via Merge Sort Tree


Setter’s Solution -

Tester's Solution - 


1 Like