Advertisement blocking software were detected ;( Please add this webpage to whitelist.

KRECT - Counting K-Rectangle

no tags 


Added by:Race with time
Date:2009-05-05
Time limit:0.343s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel Pentium G860 3GHz)
Languages:All except: ERL JS NODEJS PERL 6 VB.net
Resource:Based on problem CRECT - @vnoi

hide comments
xxbloodysantaxx: 2015-07-03 08:45:51

@Rafail it was informative , I never knew it but rather building up table was faster! O(1) queries you see.

Rafail Loizou: 2015-04-14 16:42:34

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!

Nivin : 2014-03-31 06:25:21

strict time limit :)

aristofanis: 2014-02-14 15:09:51

Got AC with O(n^4)
HINT: think like a computer; in binary :)

himalay: 2014-02-13 23:04:54

How is number of rectangles in given test case 12, mine answer is 7.

rishabhshinghal: 2014-01-18 11:30:16

my solution of complexity O(n^2*m^2*26) is not getting accpeted

Eternia: 2009-11-27 03:30:14

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.

Jelle van den Hooff: 2009-10-02 05:48:01

O((NM)^2) works great, but you have to keep the constant factor _low_.

stjepan: 2009-10-02 05:48:01

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
Robert Gerbicz: 2009-10-02 05:48:01

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