216 - Getting in Line

[C8H10N4O2]

Works for all test cases. WAs! Please help. Thanks!
[cpp]#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

double df(double a,double b)
{
return sqrt(a*a+b*b);
}

void main()
{
int i,j,N,z;
vector<vector<double> > dist;
vector<pair<int,int> > points;
vector<int> enumeration,ShortestPath;
double Shortest,Current;

z=0;

while(scanf("%d",&N)!=EOF&&N>0)
{
z++;
dist=vector<vector<double> >(N,vector<double>(N,0));
points.resize(N);
enumeration.clear();
Shortest=100000;
for(i=0;i<N;i++)
{
scanf("%d%d",&points.first,&points.second);
}
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
if(i!=j)
{
dist[j]=df(points.first-points[j].first,points.second-points[j].second)+16;
}
}
}
for(i=0;i<N;i++)
{
enumeration.push_back(i);
}
do
{
Current=0;
for(i=1;i<N;i++)
{
Current+=dist[enumeration[i-1]][enumeration];
}
if(Current<Shortest)
{
Shortest=Current;
ShortestPath=enumeration;
}
}
while(next_permutation(enumeration.begin(),enumeration.end()));
printf("**********************************************************\n");
printf("Network #%d\n",z);
for(i=1;i<N;i++)
{
printf("Cable requirement to connect (%d,%d) to (%d,%d) is %3.2lf feet.\n",points[ShortestPath[i-1]].first,points[ShortestPath[i-1]].second,points[ShortestPath].first,points[ShortestPath].second,dist[ShortestPath[i-1]][ShortestPath]);
}
printf("Number of feet of cable required is %3.2lf.\n",Shortest);
}
}[/cpp]

[ei01036]

i'm having the same problem...
if anyone knows of something that could help, pls post!

[Dominik Michniewski]

I've got Acc on this problem, but with time circa 0.5 sec ...
Could anyone help me and tell how can I improve this time ?? I use brute force, because I don't know any other method ...

Best regards
DM

[UFP2161]

RE: C8H10N4O2's code

Not sure if the board did this or not or if that is how the code is actually formatted, but remove the carriage return between "Cable requirement... %3.2lf" and the next line "feet" and add a space in between.

Otherwise, I don't see anything wrong with your code. I randomly generated 10,000 test cases and checked it against my AC code, and there is no difference between the two outputs after the above change.

RE: Optimizing

I have 0.040s, which is fast, but not the fastest for this problem. The only real optimization I do is, do the permutations myself instead of using C++'s next_permutation function, which allows me to prune the tree whenever the current distance of the links is greater than any minimum I've already found.

[oriol78]

first of all sorry about my english ..

well, i try to solve this problem using the next permutation funcion too, but judge always rpelies me WA and i can't see my mistake, can anybody help me plz? thx a lot

[cpp]

#include <iostream>
#include <vector>
#include <utility>
#include <math.h>
#include <map>
#include <stdio.h>
#include <algorithm>
using namespace std;

long double dist2(pair<int,int> x, pair<int,int> y)
{
return sqrt(((x.first-y.first)*(x.first-y.first))+((x.second-y.second)*(x.second-y.second)));
}

long double dist(vector<pair<int,int> > v)
{
if(v.size() < 2)
return 0;
long double totalDist = 0;
for(int i = 0; i < v.size()-1; i++)
totalDist += dist2(v,v[i+1]);
return totalDist;
}

vector<pair<int,int> > SP(vector<pair<int,int> > points)
{
vector<pair<int,int> > res;
long double min = 1000000000, minAux;
if(points.size() == 2)
return points;
while(next_permutation(points.begin(),points.end()))
{
minAux = dist(points);
if(minAux < min)
{
res = points;
min = minAux;
}
}
return res;
}

void output(vector<pair<int,int> > shortestPath, int _case)
{
long double totalDist = 0 ;
cout << "**********************************************************" << endl;
cout << "Network #" << _case << endl;
for(int i = 0; i < shortestPath.size()-1; i++)
{
long double aux = dist2(shortestPath,shortestPath[i+1])+16;
cout << "Cable requirement to connect ("
<< shortestPath.first << "," << shortestPath.second << ") to ("
<< shortestPath[i+1].first << "," << shortestPath[i+1].second << " ) is " ;
printf("%.2f",aux);
cout << " feet." << endl;
totalDist += aux;
}
printf("Number of feet of cable required is %.2f.\n",totalDist);
}

void proces(vector<pair<int,int> > points, int _case)
{
vector<pair<int,int> > shortestPath;
shortestPath = SP(points);
output(shortestPath, _case);
}

int main()
{
int numPoints, _case = 1;
cin >> numPoints;
while(numPoints != 0)
{
vector<pair<int,int> > points(numPoints);
for(int i = 0; i < numPoints; i++)
cin >> points.first >> points.second;
proces(points, _case++);
cin >> numPoints;
}
return 0;
}
[/cpp]

[Per]

Oriol:

Input:

Code: Select all

6
111 84
55 28
43 116
38 101
28 62
5 19

Output as in first sample input case (i.e. 305.45 feet).

[oriol78]

well,
first i must sort the points, thx, but i'm WA again, can anybody test again my code?
[cpp]

#include <iostream>
#include <vector>
#include <utility>
#include <math.h>
#include <map>
#include <stdio.h>
#include <algorithm>
using namespace std;

long double dist2(pair<int,int> x, pair<int,int> y)
{
return sqrt(((x.first-y.first)*(x.first-y.first))+((x.second-y.second)*(x.second-y.second)));
}

long double dist(vector<pair<int,int> > v)
{
if(v.size() < 2)
return 0;
long double totalDist = 0;
for(int i = 0; i < v.size()-1; i++)
totalDist += dist2(v,v[i+1]);
return totalDist;
}

vector<pair<int,int> > SP(vector<pair<int,int> > points)
{
vector<pair<int,int> > res;
long double min = 1000000000, minAux;
sort(points.begin(),points.end());
min = dist(points);
res = points;
while(next_permutation(points.begin(),points.end()))
{
minAux = dist(points);
if(minAux < min)
{
res = points;
min = minAux;
}
}
return res;
}

void output(vector<pair<int,int> > shortestPath, int _case)
{
long double totalDist = 0 ;
cout << "**********************************************************" << endl;
cout << "Network #" << _case << endl;
for(int i = 0; i < shortestPath.size()-1; i++)
{
long double aux = dist2(shortestPath,shortestPath[i+1])+16;
cout << "Cable requirement to connect ("
<< shortestPath.first << "," << shortestPath.second << ") to ("
<< shortestPath[i+1].first << "," << shortestPath[i+1].second << ") is " ;
printf("%.2f",aux);
cout << " feet." << endl;
}
totalDist = dist(shortestPath) + (16*(shortestPath.size()-1));
printf("Number of feet of cable required is %.2f.\n",totalDist);
}

void proces(vector<pair<int,int> > points, int _case)
{
vector<pair<int,int> > shortestPath;
shortestPath = SP(points);
output(shortestPath, _case);
}

int main()
{
int numPoints, _case = 1;
cin >> numPoints;
while(numPoints != 0)
{
vector<pair<int,int> > points(numPoints);
for(int i = 0; i < numPoints; i++)
cin >> points.first >> points.second;
proces(points, _case++);
cin >> numPoints;
}
return 0;
}
[/cpp]

[pavelph]

Sorry, I haven`t ACC for this problem and I can`t understand smth: for
input

Code: Select all

6 
111 84 
55 28 
43 116 
38 101 
28 62 
5 19
0

answer will be
output

Code: Select all

**********************************************************
Network #5
Cable requirement to connect (111,84) to (43,116) is 91.15 feet.
Cable requirement to connect (43,116) to (38,101) is 31.81 feet.
Cable requirement to connect (38,101) to (28,62) is 56.26 feet.
Cable requirement to connect (28,62) to (55,28) is 59.42 feet.
Cable requirement to connect (55,28) to (5,19) is 66.80 feet.
Number of feet of cable required is 305.45.

, not "as in first sample input case". Help me please!!!

[pavelph]

I read on the list of problems that 216 has Special Judge. What does it mean? Here my code, that works on all inputs, but getting me WA.
[pascal]{CODE CUT}[/pascal]

[Tahseen Mohammad]

In a normal problem there is only one solution to a specific input.
So the judge simply creates two output from the judge input.
It then compares the two files. If the files matches then you get
AC, WA otherwise.

A special judge means that for a specific input there are multiple
valid solutions and any one of them will do. So the judge program
get your output for the judge input. But it does not compare it with
judge output rather it reads in your output and check for consistency
of your output against the input. If the output is consistent then you get
AC, WA otherwise.

What it really means that don't worry if your output don't exactly match
with judge output/sample output. You will get AC as long as it is correct.

Right now I don't have time to go through with your code. As soon as I'm
free I will look into it for error.

Sorry for such long explanation. I can't seem to explain things in short
like others do.

[pavelph]

Thank you.
I`m found my mistake: I didn`t understood condition of problem. I thougth that first computer fixed.
Now I got AC!!! Thanks.

[IBelieve]

Why do I get WA ? It works on my computer and produses right answers for the sample outputs provided ...

[pascal]
program GettingInLine;
var si,s:array [1..1000] of integer;
x,y:array [1..1000] of integer;
a,r:real;
stars:string;
visited:array [1..1000] of boolean;
function dist(x1,y1,x2,y2:real):real;
begin
dist:=sqrt(sqr(x2-x1)+sqr(y2-y1))+16;
end;
procedure backtrack(n,i:integer;d:real);
var k:integer;
begin
if (i = N+1) then
if (D<R) then begin R:=D;Si:=S end else begin end else
for k:=1 to n do
begin
s:=k;
if not visited[k] then
begin
visitedt[k]:=true;
if i>1 then
a:=D+Dist(x[S],y[S],x[S[i-1]],y[S[i-1]])
else a:=0;
if (a<=R) then
backtrack(n,i+1,a);
visited[k]:=false;
end;
end;
end;
procedure ReadTest(n:integer);
var i:integer;
begin
for i:=1 to n do
readln(input,x,y);
end;
procedure ReadNSolve;
var nr,i,n:integer;
begin
stars:='**********************************************************';
nr:=1;
R:=maxint;
readln(input,n);
while (n<>0) do
begin
ReadTest(n);
backtrack(n,1,0);
writeln(Stars);
writeln('Network #',nr);
for i:=2 to n do
writeln('Cable requirement to connect (',x[Si[i-1]],',',y[Si[i-1]],') to (',x[Si],',',y[Si],') is ',dist(x[Si[i-1]],y[Si[i-1]],x[Si],y[Si]):2:2,' feet.');
writeln('Number of feet of cable required is ',R:2:2,'.');
readln(input,N);
R:=maxint;
end;
end;
begin
ReadNSolve;
end.
[/pascal]

[little joey]

About your tagline: I don't agree with you, but that doesn't mean you're right...

About your posting: Why do you post it here and not in the forum for volume 2?

About your program: I can't believe it compiles on your system because it contains a typo:
in procedure backtrack you use visitedt[k] in stead of visited[k] on one occasion...

Your program will get accepted if you print the appropriate network number in stead of "Network #1:" for every network.

[watershed]

please tell me
if input is..

Code: Select all

2
100 100
100 100

answer should ?

Code: Select all

**********************************************************
Network #1
Cable requirement to connect (100,100) to (100,100) is 16.00 feet.
Number of feet of cable required is 16.00.

Code: Select all

**********************************************************
Network #1
Cable requirement to connect (100,100) to (100,100) is 0.00 feet.
Number of feet of cable required is 0.00.

[UFP2161]

My program outtputed the first one, but it shouldn't matter since the description states that:

No two computers are at identical locations and each computer will be listed once.