IITK2P08 - Editorial

editorial
1

Problem link

contest
practice

Difficulty

EASY - MEDIUM

Pre-requisites

two pointers, binary search

Problem

Find number of sub-matrices of a matrix of dimension n * n having exactly K distinct characters from English lower case alphabet.

Solution

Brute Force won’t pass
If for each sub-matrix, we count number of distinct characters in it using O(R * C) where R is number of rows and C is number of columns in matrix. It’s time complexity will be O(n 6) which is too slow.

Fix a particular Height
Fix a height, then try for each 1 <= i <= j <= n such that you are currently looking at row = height and columns from i to j(inclusive). Now for this fixed i, j, you can note that if we iterate over k >= height such that we are currently looking at rectangle (height, i) and (k, j). Then in this rectangle, if we increase k, then number of distinct elements also increase. So you can apply two binary searches over k to solve problem for fixed, height, i and j. So overall complexity will be O(n * n * n * n * log n).

More optimizations
By using the idea, that k will always increase, you can solve it in O(n^4). This idea is called two pointers idea.

You can also use a solution called monotone queue too.

Another solution
It uses trick that K is not that large, K <= 26. So you can use bit-mask idea to solve the problem too.

Tester’s solution:
You can access it here.

1 Like
2

Can I know why my O(n *n *n *n *26) doesn’t pass? Link : CodeChef: Practical coding for everyone

3

Hello Everyone ,

I used this solution during the contest which gets passed over the test data…

Trivially i traversed over the all sub matrices … O(N4) and as there can be 26 distinct characters i have a number corresponding to each submatrix which i used to calculate the number of distinct element by counting the number of set bits in that number .

However to count the number of set bits i used this method (fastest one according to my knowledge level )

int cntset(int x){
	int c = 0 ;
	while(x){
		c ++ ;
		x -= x&-x ;
	}
	return c ;
}

My whole code link

4

How can we use bitmasks to solve it?

5

not sure if this will be faster but since you are calculating bitcount at each step it might be. keep an extra variable let’s say cnt and increment it whenever you encounter a character whose bit is not set