PROBLEM LINK:
Setter- Ritesh Gupta
Tester- Encho Mishinev
Editorialist- Abhishek Pandey
DIFFICULTY:
Easy
PRE-REQUISITES:
Implementation
PROBLEM:
Given a 2-D matrix of size N \times M find the number of sub-rows and sub-columns such that-
- The subrow and sub-column intersect at their centre.
- The subrow and sub-column are of same length.
- Their lengths are odd.
- The subrow and sub-column are both palindrome.
QUICK-EXPLANATION:
Key to AC- \text{``Just do what the problem says!"} - @melfice
Realize that brute force is O(NM * min(N,M)) and since N \times M \leq 10^5, this means that min(N,M) < 350 and hence brute force works!
Hence, for every cell of the matrix, assume that cell (say, A_{i,j}) as the center where the subrow and sub-columns are to intersect. Then, extending all four sides - left, right, up and down, check cells at distance of 0,1,2,...,k (where k is max possible length till we find valid subrows and subcolumns) . These would yield the sub-rows and sub-columns of length 1,3,5,...2*k+1, i.e. subrows and sub-columns of odd and same length centered at cell A_{i,j}.
Now the only check we need to do is to check if they are palindrome which can be easily done on the go.
EXPLANATION:
We will divide the explanation into various parts of the brute force, namely the following-
- Estimating the time complexity
- Checking palindromes on the go
- Wrapping up Brute Force
- Can it be made faster?
Lets start with it then 
Estimating the Time Complexity of brute force
Lets admit it. There are multiple people who’d have submitted the brute force for partial and were surprised to see \color{lightgreen}AC. Or some people who wouldn’t have submitted any solution trying to think of an optimised solution to this problem.
This is not good! And the root cause is error in fundamental calculations of time complexity. And I think I know what this fundamental error is!
“Ohhhhhhhh, the brute force is O(N*M*Something) ZOMGOSH its cubic!!! No chance of passing!!”
So, it turns out that while the brute force is cubic, it passes pretty easily. And the essence lies in this ``Something" factor in our calculation.
Realize that since sub-row and sub-column need to be of same length, centered on current centre A_{i,j}, the maximum distance k a cell can be from centre is min(N,M)/2. This is because if the distance of any cell is more than that, then at least one of the cells in sub-row or sub-column will lie outside the dimensions of matrix. If you need an example, I have put one in bonus section. 
Why is this important? This is important because this means the ``Something" we computed earlier is only of order min(N,M). It can be shown that min(N,M) \leq \sqrt{N*M}. (How? - Answer in bonus section.)
This makes the time complexity somewhat O(N*M*\sqrt{N*M}) or O( (N*M)^{1.5}), which easily fits the time limit given N*M \leq 10^5.
Checking Palindromes on the go
This section is easy to explain with an example.
Say we have a string S=``aba" and we want to check if its palindrome. What do we do?
We check using the following check - \text{Is character at index i == character at index (n-i)?} (Assuming 1-based indexing). So, we namely check the following -
- \text{Is character at index 1 == character at index 3?} (i.e. is a==a?)
- \text{Is character at index 2 == character at index 2?} (i.e. is b==b?)
Say I tell you that now I modified S by adding a new character C_1 in front of S and a new character C_2 at back of string. That is, S= ``C_1abaC_2". We will now check-
- \text{Is character at index 1 == character at index 5?(i.e. is }C_1==C_2?)
- \text{Is character at index 2 == character at index 4?} (i.e. is a==a?)
- \text{Is character at index 3 == character at index 3?} (i.e. is b==b?)
How many new checks did we have to do, given that we had already done check for when S was just ``aba" ? The only new check is if C_1==C_2, rest of the checks have already been done earlier!
This C_1 and C_2 correspond to the first and last element of the sub-row/sub-column under consideration. In other words, if we are looking at subrows/subcolumns of length (2*k+1), C_1 and C_2 are the cells at distance of k from centre on either side of it.
As observed above, we only need to check if C_1 and C_2 are equal or not to check if the subrow/subcolumn is still palindrome or not. This is important because checking the entire row or column again and again to check palindromity works in O( (N*M)^2) which will time out!
So TLDR, only check the extreme elements instead of entire subrow or subcolumn since if we are looking at subrow/subcolumn of length 2*k+1, this means that subrow/subcolumn of length 2*(k-1)+1 was palindrome (else we would have stopped earlier) so only the extreme elements need to be checked!
Wrapping up the Brute Force
Now all that is left is to implement the solution.
Firstly, subrow and subcolumns of length 1 , i.e. those spanning only 1 element A_{i,j} count. The best thing to do is that for every element A_{i,j}, first assume it to be the centre of subrow and sub-columns and gradually extend.
Meaning, first take A_{i,j} as centre. Then, in all 4 directions - Up, Down, Left and Right, extend k=1,2,3,... cells beyond one by one, and keep going till you find the subrow and subcolumn both are palindrome and contributing to the answer.
Beyond this, there is actually not much to say here about it, since it is a simple implementation of brute force. The only useful thing I can add here is asking to be careful from common errors like \text{Index Out of Bounds} which can cause undefined behaviour in C++ and/or RE:NZEC in other languages.
Below is a commented snippet from setter’s code-
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
int u,v,w,x;
u = v = i; // u and v point to extreme/corner/start and end elements of subrow
w = x = j; // Similar to u and v but for subcolumns columns
int cnt = 0;
//While u,v,w,x are within the matrix.
//The a[u][j] == a[v][j] check is similar to the Is C1==C2 check for row.
//The a[i][w] == a[i][x] is the C1==C2 check for columns.
while(u >= 0 && v < n && w >= 0 && x < m && a[u][j] == a[v][j] && a[i][w] == a[i][x])
{
u--;
v++;
w--;
x++;
cnt++;
}
ans += cnt;
}
}
Can it be made faster
To all te folks who brainstormed thinking of a better solution than brute force - Yes, it can be made faster.
There exists a O(N*M *log[ min(N,M) ]). If you look at our solution, you will realize that palindrome checking is the bottleneck contributing to min(N,M) factor to the time limit.
But realize the following -
If a subrow/sub-column of length k is palindrome, this means that subrow/sub-columns of length x such that x \leq k are also palindrome! This is easy to see if you have a re-look at the example in Checking Palindromes on the go section.
Additionally, if a subrow/subcolumn of length k is NOT palindrome, then any subrow/sub-column of length >k will not be palindrome as well.
This monotonicity allows us to binary search on the length of subrow and subcolumn, i.e. on k. To quickly check if a subrow/subcolumn of given length is palindrome or not, we will do some pre-processing to compute row and column hashes and using hashing to check the palindromity in O(1). This will be similar to Checking if a String/Substring is Palindrome or Not .
You can refer to tester’s solution for more details (shout-out to @enchom !)
SOLUTION
Setter
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while(t--)
{
int n,m;
cin >> n >> m;
int a[n][m];
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
cin >> a[i][j];
}
int ans = 0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
int u,v,w,x;
u = v = i;
w = x = j;
int cnt = 0;
while(u >= 0 && v < n && w >= 0 && x < m && a[u][j] == a[v][j] && a[i][w] == a[i][x])
{
u--;
v++;
w--;
x++;
cnt++;
}
ans += cnt;
}
}
cout << ans << "\n";
}
}
Tester
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
typedef unsigned long long ullong;
typedef long long llong;
int t;
int n,m;
vector<int> grid[100111];
const ullong B = 127ULL;
ullong Bpows[100111];
struct HashMachine
{
vector<ullong> hashes;
void clear()
{
hashes.clear();
}
void add(ullong val)
{
if (hashes.empty())
hashes.push_back(val);
else
{
ullong h = hashes.back();
h = h * B + val;
hashes.push_back(h);
}
}
ullong getHash(int L,int R)
{
L--;
R--;
ullong res = hashes[R];
if (L > 0)
res -= hashes[L-1] * Bpows[R - L + 1];
return res;
}
ullong getHashInv(int L,int R)
{
L = hashes.size() - L + 1;
R = hashes.size() - R + 1;
return getHash(R, L);
}
};
HashMachine rows[100111], invRows[100111];
HashMachine cols[100111], invCols[100111];
bool segPali(HashMachine &straight, HashMachine &inverse, int L, int R)
{
return straight.getHash(L, R) == inverse.getHashInv(L, R);
}
bool rowPali(int cx, int cy, int r)
{
if (cy - r < 1 || cy + r > m)
return false;
return segPali(rows[cx], invRows[cx], cy - r, cy + r);
}
bool colPali(int cx, int cy, int r)
{
if (cx - r < 1 || cx + r > n)
return false;
return segPali(cols[cy], invCols[cy], cx - r, cx + r);
}
void getHashes()
{
int i,j;
for (i=1;i<=n;i++)
{
rows[i].clear();
invRows[i].clear();
for (j=1;j<=m;j++)
{
rows[i].add(grid[i][j]);
}
for (j=m;j>=1;j--)
{
invRows[i].add(grid[i][j]);
}
}
for (i=1;i<=m;i++)
{
cols[i].clear();
invCols[i].clear();
for (j=1;j<=n;j++)
{
cols[i].add(grid[j][i]);
}
for (j=n;j>=1;j--)
{
invCols[i].add(grid[j][i]);
}
}
}
int main()
{
int i,j;
Bpows[0] = 1ULL;
for (i=1;i<=100010;i++)
{
Bpows[i] = Bpows[i-1] * B;
}
scanf("%d",&t);
for (int test=1;test<=t;test++)
{
llong ans = 0;
scanf("%d %d",&n,&m);
for (i=1;i<=n;i++)
{
grid[i].resize(m+1);
}
for (i=1;i<=n;i++)
{
for (j=1;j<=m;j++)
{
scanf("%d",&grid[i][j]);
}
}
getHashes();
for (i=1;i<=n;i++)
{
for (j=1;j<=m;j++)
{
int l = 1, r = min(min(i-1, j-1), min(n-i, m-j)), mid, best = 0;
while(l <= r)
{
mid = (l + r) / 2;
if (rowPali(i, j, mid) && colPali(i, j, mid))
{
best = mid;
l = mid + 1;
}
else
r = mid - 1;
}
ans += (best + 1);
}
}
printf("%lld\n",ans);
}
}
Time Complexity=O(N*M*\sqrt{N*M}) for setter and O(N*M*log(N*M) ) for tester.
Space Complexity=O(N*M)
CHEF VIJJU’S CORNER
Example to prove maximum length is min(N,M)/2
For instance, let some particular row in the array be Row \ r = \{2,3,1,7,8\}. Say that number of columns is large. Without knowing the number of columns I can claim that maximum distance from centre cell possible is 2 (or \leq 2 if number of columns is small!) possible when centre cell is at value cell with 1 (Cells with value 2 and 8 are at distance k=2 .)
Proof that Min(N,M)<= Sqrt (N*M)
\text{Formal proof to prove: min(N,M)} \leq \sqrt{N*M}
Lets assume that our assumption is wrong, meaning, min(N,M) can be greater than \sqrt{N*M}.
Without loss of generality, let N be the smaller dimension, i.e. min(N,M)=N and hence-
N > \sqrt{N*M} (as assumed above)…eq (1)
Since M is the larger dimension, M needs to be at least as large as N.
\implies M > \sqrt{N*M}....eq(2)
Multiplying equation 1 and 2, we get-
N*M >(\sqrt {N*M})^2
\implies N*M > N*M
which is a contradiction. Hence, our assumption that min(N,M) > \sqrt{N*M} is wrong.
Tester's Notes
The basic idea for faster solution is that if we make a polynomial hash of each prefix of a row, we can then easily find the hash of any interval in that row. We, hence, do that for each row and for each column, as well as for the reverse of each row and each column. All of that is O(N*M) and we can then verify if an interval of a row/column is a palindrome in O(1) by comparing the hashes of the interval and its inverse. We then fix each center cell and do binary search to find the largest palindrome cross with that center. Total complexity is O(N*M*log(N*M)).
Beware the 5 sins when solving this problem
If thou art solving this problem, thou must not commit the sins below!
- Using unintialised variable to store answer.
- Not properly checking the bounds and going out-of array bounds.
- Not realizing the difference between working of below 2 code snippets:
while(i < n and A[i]%2==0) ++i;while(A[i]%2==0 and i < n) ++i;
- Not comparing your solution with other solutions with neater implementation
- Not liking this editorial!
