CHFDORA - Editorial

PROBLEM LINK:

Div1
Div2
Practice

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 :smiley:

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. :slight_smile:

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 :smiley:

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!

  1. Using unintialised variable to store answer.
  2. Not properly checking the bounds and going out-of array bounds.
  3. 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;
  4. Not comparing your solution with other solutions with neater implementation
  5. Not liking this editorial! :stuck_out_tongue:
Related Problems
24 Likes

Could someone tell me what is the difference between these two statements?

2 Likes

The difference is in the checking of i<n.
i<n should be checked first to ensure that a[i] exists.

2 Likes

The comparison operators work from left to right so the first condition is checked first and if it is false then second condition is not checked. So, the first code is correct. If the index is greater than the size of array the second condition will not be checked hence removing the array out of bound error.

I have the same code as tester’s. Can anyone please point out the error.
https://www.codechef.com/viewsolution/28976490

The test cases were weak and my
O(N*M*min(N,M)*min(N,M)) was passing with 100 pts in 0.79 secs.
I reported in comments section (on 7th january) but no action was taken.

https://www.codechef.com/viewsolution/28756074

@alei @rishup_nitdgp @enchom @vijju123
Can we improve problem for practice section at least.

https://www.codechef.com/viewsolution/28879137
plzz guys help me out with this one my solution is getting TLE even when i did it with same logic

This is quite interesting indeed. It turns out that the problem is not in weak testdata, but perhaps relaxed time limit and surprising speed of the CodeChef system.

In reality close-to-maximal testcases do exist in the current testset.

It might seem that O(N*M*min(N,M)*min(N,M)) is enormous, as for N=M=300 this should be quite close to 10^10. However, in reality its constant factor is very small. It turns out that even the maximal test N=M=316 with only values of 1, results in about 2*10^8 operations with your solution.

The test set has cases with T=3 and N = M = 300, which are very close to the maximum, which would be T=3 and N = M = 316. I am fairly certain that even if we were to add the maximal your solution would still pass as it is a fairly small increase.

In any case, if any action is to be taken to improve the problem for practice, it’d have to be dropping the time limit, perhaps to 0.5s.

2 Likes

Always love @vijju123’s editorials. Especially the related problems part and the extra parts that he includes!

2 Likes

If you write the second statement in your code i.e. while(A[i]%2==0 and i < n) ++i;
As Logical AND (\&\&) is a sequence point (Sequence point is a point in your instruction which makes sure that all the instructions written before it must be evaluated first and any side-effect must be complete) the expression A[i] % 2 == 0 will be evaluated first.
Now if the value of i is \geq n then it is the case of Segmentation Fault and your program will generate SIGSEGV Error.

Thanks for Reading
Peace :v:

I am sure if my solution is fast enough than other optimized solutions will be much more faster.
I think you can try increasing N*M to 5*10^5 or 10^6. Not sure though.

yeah i did the same thing and still got tle can someone explain why?

@vijju123 when can we expect the editorials of the challenge problems? and also of Army of me? Eagerly waiting for the editorial of Army of me :blush::blush::blush:

Very Good editorial!

1 Like

what does this line mean…
given constraints are:

  • 1≤T≤1001≤T≤100
  • 1≤N,M1≤N,M
  • N⋅M≤105N⋅M≤105
  • 1≤Ai,j≤1061≤Ai,j≤106 for each valid i,ji,j
  • the sum of N⋅MN⋅M over all test cases does not exceed 3⋅105

Why were 100 points awarded for the Brute force implementation? I feel that 100 pts should have been awarded for the O(N*M) approach using Manacher’s algorithm.

2 Likes

Great editorial! @vijju123:smiley:

1 Like

@doga5743
https://www.codechef.com/viewsolution/29015248
line 37 break