## 216 - Getting in Line

Moderator: Board moderators

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

### Re: I used brute force for this problem, but always have get

zid_adrenalyns wrote: Actually, I have the same output for the samples posted.
I don't think that.
For example this line is wrong:

Code: Select all

``return sqrt((a[X]-b[X])*(a[X]-b[X]) + (a[Y]-b[Y])*(a[Y]-b[Y])+16.0);``
because the cabel is longer by 16 feets than the distance of the two points, so it should be:

Code: Select all

``return sqrt((a[X]-b[X])*(a[X]-b[X]) + (a[Y]-b[Y])*(a[Y]-b[Y]))+16.0;``
There can be some other errors also.
And your program is little ugly, I would never write this:

Code: Select all

``````#define X 0
#define Y 1 ``````

New poster
Posts: 11
Joined: Thu Jun 15, 2006 5:46 pm
Location: Juchitán Oaxaca, México
Contact:

### still WA

Robert Gerbicz wrote:
zid_adrenalyns wrote: Actually, I have the same output for the samples posted.
I don't think that.
For example this line is wrong:

Code: Select all

``return sqrt((a[X]-b[X])*(a[X]-b[X]) + (a[Y]-b[Y])*(a[Y]-b[Y])+16.0);``
because the cabel is longer by 16 feets than the distance of the two points, so it should be:

Code: Select all

``return sqrt((a[X]-b[X])*(a[X]-b[X]) + (a[Y]-b[Y])*(a[Y]-b[Y]))+16.0;``
U r right!, I made a terrible mistake, but I have fixed that in my last submition (before the last post).
And your program is little ugly, I would never write this:

Code: Select all

``````#define X 0
#define Y 1 ``````
About the code post below, U can chage this lines for enum{X,Y}; I think this is irrelevant.
There can be some other errors also.
Are u find them? Please tell me.
Making simple things simple, making complex things possible!!

gba356
New poster
Posts: 15
Joined: Sat Apr 28, 2007 10:12 am
Location: Taiwan
I tried to solve the problem with DFS and some branch and bound, but it keeps give me WA.

Could somebody help me?

Code: Select all

``````#include<iostream>
#include<math.h>
#define N 10
#define INF 214748647
#define Dist(i,j) sqrt( (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]) )
using namespace std;

int n,x[N],y[N];
int visit[N]={0},path[N],minpath[N];
double mindist,dist[N][N];

inline void
DFS(int start,int depth,double tempdist)
{
path[depth-1]=start;
if( tempdist>=mindist )return;
if( depth==n&&tempdist<mindist )
{
for(int i=0;i<n;i++)
minpath[i]=path[i];
mindist=tempdist;
return;
}
for(int i=0;i<n;i++)  /* DFS */
if( !visit[i] )
{
visit[i]=1;
DFS(i,depth+1,tempdist+dist[start][i]);
visit[i]=0;
}
}

int main()
{
//    freopen("216.in","r",stdin);
//    freopen("216.out","w",stdout);
cout.setf(ios::fixed);
cout.precision(2);
int case_n=0;
while( cin>>n,n )
{
mindist=INF;
for(int i=0;i<n;i++)
cin>>x[i]>>y[i];
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
dist[i][j]=dist[j][i]=Dist(i,j);
for(int i=0;i<n;i++)
DFS(i,0,0);
cout<<"**********************************************************"<<endl;
cout<<"Network #"<<++case_n<<endl;

for(int i=0;i<n-1;i++)
cout<<"Cable requirement to connect ("<<x[minpath[i]]<<","
<<y[minpath[i]]<<") to ("<<x[minpath[i+1]]<<","<<y[minpath[i+1]]<<") is "
<<dist[minpath[i]][minpath[i+1]]+16<<" feet."<<endl;
cout<<"Number of feet of cable required is "<<mindist+16*(n-1)<<"."<<endl;
}
}
``````

New poster
Posts: 6
Joined: Sun Apr 23, 2006 5:47 pm
Location: Cairo
Contact:

### i tried all the sample I/O but still getting wrong answer. :

i tried all the sample I/O but still getting wrong answer. :'(

[/code]#include <iostream>
#include <fstream>
#include <cmath>
#include <iomanip>
using namespace std;

//ifstream in ("input.txt");
//ofstream out ("output.txt");

long n;
long path;
bool valid;
long x, y;
double minimum = 2147483647;
double total = 0;
long order;
long X, Y;
double Dis;

void Display()
{
long i;
total = 0;
for(i=0; i<n-1; i++)
{
// out << path << " ";
double xdif, ydif;
xdif = x[path[i+1]] - x[path];
ydif = y[path[i+1]] - y[path];

total += (16+sqrt(pow(double(ydif),2.0)+pow(double(xdif),2.0)));

}

// out << "\t" << total << endl;
if(minimum>total)
{
minimum = total;
for(i=0; i<n; i++)
{
double xdif = x[path[i+1]] - x[path];
double ydif = y[path[i+1]] - y[path];
X = x[path];
Y = y[path];
Dis = (16+sqrt(pow(double(ydif),2.0)+pow(double(xdif),2.0)));
}

}

}

void Permutation(long counter)
{
if(counter == n)
{
total = 0;
Display();
return;
}
long i;
for(i=0; i<n; i++)
{
if(valid[i])
{
valid[i] = false;
path[counter] = i;
Permutation(counter+1);
valid[i] = true;
}
}
}

int main()
{
long counterr = 0;

while (cin >> n)
{
if (n==0)
break;

for (long i=0; i<n; i++)
cin >> x[i] >> y[i];

for(long i=0; i<n; i++)
valid[i] = true;

Permutation(0);
Display();

//if (counterr!=0)
cout<<"**********************************************************"<<endl;
cout << "Network #" << ++counterr << endl;

for (long i=0; i<n-1; i++)
{
double xdif = X[i] - X[i+1];
double ydif = Y[i] - Y[i+1];
cout << "Cable requirement to connect (" << X[i] << "," << Y[i] << ") to (" << X[i+1] << "," << Y[i+1] << ") is ";
cout << setiosflags(ios::fixed) << setiosflags(ios::showpoint) << setprecision(2) << Dis[i] << " feet.\n";
}
cout << "Number of feet of cable required is ";
cout << setiosflags(ios::fixed) << setiosflags(ios::showpoint) << setprecision(2) << minimum << "." << endl;

minimum = 2147483647;
total = 0;

}
return 0;
}

Orgi
New poster
Posts: 11
Joined: Mon Oct 29, 2001 2:00 am
Location: Bulgaria
Can anybody supply some test cases for 216?
Please, if someone has AC on C or C++, i'd like to know how he/she copes with rounding errors?

haaaz
New poster
Posts: 29
Joined: Sun Sep 08, 2002 8:02 am
I am also getting WA on the new server when I tried to resubmit codes I wrote long time ago... I have tried all sample inputs I found in this forum and I think my program gives the correct outputs.

I am just using DFS brute force....

AND most importantly my code got accepted a few years ago on the old server!!! can anybody help?

Code: Select all

``````//p216 Getting in Line

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;

const double INF=999999999999.0;
struct com {
int x,y;
};
com comlist;
int n;
int list,ans;
double total;
double d;
bool used={false};
double dist(com a, com b) {
return sqrt(double(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y))+16;
}

void p(int depth) {
if (depth==n) {
//caluculate distance
double t=0;
for (int i=1; i<n; i++) t+= d[ list[i-1] ][ list[i] ];
if (t<total) {
total=t;
for (int i=0; i<n; i++) ans[i]=list[i];
}
return;
}
for (int i=0; i<n; i++) {
if (used[i]) continue;
list[depth]=i;
used[i]=true;
p(depth+1);
used[i]=false;
}
}

int main() {
com x;
int test=1;
cout.setf(ios::fixed);
cout.precision(2);
while (cin >> n) {
if (n==0) break;
total=INF;
cout << "**********************************************************\n"
<< "Network #" << test << '\n';

for (int i=0; i<n; i++) {
list[i]=i;
cin >> x.x >> x.y;
comlist[i]=x;
}
for (int i=0; i<n; i++)
for (int j=0; j<n; j++) d[i][j]=dist(comlist[i],comlist[j]);
p(0);
for (int i=1; i<n; i++) {
cout << "Cable requirement to connect (" << comlist[ans[i-1]].x << "," << comlist[ans[i-1]].y
<< ") to (" << comlist[ans[i]].x << "," << comlist[ans[i]].y << ") is " << d[ans[i-1]][ans[i]] << " feet.\n";
}
cout << "Number of feet of cable required is " << total << ".\n";
test++;
}
return 0;
}        ``````
[/code]

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Contact:

### Re: 216 WA !!Plz Help

Try this cases:

Code: Select all

``````8
100 150
102 23
34 67
32 63
11 25
132 35
54 122
54 23
8
120 15
102 21
34 64
132 16
1 125
13 135
12 162
55 45
0``````
output:

Code: Select all

``````**********************************************************
Network #1
Cable requirement to connect (132,35) to (102,23) is 48.31 feet.
Cable requirement to connect (102,23) to (54,23) is 64.00 feet.
Cable requirement to connect (54,23) to (11,25) is 59.05 feet.
Cable requirement to connect (11,25) to (32,63) is 59.42 feet.
Cable requirement to connect (32,63) to (34,67) is 20.47 feet.
Cable requirement to connect (34,67) to (54,122) is 74.52 feet.
Cable requirement to connect (54,122) to (100,150) is 69.85 feet.
Number of feet of cable required is 395.62.
**********************************************************
Network #2
Cable requirement to connect (132,16) to (120,15) is 28.04 feet.
Cable requirement to connect (120,15) to (102,21) is 34.97 feet.
Cable requirement to connect (102,21) to (55,45) is 68.77 feet.
Cable requirement to connect (55,45) to (34,64) is 44.32 feet.
Cable requirement to connect (34,64) to (1,125) is 85.35 feet.
Cable requirement to connect (1,125) to (13,135) is 31.62 feet.
Cable requirement to connect (13,135) to (12,162) is 43.02 feet.
Number of feet of cable required is 336.10.
``````
no need to use eps

@li_kuet
New poster
Posts: 44
Joined: Fri May 25, 2012 6:22 pm

### Re: 216(Getting in Line )------->Long Time Wrong Answer

I have tried all the test case from the forum but Can't find out the bug   I used bitmask+dp to solve the problem.
please help  Last edited by @li_kuet on Tue Jun 19, 2012 12:42 am, edited 1 time in total.

@li_kuet
New poster
Posts: 44
Joined: Fri May 25, 2012 6:22 pm

### Re: 216 WA !!Plz Help

I have tried all the test case from the forum but Can't find out the bug   I used bitmask+dp to solve the problem.
please help  Code: Select all

``````Removed after AC :D :D
``````
Last edited by @li_kuet on Tue Jun 19, 2012 5:25 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 216 WA !!Plz Help

Input:

Code: Select all

``````3
8 16
8 11
9 16
0``````
AC output:

Code: Select all

``````**********************************************************
Network #1
Cable requirement to connect (8,11) to (8,16) is 21.00 feet.
Cable requirement to connect (8,16) to (9,16) is 17.00 feet.
Number of feet of cable required is 38.00.``````
Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 216(Getting in Line )------->Long Time Wrong Answer

Check input and AC output for thousands of problems on uDebug!

Farsan
New poster
Posts: 34
Joined: Fri Aug 12, 2011 6:37 am

### Re: 216 - Getting in Line

MST should not work here because every node (except terminal nodes) must have exactly 2 edges but in mst any node can have any number of edges connected with it...

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 216 - Getting in Line

Don't find the MST. Each network has at least 2 and at most 8 computers. Use a brute force algorithm.
Check input and AC output for thousands of problems on uDebug!