216 - Getting in Line

All about problems in Volume 2. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

IMHO

Post by 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
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Post by 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
New poster
Posts: 4
Joined: Sun Jul 10, 2005 9:19 pm
Contact:

Help.

Post by 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
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Re: Help.

Post by asif_rahman0 »

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

Post by abhi »

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

Post by helloneo »

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

Post by hamedv »

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

Post by hamedv »

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

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am

Post by 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
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by 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
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am

Post by hamedv »

actually i did'nt read the problem statement
:oops:

zid_adrenalyns
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

Post by 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!
Making simple things simple, making complex things possible!!

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

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

Post by DP »

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

Post by 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
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

Post by zid_adrenalyns »

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

Post Reply

Return to “Volume 2 (200-299)”