Page 1 of 2

250 - Pattern Matching Prelims

Posted: Fri Jan 09, 2004 8:45 pm
by junbin
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...

Posted: Sat Jan 17, 2004 12:47 pm
by little joey
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...

Posted: Sun Jan 18, 2004 12:11 pm
by junbin
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...

Thanks for your help anyway. :)

Posted: Tue Feb 10, 2004 7:29 pm
by zizi
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?

Posted: Wed Feb 11, 2004 12:18 am
by junbin
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.

Posted: Thu Aug 04, 2005 9:50 pm
by Sedefcho
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.

Posted: Thu Aug 04, 2005 9:59 pm
by Sedefcho
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)
Thanks in advance.

Posted: Thu Aug 04, 2005 10:11 pm
by mf
Your output is correct.

Posted: Thu Aug 04, 2005 11:01 pm
by Sedefcho
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 ?!

Posted: Fri Aug 05, 2005 12:43 pm
by Sedefcho
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.

Posted: Sat Mar 25, 2006 10:27 am
by sclo
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.

Posted: Sun Mar 25, 2007 1:58 pm
by DJWS
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. :D

Why it always get WA...

Posted: Fri Jun 22, 2007 6:41 am
by algoJo
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 :D

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);
   }
}


Re: Why it always get WA...

Posted: Fri Jun 22, 2007 6:58 am
by helloneo
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 :D

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

Posted: Fri Jun 22, 2007 7:10 am
by algoJo
Thanks for replying helloneo.. :D
I still got WA :(
this is how I implement the EPS

Code: Select all

if(res2+1e-6<=smallCol+1e-6&&res+1e-6<=smallRow+1e-6)   {smallRow=res;smallCol=res2;ansR=r;ansC=c;}
is it rite?
hmm...., is there any tricky input on this problem...