11019 - Matrix Matcher

[aminallam]

Also, I have used a small number (MOD=65529), so as to ensure that no overflow (using int) will occur (its square should fit in int). Is there a way to overcome this? I do not like to switch to long long computations as they are slow.

[sclo]

the trick of using unsigned int only works if the modulus is 2^32

[aminallam]

Can you help me further?
I used something like these (in most computations) and got AC:
hm2[j]=((hm2[i-1][j]+MOD-(hm1[i-x][j]*po[x-1])%MOD)*AS+hm1[j])%MOD;
where MOD = 65521
How can I convert it using this trick of unsigned int? I have tried removing %MOD, and +MOD, and making all numbers in unsigned int (to consider MOD=2^32), but I got WA.
I am sure this is not a problem of "probability" as I made further checks to ensure that pattern occurred. I think that this line in not true (assuming all vars in unsigned int):
hm2[j]=(hm2[i-1][j]-hm1[i-x][j]*po[x-1])*AS+hm1[j];

[sclo]

Can you help me further?
I used something like these (in most computations) and got AC:
hm2[j]=((hm2[i-1][j]+MOD-(hm1[i-x][j]*po[x-1])%MOD)*AS+hm1[j])%MOD;
where MOD = 65521
How can I convert it using this trick of unsigned int? I have tried removing %MOD, and +MOD, and making all numbers in unsigned int (to consider MOD=2^32), but I got WA.
I am sure this is not a problem of "probability" as I made further checks to ensure that pattern occurred. I think that this line in not true (assuming all vars in unsigned int):
hm2[j]=(hm2[i-1][j]-hm1[i-x][j]*po[x-1])*AS+hm1[j];

I got AC with using only unsigned ints, and I have similar lines in my code (the easiest way is to just do a search and replace and make all types unsigned)
for example in my code, I had:

Code: Select all

R[i][j+1] = (R[i][j]-M[i][j]*P[y-1])*27+M[i][j+y];
H[i+1][j] = (H[i][j]-R[i][j]*P[(x-1)*y])*P[y]+R[i+x][j];

I think you program might contain some other bugs too.
By the way, I hope there are no division anywhere in your code. You're not allowed to do any divisions, some of the divisions can mess up the computations. The reason is that 2^32 is not a prime.

[gagern]

I fear there is something wrong with the input.

I wrote a program that reads a whole matrix definition in one call to fread. But no matter if I assumed exactly one newline following the matrix size, or used gets to first read to the end of the line with the dimensions, or had scanf skip all whitsepace after the matrix size, every time the read data did not contain newlines where they should have been, or so my generated RE suggests.

It is difficult to write an efficient program if you cannot rely on the input format.

[Cho]

Why fread? I read the input as follow:

Code: Select all

#include <stdio.h>

char txt[1024][1024], ptn[1024][1024];

int main()
{
   int M, N, Y, X, T, i;
   
   for(scanf("%d", &T); T--; )
   {
      scanf("%d %d\n", &M, &N);
      for(i=0; i<M; gets(txt[i++]));
      scanf("%d %d\n", &Y, &X);
      for(i=0; i<Y; gets(ptn[i++]));

      // Compute and output the answer ...
   }
   
   return 0;
}

scanf("%s", ...) is probably safer (many people here don't recommend gets at all). But gets should be faster.

[little joey]

Maybe the input file was produced under MSDOS XP in which case a newline consists of 2 bytes?
If you use binary I/O in your programs, you're pretty much on your own. Even if you patch your program to read the particular format of the input file, there is a reasonable chance it will be updated in the future and have an other format next time.

I don't think there is a good reason to turn to hacking for this problem; I read all the input into their appropriate data structures using getchar(), isdigit() and islower() in 0.6 seconds, which leaves enough time to do the matching.

[gagern]

OK, yes, I could use other functions as well.
I just adapted the code from Cho:

Code: Select all

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char txt[1024][1024], ptn[1024][1024];

int main()
{
   int M, N, Y, X, T, i;
   int len, zero = 0, *nullpt = 0;
   
   for(scanf("%d", &T); T--; )
   {
      scanf("%d %d\n", &M, &N);
      for(i=0; i<M; ++i) {
	gets(txt[i]);
	len=strlen(txt[i]);
	if (len < N) abort();
	if (len > N) *nullpt ++;
      }
      scanf("%d %d\n", &Y, &X);
      for(i=0; i<Y; ++i) {
	gets(ptn[i]);
	len=strlen(ptn[i]);
	if (len < X) len /= zero;
	if (len > X) while (!zero);
      }

      // Compute and output the answer ...
   }
   
   return 0;
}

Result: Time Limit.
There is one line in the second matrix of some test case that is longer than it ought to be.

Yes, it could be a CR/LF pair, although it would be strange that only part of the input is affected.

I probably overjudged the time 1000 gets calls would take. My idea was that a thousand calls (one for each line) should be avoided when possible, but that seems not to bee a real issue here.

[PiM]

Please,does anyone has the programming code of the Problem H Matrix Matcher.I'm russian student and i need some help.If anyone has this code on C++ or С# please tell me about it.Thanks!

[Kevin]

For problem 11019:

I get:
g++: Internal compiler error: program as got fatal signal 25
from the judge.

It compiles correctly on my computer. Any ideas?

Thanks,

- Kevin

Edit: Solved, offending line:

Code: Select all

int mh[1024][1024][128] = {0};

[Darko]

We have a Solaris server with g++ with 2.95 and it gives this warning (and then hangs):

11019.cpp:98: warning: aggregate has a partly bracketed initializer
11019.cpp:98: warning: aggregate has a partly bracketed initializer

Line 98 is

Code: Select all

int mh[1024][1024][128] = {0};

it compiles on UVa if you remove ={0} part (I don't know if it passes, I submitted it as 100)

[Krzysztof Duleba]

Well, my guess is that a program allocating over 500MB of memory has very slim chances of passing.

[Darko]

Good thing I never tried to run it - I never thought about it

I just found it interesting that our server has a compiler that is older than UVa's (it is 2.95.3) - and that it actually can be useful for something.

[Kevin]

Thanks guys, I should have seen that.

Looks like I have a few things to speed up other than that.