KRECT - Counting K-Rectangle
Given a M*N square board. Each square contains a letter of the English alphabet ('A' .. 'Z').
A K-rectangle of the board is a rectangle whose sides are parallel to the sides of the board, and contains exactly K different types of letter.
For example, with this 4*3 board:
CED CEB CBC DDA
The rectangle [(1,1), (2,2)] is a 2-rectangle of the board because it contains 2 different letters: C and E.
Given M, N, K and the M*N board. Determine how many K-rectangles there are in the board.
The first line contains 3 integers M, N and K. (1 ≤ M, N ≤ 100, 1 ≤ K ≤ 26)
The following M lines, each contains N letters of the English alphabet ('A' .. 'Z')
Write one integer - the number of K-rectangles in the given board.
Input: 4 3 3 CED CEB CBC DDA Output: 12
I need to stop getting swayed away by constraints and tags :/
@Rafail it was informative , I never knew it but rather building up table was faster! O(1) queries you see.
to avoid counting the 1s in the binary representation in O(A) linear time you should just use a built-in function. Search and you shall find!
strict time limit :)
Got AC with O(n^4)
How is number of rectangles in given test case 12, mine answer is 7.
my solution of complexity O(n^2*m^2*26) is not getting accpeted
it's weird.. when I submitted my code(O(n^4)) and with LANG C++ 4.3.2 it passed all the test cases in 4.62 sec but when I submitted the same code with LANG C++ 4.0.0-8, the result it TLE...
Jelle van den Hooff:
O((NM)^2) works great, but you have to keep the constant factor _low_.