11019 - Matrix Matcher
Moderator: Board moderators
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 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];
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];
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.
Input format
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.
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.
Why fread? I read the input as follow:
scanf("%s", ...) is probably safer (many people here don't recommend gets at all). But gets should be faster.
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;
}
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
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.
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.
OK, yes, I could use other functions as well.
I just adapted the code from Cho:
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.
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;
}
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.
Internal Compiler Error on judge
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:
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.
We have a Solaris server with g++ with 2.95 and it gives this warning (and then hangs):
it compiles on UVa if you remove ={0} part (I don't know if it passes, I submitted it as 100)
Line 98 is11019.cpp:98: warning: aggregate has a partly bracketed initializer
11019.cpp:98: warning: aggregate has a partly bracketed initializer
Code: Select all
int mh[1024][1024][128] = {0};
-
- Guru
- Posts: 584
- Joined: Thu Jun 19, 2003 3:48 am
- Location: Sanok, Poland
- Contact: