11019 - Matrix Matcher

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

11019 - Matrix Matcher

Post by david »

What, exactly, is a "character" for this problem?
It seems there are characters not in the 'a'-'z' or 'A'-'Z' range.

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio »

What happen with this problem?
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?

krijger
New poster
Posts: 39
Joined: Wed Jul 21, 2004 12:35 am

Post by krijger »

During the actual contest, I got accepted with a program which assumes all characters are 'a'-'z'.

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).

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko »

Before I went back to sleep, I just tried reading the file in - it took 2.5secs with Java, so I just gave up.

Darko

andresw1
New poster
Posts: 27
Joined: Sat Mar 18, 2006 5:04 pm

Post by andresw1 »

Can you give some hint for this problem? I know that this can be solved with Aho-Corasik string matching algortihms but I don't know how or if there is simplier solution (like a number of KMPs)

krijger
New poster
Posts: 39
Joined: Wed Jul 21, 2004 12:35 am

Post by krijger »

I solved it with Aho-Corasik during the actual contest and I don't think a number of KMP's will be fast enough.

andresw1
New poster
Posts: 27
Joined: Sat Mar 18, 2006 5:04 pm

Post by andresw1 »

OK, so you build the tree, add special sign to the end of every row and run the algorithm. Then you get a matrix of lists... for every position you have a list which string starts there... what you do next? And how you do it fast:)

krijger
New poster
Posts: 39
Joined: Wed Jul 21, 2004 12:35 am

Post by krijger »

Well that's were I used bitmasks. The i-th row of the pattern can end at (x,y) in the matrix iff i==0 or the (i-1)-th row of the pattern can end at (x-1,y).

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.

andresw1
New poster
Posts: 27
Joined: Sat Mar 18, 2006 5:04 pm

Post by andresw1 »

Very nice... what if you don't use bitmasks. Will it give TLE?

krijger
New poster
Posts: 39
Joined: Wed Jul 21, 2004 12:35 am

Post by krijger »

I don't know. Haven't tried that. But if there are 'worst cases' in the jury-input (something like all A) I think it will.

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho »

I compute the hash value (long long multiplications involved) of the small pattern. Then preprocess the large text such that the hash value of each X by Y 2D-substring can be computed in constant time. I didn't optimize the code (and found no much room for optimization). It runs roughly 2.5 secs too.

aminallam
New poster
Posts: 39
Joined: Thu Dec 08, 2005 12:51 pm
Location: Suez, Egypt.

Post by aminallam »

Mr. Cho, can you give more insight for your hashing mechanism?
Thank you.

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho »

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.)

andresw1
New poster
Posts: 27
Joined: Sat Mar 18, 2006 5:04 pm

Post by andresw1 »

Hello,

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?

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

Post by david »

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,
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
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.

Post Reply

Return to “Volume 110 (11000-11099)”