250 - Pattern Matching Prelims

All about problems in Volume 2. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

250 - Pattern Matching Prelims

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

Post 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...
junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post 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. :)
zizi
New poster
Posts: 7
Joined: Fri Jan 30, 2004 4:51 am

Post 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?
junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post 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.
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post 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.
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post 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.
mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf »

Your output is correct.
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post 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 ?!
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

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

Post 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.
DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:

Post 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
algoJo
New poster
Posts: 37
Joined: Sun Dec 17, 2006 9:02 am

Why it always get WA...

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

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

Re: Why it always get WA...

Post 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
algoJo
New poster
Posts: 37
Joined: Sun Dec 17, 2006 9:02 am

Post 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...
Post Reply

Return to “Volume 2 (200-299)”