A contest problem.. where am i wrong??
From: Bhaskara Aditya (bhaskaraaditya_at_msn.com)
Date: 02/29/04
- Next message: Calum: "Re: Arthur O'Dwyer on the feasibility of simulating a Turing Machine"
- Previous message: Michael Mendelsohn: "Re: Fast pancake flipping"
- Next in thread: Ian Woods: "Re: A contest problem.. where am i wrong??"
- Reply: Ian Woods: "Re: A contest problem.. where am i wrong??"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: 29 Feb 2004 05:19:43 -0800
Hi everyone, I've been trying to solve the foll problem :
Cow Tours
Farmer John has a number of pastures on his farm. Cow paths connect
some pastures with certain other pastures, forming a field. But,at the
present time, you can find at least two pastures that cannot be
connected by any sequence of cow paths, thus partitioning Farmer
John's farm into multiple fields.
Farmer John would like add a single a cow path between one pair of
pastures using the constraints below.
A field's `diameter' is defined to be the largest distance of all the
shortest walks between any pair of pastures in the field. Consider the
field below with five pastures, located at the points shown, and cow
paths marked by lines:
15,15 20,15
D E
*-------*
| _/|
| _/ |
| _/ |
|/ |
*--------*-------*
A B C
10,10 15,10 20,10
The `diameter' of this field is approximately 12.07106, since the
longest of the set of shortest paths between pairs of pastures is the
path from A to E (which includes the point set {A,B,E}). No other pair
of pastures in this field is farther apart when connected by an
optimal sequence of cow paths.
Suppose another field on the same plane is connected by cow paths as
follows:
*F 30,15
/
_/
_/
/
*------
G H
25,10 30,10
In the scenario of just two fields on his farm, Farmer John would add
a cow path between a point in each of these two fields (namely point
sets {A,B,C,D,E} and {F,G,H}) so that the joined set of pastures
{A,B,C,D,E,F,G,H} has the smallest possible diameter.
Note that cow paths do not connect just because they cross each other;
they only connect at listed points.
The input contains the pastures, their locations, and a symmetric
"adjacency" matrix that tells whether pastures are connected by cow
paths. Pastures are not considered to be connected to themselves.
Here's one annotated adjacency list for the pasture {A,B,C,D,E,F,G,H}
as shown above:
A B C D E F G H
A 0 1 0 0 0 0 0 0
B 1 0 1 1 1 0 0 0
C 0 1 0 0 1 0 0 0
D 0 1 0 0 1 0 0 0
E 0 1 1 1 0 0 0 0
F 0 0 0 0 0 0 1 0
G 0 0 0 0 0 1 0 1
H 0 0 0 0 0 0 1 0
Other equivalent adjacency lists might permute the rows and columns by
using some order other than alphabetical to show the point
connections. The input data contains no names for the points.
The input will contain at least two pastures that are not connected by
any sequence of cow paths.
Find a way to connect exactly two pastures in the input with a cow
path so that the new combined field has the smallest possible diameter
of any possible pair of connected pastures. Output that smallest
possible diameter.
PROGRAM NAME: cowtour
INPUT FORMAT
Line 1: An integer, N (1 <= N <= 150), the number of pastures
Line 2-N+1: Two integers, X and Y (0 <= X ,Y<= 100000), that denote
that X,Y grid location of the pastures; all input pastures are unique.
Line N+2-2*N+1: lines, each containing N digits (0 or 1) that
represent the adjacency matrix as described above, where the rows' and
columns' indices are in order of the points just listed.
SAMPLE INPUT (file cowtour.in)
8
10 10
15 10
20 10
15 15
20 15
30 15
25 10
30 10
01000000
10111000
01001000
01001000
01110000
00000010
00000101
00000010
OUTPUT FORMAT
The output consists of a single line with the diameter of the newly
joined pastures. Print the answer to exactly six decimal places. Do
not perform any special rounding on your output.
SAMPLE OUTPUT (file cowtour.out)
22.071068
------------------
I've done as follows: I find the "diameter wrt every vertex --
diam[v]", the length of the longest path with starting point as that
vertex. Then, we check every pair of unconnected vertices a, b and
compute diam[a]+diam[b]+dist[a,b]. Let the least of these be min. Now,
i'll find the maximum of min and diam[v1], diam[v2], .. , diam[v_n].
This gives what is required. (the diam's are the previously computed
ones). The program works for the first 6 testcases.. but fails for the
7th. I think the problem is with computing the diam[v] since in the
current testcase, there are vertices with initial diam[v]>reqd answer.
I basically find the diam[v] using somewhat usual procedure.. and
that's why i dont know where i'm wrong. Can someone explain?? I have
included the code below :
#include <iostream.h>
#include <fstream.h>
#include <math.h>
short int nbrlist[150][150]; /* list of neighbours */
short int nofnbrs[150]={0}; /* no. of neighbours */
int x[150], y[150];
int N;
long double diam[150];
long double dist[150][150];
long double mindist[150][150];
ifstream fin("cowtour.in");
ofstream fout("cowtour.out");
void getdists()
{
int i, j;
for(i=0; i<N; i++)
{
for(j=0; j<N; j++)
{
dist[i][j]=sqrt(((x[i]-x[j])*(x[i]-x[j]))+((y[i]-y[j])*(y[i]-y[j])));
}
}
}
void getdiams()
{
int i=0, count, j, stno=0, k, prevno;
int stack0[150], stack1[150];
for(i=0; i<N; i++)
{
bool visited[150]={0};
stno=0;
diam[i]=0; visited[i]=1;
count=1; stack0[0]=i; mindist[i][i]=0;
while(count>0)
{
prevno=count;
count=0;
k=0;
if(stno==0)
{
for(j=0; j<prevno; j++)
{
for(k=0; k<nofnbrs[stack0[j]]; k++)
{
if(visited[nbrlist[stack0[j]][k]]==0)
{
visited[nbrlist[stack0[j]][k]]=1;
mindist[i][nbrlist[stack0[j]][k]]=mindist[i][stack0[j]]+dist[stack0[j]][nbrlist[stack0[j]][k]];
if(mindist[i][nbrlist[stack0[j]][k]]>diam[i])
diam[i]=mindist[i][nbrlist[stack0[j]][k]];
stack1[count]=nbrlist[stack0[j]][k];
count++;
}
}
}
stno=1;
}
else if(stno==1)
{
for(j=0; j<prevno; j++)
{
for(k=0; k<nofnbrs[stack1[j]]; k++)
{
if(visited[nbrlist[stack1[j]][k]]==0)
{
visited[nbrlist[stack1[j]][k]]=1;
mindist[i][nbrlist[stack1[j]][k]]=mindist[i][stack1[j]]+dist[stack1[j]][nbrlist[stack1[j]][k]];
if(mindist[i][nbrlist[stack1[j]][k]]>diam[i])
diam[i]=mindist[i][nbrlist[stack1[j]][k]];
stack0[count]=nbrlist[stack1[j]][k];
count++;
}
}
}
stno=0;
}
}
}
}
void printans(long double min)
{
double intpart, fracpart;
fracpart=modf(min, &intpart);
fout << intpart << ".";
for(int i=0; i<5; i++)
{
fracpart=fracpart*10;
fracpart=modf(fracpart, &intpart);
fout << intpart;
}
fracpart=fracpart*10;
fracpart=modf(fracpart, &intpart);
if(fracpart>0.5) intpart++;
fout << intpart << "\n";
}
int main()
{
int i, j;
char temp;
for(i=0; i<150; i++)
{
for(j=0; j<150; j++)
{
mindist[i][j]=-1;
}
}
fin >> N;
for(i=0; i<N; i++)
{
fin >> x[i] >> y[i];
}
temp=fin.get();
for(i=0; i<N; i++)
{
for(j=0; j<N; j++)
{
temp=fin.get();
if(int(temp)==49) {nbrlist[i][nofnbrs[i]]=j; nofnbrs[i]++;}
}
temp=fin.get();
}
// cout << "inpt complete " << nofnbrs[1] << " " << nofnbrs[2] <<
endl;
getdists();
getdiams();
// for(i=0; i<N; i++)
// {
// cout << i << " --> " << diam[i] << endl;
// }
long double min=999999999, tempor;
for(i=0; i<N; i++)
{
for(j=0; j<N; j++)
{
if(mindist[i][j]==-1)
{
tempor=diam[i]+diam[j]+dist[i][j];
if(tempor<min) min=tempor;
}
}
}
for(i=0; i<N; i++)
{
if(diam[i]>min) min=diam[i];
}
printans(min);
fin.close();
fout.close();
return 0;
}
- Next message: Calum: "Re: Arthur O'Dwyer on the feasibility of simulating a Turing Machine"
- Previous message: Michael Mendelsohn: "Re: Fast pancake flipping"
- Next in thread: Ian Woods: "Re: A contest problem.. where am i wrong??"
- Reply: Ian Woods: "Re: A contest problem.. where am i wrong??"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
