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

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

Post by 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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

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

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

Post by 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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

aminallam wrote: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
New poster
Posts: 7
Joined: Thu Mar 11, 2004 5:37 pm

Input format

Post by 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
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by 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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by 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
New poster
Posts: 7
Joined: Thu Mar 11, 2004 5:37 pm

Post by 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
New poster
Posts: 2
Joined: Fri Dec 08, 2006 11:33 pm

Post by 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
New poster
Posts: 7
Joined: Tue Oct 24, 2006 2:14 am

Internal Compiler Error on judge

Post by 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};

Last edited by Kevin on Tue Feb 27, 2007 6:32 pm, edited 1 time in total.

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

Post by 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
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba »

Well, my guess is that a program allocating over 500MB of memory has very slim chances of passing.
For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...

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

Post by 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
New poster
Posts: 7
Joined: Tue Oct 24, 2006 2:14 am

Post by Kevin »

Thanks guys, I should have seen that.

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

Post Reply

Return to “Volume 110 (11000-11099)”