Problem Link
Author : Jatin Yadav
Tester : Misha Chorniy
Editorialist : Anand Jaisingh
Pre-Requisites :
Suffix arrays, LCP arrays, DSU, dynamic segment trees.
Explanation :
What I explain here is a completely deterministic O(N \cdot M \cdot log^{2} N ) solution, intended by the setter. There are other O(N \cdot M \cdot min(N,M)) solutions, that may easier to come up with and code, but may use non-deterministic ways like hashing.
If you want to read a good O(N \cdot M \cdot min(N,M)) solution, I suggest reading this code, it is quite easy to understand overall. Now, let’s begin with our solution :
So, First, for each cell, let’s consider this cell as a cell in the first column of some sub-matrix, and let’s count for each width, the number of different sub matrices where this sub array of columns beginning in this cell is not identical to any sub array of columns above it, in the same sub matrix.
This is like if some sub matrix contains multiple occurrences of the same row, then we just count it’s first occurrence, none after it.If we add this for each cell, that’s the answer we want. If, for each cell, we can find its lcp ( longest common prefix ) for each row above it beginning in the same column, we make a good start.
Assume, we calculate for each cell (i,j) for each cell in the same column above it, the last column until which they share the same element in each position. For some cells (i,j) and (k,j), let’s call this value val[j][i][k]. We can calculate this table in O(N^3 + N \cdot M) time. Also, let val[j][i][k]=j-1 , whenever k \ge i . Now, Let :
max(j,i,k) = maximum of val[j][i][x] , k \le x < i .
f(i,j) = \sum_{k=i}^{0} m-1-max(j,i,k) .
Then the answer is :
\sum_{i=0}^{N-1} \sum_{j=0}^{M-1} f(i,j) \cdot (N-i) .
We can finish all of this in O(N^3 + N \cdot M ) time, and O(N^3) memory. This should be good enough to pass sub task 1.
Now, you should read about suffix arrays before proceeding further. You can read about it here or on any other online resource
Now, its obvious the part where we find the lcp of each pair of cells in the same column is very costly. We can optimize this part using Suffix arrays and lcp arrays. Let’s create a vector V , containing all elements inside the grid, inserted in it from left to right, top to bottom.
Now, assume this vector to represented some imaginary string where the i^{th} character of this string is the v[i]^{th} character of some unknown alphabet. Let’s try and construct a suffix array for this string, since a suffix array does not depend upon the size of the alphabet.
Let the suffix array be called sa[], now let’s construct the lcp array in O(N \cdot M) or O(N \cdot M \cdot log(NM) time, where lcp[i]=lcp(sa[i],sa[i-1]) \hspace{0.2cm} i \ge 1
Now, things may get hard, multiple reads may help. We now mention one important property of lcp arrays that is going to help us solve this problem :
Assume we want to find the lcp of 2 suffices beginning in index i and j respectively. Let the rank of suffix beginning at i be x, and y for j. Then the lcp of suffices i,j is min(lcp[x+1],lcp[x+2]...lcp[y], x < y . You can try and prove this yourself.
In fact, we we sort the ranks belonging to a single column let’s call this set Z, then the lcp of any set of cells belonging to the column is always among the lcp of some adjacent cells in Z. This is obvious after we notice the property above.
Now, the approach we are going to take is to first find the sum of the number of rows over each sub matrix, and then we are going to find for each sub matrix the number of duplicate rows, and subtract these results later.
Now, let’s see how we can operate over the ranks belonging to a single column. Let the set of ranks belonging to some column be r_0,r_1...r_{n-1} in sorted order. Let’s add lcp of r_i,r_{i-1} to a set S, and let’s sort this set, the elements of this set be called f_0,f_1,...f_{n-2}, f_0 being the highest value. Also, we maintain some sets, where initially the set for each r_i contains only itself. Now, let’s use the f_{i}'s one by one. Let some f_i correspond to r_x,r_y.
Then we maintain some kind of dsu, where we merge sets belonging to r_x,r_y . Initially, each r_i is the rank of some row belonging to the column. So, when we merge some sets with parents r_x,r_y, we know that all the rows on merger of these sets will share lcp exactly equal to f_i.
Basically, intuitively think of it like this, we add some ranks belonging to the suffix array, in decreasing order, and whenever we have a contiguous set of elements from the suffix array, we know the lcp of the rows these ranks correspond to is the minimum of their sub array
While we add these f_i's one by one, we need to maintain some kind of sums, that let’s us calculate what we need. We can maintain these sums using segment trees, maintain a segment tree, a dynamic one for each dsu. When we merge two sets, we can update the elements of the smaller set in the segment tree of the larger set. In this way, each element moves at max O(log(N)) times.
For example, let’s explain this better via simulation for a single column :
Let the set of ranks belonging to a single column be [1,5,10,23] corresponding to rows 2,3,4,1 . Now, let lcp(1,5)=2,lcp(5,10)=3,lcp(10,23)=1. Now, let’s add the f_i's one by one, i.e. 3,2,1.
Add 3 : Merge (5),(10) , now we know rows 3,4 share lcp of 3.
Add 2 : Merge (5,10),(1), now we know rows 2,3,4 share lcp of 2
Add 1 : Merge (1,5,10),(23), now we know rows 2,3,4,1 share lcp of 1.
At each step, we alter some sums, that let’s us know for each row in the column, the number of sub-matrices in which it is a duplicate. We can sum this all over. This sum is of the type , in the current set, we find for each row the closest element to its left in the current set, and the lcp value of all the rows in this set let it be k. Then whenever, the current row as well as its left neighbour from the set are in the same sub matrix and we choose a width of \le k for the sub matrix, then the current row is a duplicate.
How we maintain these sums is that for a single set belonging to the dsu, we maintain a segment tree for it, and mark for each row belonging to this set, the leaf nodes for the row += 1. Then, when we merge two nodes, lets call them left and right, :
Whenever the rightmost row that belongs to the left child of the current node and the leftmost row belonging to the right child of the current node and there together in a single sub matrix with lcp \le current f_i for this set, we sum that one of these rows is a duplicate.
So, basically, each r_x is merged with its right most neighbour in the current set at some point when we merge two segment tree nodes, and we have managed to sum all duplicates. Later, when we merge two sets, we move all the rows belonging to the smaller set to the segment tree belonging to the larger set.
With this, we can prove each element moves a maximum of log N times, this is something called as small to large technique
Now, last step should be just reading the code, and you should be able to understand what has been stated quite easily. I highly recommend reading this code, a beautiful and completely deterministic solution.
Author’s Code : Link
Another beautiful Solution : Link