## 250 - Pattern Matching Prelims

Moderator: Board moderators

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

### 250 - Pattern Matching Prelims

Can anyone think of any weird input/output for this problem? As far as I can tell, it's a pretty straight forward counting problem, but I keep getting WA...
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
As always when dealing with floats/reals two things are important:
- precision (what datatype to use);
- comparison (equality of two numbers is defined within a margin of error).
Think about that. I only got AC on my third attempt...
junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am
Actually the problem was because the data set used to test was wrong... they fixed it and now I've got AC'ed. :p Forgot to delete the post though...

zizi
New poster
Posts: 7
Joined: Fri Jan 30, 2004 4:51 am
What's the correct data set for this problem . ??
I have another question ,can the i comlumn of the gravity be m and or j column be n?
junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am
zizi wrote:What's the correct data set for this problem . ??
I have another question ,can the i comlumn of the gravity be m and or j column be n?
I think the gravity column can be any of the valid columns.
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
Could somebody post some test cases ?
Are there any critical cases ?

I think I have no precision problems ( see the post from little joey )
and I always print the largest values of column and row in cases when
there is more than one gravity point.
But I keep getting WA.

Currently I can not find out where my BUG is.
Any help is welcome.
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
Could someone with an ACC program give me the answers
for the following input ( see below ):

INPUT

Code: Select all

``````5 5
0.1 0.2 0.1 0.2 0.1
0.1 0.2 0.3 0.1 0.1
0.2 0.3 0.1 0.1 0.3
0.4 0.1 0.1 0.1 0.2
0.2 0.2 0.3 0.3 0.1

5 10
0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1
0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2
0.3 0.3 0.3 0.3 0.3 0.3 0.3 0.3 0.3 0.3
0.4 0.4 0.4 0.4 0.4 0.4 0.4 0.4 0.4 0.4
0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.6

3 3
0.0 0.0 0.0
0.0 0.0 0.0
0.0 0.0 0.0

1 1
0.5

5 5
0.1 0.1 0.1 0.1 0.9
0.2 0.2 0.2 0.2 0.9
0.3 0.7 0.3 0.9 0.9
0.4 0.4 0.4 0.9 0.9
0.5 0.5 0.5 0.5 0.9

5 5
0.1 0.1 0.1 0.1 0.9
0.2 0.2 0.2 0.2 0.9
0.3 0.11 0.3 0.9 0.9
0.4 0.44 0.4 0.9 0.9
0.5 0.15 0.25 0.5 0.9

5 5
0.1 0.1 0.1 0.1 0.3
0.2 0.2 0.0002 0.2 0.2
0.3 0.12 0.3 0.9 0.1
0.4 0.4 0.4 0.9 0.9
0.5 0.5 0.5 0.5 0.9

5 5
0.1 0.1 0.1 0.1 0.6
0.2 0.2 0.2 0.2 0.004
0.3 0.7 0.3 0.2 0.1
0.4 0.4 0.4 0.9 0.1
0.5 0.5 0.5 0.5 0.1

5 5
0.1 0.1 0.1 0.1 0.9
0.2 0.2 0.2 0.3 0.9
0.3 0.17 0.3 0.4 0.9
0.4 0.14 0.4 0.1 0.9
0.5 0.5 0.15 0.5 0.99

10 10
0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1
0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1
0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1
0.1 0.1 0.1 0.2 0.1 0.1 0.1 0.1 0.1 0.1
0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1
0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1
0.77 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.99 0.1
0.1 0.88 0.1 0.1 0.77 0.1 0.1 0.1 0.1 0.1
0.1 0.1 0.66 0.1 0.17 0.1 0.1 0.9 0.1 0.00001
0.1 0.1 0.1 0.90 0.880 0.1 0.1 0.99 0.00001 0.222

0 0
``````
My WA program prints:

OUTPUT

Code: Select all

``````Case 1: center at (3, 3)
Case 2: center at (4, 6)
Case 3: center at (3, 3)
Case 4: center at (1, 1)
Case 5: center at (3, 4)
Case 6: center at (3, 4)
Case 7: center at (4, 4)
Case 8: center at (4, 3)
Case 9: center at (3, 4)
Case 10: center at (7, 5)
``````
mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
So my problem should be some stupid one...
Some boundary case or special chars in input ...
Who knows...

Actually this is worse as it is harder to fix.

Maybe I still have some logical BUG ?!
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
I rewrote my program in Java ( previously it was in C++ ) and
I made it more defensive with respect to input. And I got ACC.

Still I do not know why the C++ program gets WA and not ACC.

I mean I use only scanf () and not gets () which makes my program
automatically skip blank lines and so on. This way it also
DOES NOT assume that the format of a test case is :

cntRows(N) cntCols(M)
..................line 1 ( having M double numbers on it )
..................line 2 ( having M double numbers on it )
..................
..................line N ( having M double numbers on it )
<blank line>

So, despite the fact that my C++ program does not rely on
exactly such format of an input block ( test case ) it gets WA.
And I am sure the problem of my C++ program was somehow
input related.

I can see there're very few submissions for this problem and
there're also very few ACC programs. Is this due to I/O stuff ?
I mean, it is an easy problem with only about 150 ACC programs.
sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
The main reason for the low number of submissions is because this is a world finals problem and it is in volume 2.

I used C++ and have no problems with input/output.
DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:
I change variables' type from double to long double. And also calculate the difference from right to left, from bottom to top. My code is written in C++. It works well.
algoJo
New poster
Posts: 37
Joined: Sun Dec 17, 2006 9:02 am

### Why it always get WA...

Hi, I think this problem is straightforward, but it gives me multiple WA..., can anyone give me some hints? I'm very very curious bout this problem...
Thanks

Code: Select all

``````#include<stdlib.h>
#include<stdio.h>
#define MAX 26
#define INF 1000000000000

long double arr[MAX][MAX];
int Row,Col;
int ansR,ansC;
long double smallRow,smallCol;

void compute(int r,int c){
long double tempA,tempB,res,res2;
int i,j;
tempA=tempB=0;
for(i=r-1;i>=0;i--)
for(j=0;j<Col;j++) tempA+=arr[i][j];
for(i=r+1;i<Row;i++)
for(j=0;j<Col;j++) tempB+=arr[i][j];
if(tempA>tempB) res=tempA-tempB;
else res=tempB-tempA;
tempA=tempB=0;
for(i=0;i<Row;i++)
for(j=c-1;j>=0;j--) tempA+=arr[i][j];
for(i=0;i<Row;i++)
for(j=c+1;j<Col;j++) tempB+=arr[i][j];
if(tempA>tempB) res2=tempA-tempB;
else res2=tempB-tempA;
if(res2<=smallCol&&res<=smallRow)   {smallRow=res;smallCol=res2;ansR=r;ansC=c;}
}

void main(){
int r,c;
int i,j,no=0;
long double temp;

while(scanf("%d %d",&Row,&Col)==2)
{
if(!Row&&!Col) break;
++no;
smallRow=smallCol=INF;
for(i=0;i<Row;i++)
for(j=0;j<Col;j++)
{
scanf("%Lf",&temp);
arr[i][j]=temp;
}
for(i=0;i<Row;i++)
for(j=0;j<Col;j++)
compute(i,j);
printf("Case %d: center at (%d, %d)\n",no,ansR+1,ansC+1);
}
}

``````
helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### Re: Why it always get WA...

algoJo wrote:Hi, I think this problem is straightforward, but it gives me multiple WA..., can anyone give me some hints? I'm very very curious bout this problem...
Thanks

Code: Select all

``````   ...
if(res2<=smallCol&&res<=smallRow)   {smallRow=res;smallCol=res2;ansR=r;ansC=c;}
...
``````
Hmm.. I'm not sure if your WAs are caused by precision error..
But, when I compare 2 floating point numbers, I had to use EPS to get AC..
My data type is "double" and EPS value is 1e-6
algoJo
New poster
Posts: 37
Joined: Sun Dec 17, 2006 9:02 am
``````if(res2+1e-6<=smallCol+1e-6&&res+1e-6<=smallRow+1e-6)   {smallRow=res;smallCol=res2;ansR=r;ansC=c;}