## 216 - Getting in Line

Moderator: Board moderators

skinnyguy
New poster
Posts: 17
Joined: Fri Oct 22, 2004 3:41 pm

### IMHO

tell me if i'm wrong, but the problem is less comparable to either the MST or Shortest Path Algorithms and more comparable to the travelling salesperson problem.. which has no other way of perfectly solving it except a brute force

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm
First time i thought that it may be solved by MST but after some thinking i found that its totally impossible for MST to solve this problem.
Because in MST, you always taking minimum but not over all possible checking.
Such as, if you take a point then you dont take that point again for checking for more minimum than what you got. If you try that ... i hopefully can tell you are trying for Backtracking not MST.

Backtrack should be the solution.

And why it will go for "Shortest Path Algorithm" if there is an easy
algorithm(Backtracking)?

MajidIust
New poster
Posts: 4
Joined: Sun Jul 10, 2005 9:19 pm
Contact:

### Help.

ok for all test case in this place but get WA.
Help.

Code: Select all

``````#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#define MAXNODES 8
using namespace std;
class Node
{
public:
double x,y;
Node(){}
Node(double i,double j){x = i ; y = j;}
double getDist(Node a){return sqrt((x-a.x)*(x-a.x)+(y-a.y)*(y-a.y));}
};
class Wire
{
public:
int i,j;
double size;
Wire(){}
Wire(int I,int J,Node a,Node b){i = I ; j = J ; size = a.getDist(b)+16;}
};

Node N[MAXNODES];
Wire W[MAXNODES-1];
bool used[MAXNODES];
Wire best[MAXNODES-1];
double bestSize;
void solve(int index , int fav , double length , int last)
{
if(index == fav)
{
if(length < bestSize || bestSize == -1)
{
bestSize = length;
copy(W,W+fav,best);
}
return ;
}
for(int i=0;i<fav;i++)
{
if(!used[i])
{
used[i] = 1;

if(index > 0)
{
W[index-1]=Wire(last,i,N[last],N[i]);
solve(index+1,fav,length+W[index-1].size,i);
}
else
solve(index+1,fav,length,i);

used[i] = 0;
}
}
}
int main()
{
int n,m,k,t;
t = 0;
cin >> n;
while(n)
{
for(int i=0;i<n;i++)
cin >> N[i].x >> N[i].y;
memset(used,0,sizeof(used));
bestSize = -1;
solve(0,n,0,0);
cout << "**********************************************************"<<endl;
cout <<"Network #"<<++t<< endl;
for(int i=0;i<n-1;i++)
{
cout << "Cable requirement to connect (" << N[best[i].i].x << "," << N[best[i].i].y << ") to (" << N[best[i].j].x << "," << N[best[i].j].y << ") is ";
printf("%3.2lf",best[i].size);
cout <<" feet."<<endl;
}
printf("Number of feet of cable required is %3.2lf.\n",bestSize);
cin >> n;
}
return 0;
}``````

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

### Re: Help.

MajidIust wrote:ok for all test case in this place but get WA.
Help.

Code: Select all

``````.............
#include <stdio.h>
#define MAXNODES 8
using namespace std;
class Node
...................
``````
really..........!!!! Have you checked with my output...YET!!
You did the basic error. The highest limit is 8. So change it 9 or 10.

abhi
Learning poster
Posts: 94
Joined: Fri Nov 25, 2005 7:29 pm
why wa ????

Code: Select all

``````CODE DELETED AFTER AC :)

``````
Last edited by abhi on Tue Feb 20, 2007 6:56 pm, edited 1 time in total.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
Try to use double instead of float..
Sometimes it cause a precision error..

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am
what's the bug of my code

Code: Select all

``````GOT AC
``````
Last edited by hamedv on Sun Jul 22, 2007 2:18 pm, edited 1 time in total.

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am
it gives the output correct but gives the distance wrong??? hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am
finally i got AC
i changed my distance function
from

Code: Select all

``````double d(int x1, int y1, int x2, int y2)
{
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}``````
to

Code: Select all

``````double d(int x1, int y1, int x2, int y2)
{
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))+16;
}``````
why? i don't know
can anyone tell me [/code]

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
Read the problem statements carefully.. so the amount of cable used to join 2 adjacent computers on the network will be equal to the distance between the computers plus 16 additional feet of cable to connect from the floor to the computers and provide some slack for ease of installation.

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am
actually i did'nt read the problem statement New poster
Posts: 11
Joined: Thu Jun 15, 2006 5:46 pm
Location: Juchitán Oaxaca, México
Contact:

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

Usually I don't paste my code in forums, but ...whatelse...I try to solved it using brute force. This is my code. Someone can find the error?

Code: Select all

``````//216.getting in line (brute force)
//determine how the computers should be connected into such a chain to minimize the total amount of cable needed
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#define X 0
#define Y 1
using namespace std;

int pts;
int index[]={0,1,2,3,4,5,6,7};
int target;
double dist(int a[],int b[]){
return sqrt((a[X]-b[X])*(a[X]-b[X]) + (a[Y]-b[Y])*(a[Y]-b[Y])+16.0);
}
main(){
int n,i,casos=0;
double minimo,dist_total;
while (scanf ("%d\n",&n) && n){
for (i=0; i<n; i++)
scanf ("%d %d\n",&pts[i][X],&pts[i][Y]);
minimo=99999999;

do{
dist_total=0;
for (i=0; i<n-1; i++)
dist_total+= dist(pts[index[i]],pts[index[i+1]]);

if (dist_total < minimo){
minimo = dist_total;//guarda el orden
memcpy(target,index,sizeof(index));
}
}while (next_permutation(index,index+n));
printf ("**********************************************************\nNetwork #%d\n",++casos);
for (int i=0; i<n-1; i++){
printf ("Cable requirement to connect (%d,%d) to (%d,%d) is %3.2lf feet.\n",
pts[target[i]][X],pts[target[i]][Y],pts[target[i+1]][X],pts[target[i+1]][Y],
dist(pts[target[i]],pts[target[i+1]]));
}
printf ("Number of feet of cable required is %3.2lf.\n",minimo);
}
}

``````
thanks!
Making simple things simple, making complex things possible!!

DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Contact:

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

zid_adrenalyns wrote:Usually I don't paste my code in forums, but ...whatelse...I try to solved it using brute force. This is my code. Someone can find the error? Try Sample I/O.
Did you code yourself?

david.lenz
New poster
Posts: 1
Joined: Sun Sep 09, 2007 11:01 pm
Some help or thoughts here would be greatly appreciated. I've played with this on and off for a little bit and am stumped. I've run the posted sample input and have the same output. Am I missing something obvious?

Thanks

Code: Select all

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

int main()
{
int perm[] = {1,2,3,4,5,6,7,8};
int count;
int bestperm;
int computers;
double smallest = 0.0;
double current = 0.0;
double x, y;
int network = 1;
double chunk, total;

cin >> count;

while(count != 0)
{
current = 0.0;
smallest = 0.0;
total = 0.0;
chunk = 0.0;

for (int i = 0; i < count; i++)
{
cin >> computers[i] >> computers[i];
}

sort(perm, perm+count);     // gives the smallest permutation
do {
current = 0.0;

for(int i = 0; i < count - 1; i++)
{

x = computers[perm[i]-1] - computers[perm[i+1]-1];
y = computers[perm[i]-1] - computers[perm[i+1]-1];

current += sqrt(x*x + y*y);
}

if ((current < smallest) || (smallest == 0.0))
{

smallest = current;
for (int i = 0; i < count; i++)
{
bestperm[i] = perm[i];
}
}

} while (next_permutation(perm, perm+count));

cout << "**********************************************************\n"
<< "Network #" << network << "\n";
for (int i = 0; i < count - 1; i++)
{
cout << "Cable requirement to connect ("
<< computers[bestperm[i]-1] << "," << computers[bestperm[i]-1] << ") to ("
<< computers[bestperm[i+1]-1]<< "," << computers[bestperm[i+1]-1] << ") is ";
x = computers[bestperm[i]-1] - computers[bestperm[i+1]-1];
y = computers[bestperm[i]-1] - computers[bestperm[i+1]-1];
chunk = sqrt(x*x + y*y) + 16;
total += chunk;
cout.setf(ios::fixed);
cout << setprecision(2) <<  chunk << " feet.\n";

}

cout << "Number of feet of cable required is " << setprecision(2) << total << endl;
network++;

cin >> count;
}

return 0;
}
``````

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

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

DP wrote:
zid_adrenalyns wrote:Usually I don't paste my code in forums, but ...whatelse...I try to solved it using brute force. This is my code. Someone can find the error? Try Sample I/O.
Did you code yourself?
Actually, I have the same output for the samples posted. I like to know if there are some tricky input or some restriction that I don't see. Can someone post Sample I/O?
Making simple things simple, making complex things possible!!