Sphere Online Judge

SPOJ Problem Set (classical)

4329. Counting K-Rectangle

Problem code: KRECT

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:


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.


4 3 3


Added by:Race with time
Time limit:1.5s
Source limit:50000B
Memory limit:256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)
Languages:All except: ERL JS NODEJS PERL 6
Resource:Based on problem CRECT - @vnoi

hide comments
2014-03-31 06:25:21 Nivin Anton A L
strict time limit :)
2014-02-14 15:09:51 Aristofanis Rontogiannis
Got AC with O(n^4)
HINT: think like a computer; in binary :)
2014-02-13 23:04:54 himalay
How is number of rectangles in given test case 12, mine answer is 7.
2014-01-18 11:30:16 rishabhshinghal
my solution of complexity O(n^2*m^2*26) is not getting accpeted
2009-11-27 03:30:14 Eternia
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...
Please tell me how this problem can occur. Thanks.
2009-10-02 05:48:01 Jelle van den Hooff
O((NM)^2) works great, but you have to keep the constant factor _low_.
2009-10-02 05:48:01 Stjepan Glavina
My solution is a O(n^2*m^2) algorithm and it is the fastest at the moment.

Last edit: 2009-06-03 19:22:36
2009-10-02 05:48:01 Robert Gerbicz
I think no.
By a possible swapping of row<->column my solution's complexity is O(min(m,n)^2*max(m,n)*|A|), where A is the alphabet, so here |A|=26.

Last edit: 2009-05-06 19:19:19
2009-10-02 05:48:01 .:: Pratik ::.
Just a hint.
Does this problem allow a O(n^4) solution to clear?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.