## 11019 - Matrix Matcher

**Moderator:** Board moderators

### 11019 - Matrix Matcher

What, exactly, is a "character" for this problem?

It seems there are characters not in the 'a'-'z' or 'A'-'Z' range.

It seems there are characters not in the 'a'-'z' or 'A'-'Z' range.

I sent my code about ten minutes ago and it's even being judge.

I searched in the submit history and only saw a TLE in this problem, and some problems were sent before mine and they even are being judge with the message: "Statistics not available - Program running".

What is happening?

[minutes later]

I have been seeing that in the old format to see your submissions my submissions in this problem appear "Delayed".

Why? What is happening?

By the way, the time limit is quite tight. During the contest, I got AC in about 2.5 seconds (when the time limit was 5 seconds), with a pretty highly optimized algorithm. (it runs in linear time and uses bitmasks all over the place).

You can do this quickly with bitmasks: canhere=matchcurrow&((canprevrow<<1)|1). The problem is that you have 100 rows, and this won't fit in a long long => you have to split the 100 rows into 2 long longs.

Cho,

You have very nice idea but I have some doubts that this will give TLE. After you find the same hash as the patern you will need to do the slow compare to see if the matching is valid. For the test case that krijger mentioned (a lot of 'A's) this will give TLE. Do you do something else which I missed? Do you have AC?

Cho wrote:Let c[j] be the character of the shorter string, I define its hash value as:

Summation over all valid i,j: c[j] * (3 ^ (i*100+j)) mod 2^32

(x^y denotes x to the power y instead of bitwise-XOR.)

Are you sure you didn't mean, for example,

cAre you sure you didn't mean, for example,

c

*[j] * (32 ^ (i*100+j)) mod 2^32 ?*

The hash function you wrote will fail to return different values for such simple strings as "ab" and "da" (assuming a is coded as 0), so I can't believe you got AC doing that without later checking if the match is exact (in which case you should get TLE for cases where both the matrix and the pattern are full of a's, for instance).

I tried to use as a hash funtion the summation over all valid i, j of

cThe hash function you wrote will fail to return different values for such simple strings as "ab" and "da" (assuming a is coded as 0), so I can't believe you got AC doing that without later checking if the match is exact (in which case you should get TLE for cases where both the matrix and the pattern are full of a's, for instance).

I tried to use as a hash funtion the summation over all valid i, j of

c

*[j] * (32 ^(i * pattern width + j)) mod 1000000007,*

but I got WA after 9.7s, so even if this approach can be made to work I wonder how you managed to get it accepted in about 2.5 seconds.but I got WA after 9.7s, so even if this approach can be made to work I wonder how you managed to get it accepted in about 2.5 seconds.