216 - Getting in Line

[skinnyguy]

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]

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]

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]

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]

why wa ????

Code: Select all

CODE DELETED AFTER AC :)

   

[helloneo]

Try to use double instead of float..
Sometimes it cause a precision error..

[hamedv]

what's the bug of my code

Code: Select all

GOT AC

[hamedv]

it gives the output correct but gives the distance wrong???

[hamedv]

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]

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]

actually i did'nt read the problem statement

[zid_adrenalyns]

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[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<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!

[DP]

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]

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[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;
}

[zid_adrenalyns]

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?