250 - Pattern Matching Prelims

[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...

[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...

[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.

[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?

[junbin]

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]

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]

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.

[mf]

Your output is correct.

[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 ?!

[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.

[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.

[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.

[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

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]

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]

Thanks for replying helloneo..
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...