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

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

Post by Robert Gerbicz »

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 

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

still WA

Post by zid_adrenalyns »

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

Post by gba356 »

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

ahmadfarid
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. :

Post by ahmadfarid »

please help please please please
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[10];
bool valid[10];
long x[8], y[8];
double minimum = 2147483647;
double total = 0;
long order[8];
long X[8], Y[8];
double Dis[8];

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

Post by Orgi »

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

Post by haaaz »

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[8];    
int n;
int list[8],ans[8];
double total;
double d[8][8];
bool used[8]={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
Location: University Of Dhaka,Bangladesh
Contact:

Re: 216 WA !!Plz Help

Post by Shafaet_du »

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
Location: Chittagong, Bangladesh

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

Post by @li_kuet »

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
Location: Chittagong, Bangladesh

Re: 216 WA !!Plz Help

Post by @li_kuet »

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

Post by brianfry713 »

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

Post by brianfry713 »

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

Post by Farsan »

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

Post by brianfry713 »

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!

Post Reply

Return to “Volume 2 (200-299)”