216  Getting in Line
Moderator: Board moderators
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

 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)?
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)?
Help.
ok for all test case in this place but get WA.
Help.
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((xa.x)*(xa.x)+(ya.y)*(ya.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[MAXNODES1];
bool used[MAXNODES];
Wire best[MAXNODES1];
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[index1]=Wire(last,i,N[last],N[i]);
solve(index+1,fav,length+W[index1].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<n1;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;
}

 Experienced poster
 Posts: 209
 Joined: Sun Jan 16, 2005 6:22 pm
Re: Help.
really..........!!!! Have you checked with my output...YET!!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 ...................
You did the basic error. The highest limit is 8. So change it 9 or 10.
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.
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.
finally i got AC
i changed my distance function
from
to
why? i don't know
can anyone tell me [/code]
i changed my distance function
from
Code: Select all
double d(int x1, int y1, int x2, int y2)
{
return sqrt((x1x2)*(x1x2)+(y1y2)*(y1y2));
}
Code: Select all
double d(int x1, int y1, int x2, int y2)
{
return sqrt((x1x2)*(x1x2)+(y1y2)*(y1y2))+16;
}
can anyone tell me [/code]

 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?
thanks!
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[8][2];
int index[]={0,1,2,3,4,5,6,7};
int target[8];
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<n1; 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<n1; 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);
}
}
Making simple things simple, making complex things possible!!
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?

 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
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[8];
int computers[2][8];
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[0][i] >> computers[1][i];
}
sort(perm, perm+count); // gives the smallest permutation
do {
current = 0.0;
for(int i = 0; i < count  1; i++)
{
x = computers[0][perm[i]1]  computers[0][perm[i+1]1];
y = computers[1][perm[i]1]  computers[1][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[0][bestperm[i]1] << "," << computers[1][bestperm[i]1] << ") to ("
<< computers[0][bestperm[i+1]1]<< "," << computers[1][bestperm[i+1]1] << ") is ";
x = computers[0][bestperm[i]1]  computers[0][bestperm[i+1]1];
y = computers[1][bestperm[i]1]  computers[1][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
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?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?
Making simple things simple, making complex things possible!!