L
Luc The Perverse
Just shoot me!
I spent all day (5 hours) working on a top coder problem and now it is
failing the test cases after I thought I finally had it.
I was wondering if anyone could tell me what is going wrong.
Here is the problem. (If I am misusing the word permutation and should be
using the word combination, please forgive me, but at least I will be
consistent!)
Problem Statement
A traveling salesman has recently decided to go international
and sell his wares around the globe. He has done in depth research and has
come up with a list of cities which he thinks will provide the best market
for his goods. In planning his trip, the salesman wants to minimize the
total distance he has to travel because he does not particularly like
traveling (which is unfortunate for him, as he is a traveling salesman) and
furthermore, he figures the less distance he has to travel, the cheaper his
trip will be. However, this salesman is not particularly good at math, and
so you must write a computer program to help him find his way in the least
distance.
You will be given a set of cities defined by their longitudes and
latitudes. In addition, you will be given the radius of the planet that this
traveling salesman resides on. Assume that there are direct flights, both
ways, between every pair of cities that the salesman wants to visit, and
that the flights follow the shortest path possible (over the surface of the
planet). In addition, the first element of the input String[] will be the
city in which the salesman lives, and thus his trip must start and end at
this city.
Each city is defined by two numbers, a latitude and a longitude. The
latitude is the number of degrees above the equator, with 90 being the north
pole, and -90 being the south pole. The longitude is the number of degrees
east or west of some arbitrary, predefined point. Thus, 90 degrees east is
one quarter of the way around the globe in the eastern direction.
If the result is not an integer, round it to the nearest integer (.5
rounds up)
Definition
Class: Travel
Method: shortest
Parameters: String[], int
Returns: int
Method signature: int shortest(String[] cities, int radius)
(be sure your method is public)
Notes
- Assume the planet is a perfect sphere.
- To find the cartesion coordinates of a city, assuming the center of
the planet is at (0,0,0), use the following formulas:
x = r*cos(latitude)*cos(longitude)
y = r*cos(latitude)*sin(longitude)
z = r*sin(latitude)
Constraints
- cities contains between 2 and 9 elements, inclusive.
- Each element of cities represents a unique point on the globe.
- Each element of cities is formatted as "<latitude> <longitude>"
where <latitude> is an integer in the range -90 to 90, inclusive, and
<longitude> is an integer in the range -180 to 180, inclusive.
- radius is an integer between 1 and 1,000, inclusive.
- to avoid rounding errors, the shortest path, prior to rounding,
will not be within 0.001 of <x>+0.5 for any integer <x>.
Examples
0)
{"0 0","0 1"}
1000
Returns: 35
The two cities are located one degree apart at the same
latitude
1)
{"0 0","0 1","0 -1","-1 0","1 0","-1 -1","1 1","1 -1","-1 1"}
1
Returns: 0
2)
{"40 -82","-27 -59","-40 48"
,"26 -12","-31 -37","-30 42"
,"-36 -23","-26 71","-19 83","8 63"}
698
Returns: 4505
This problem statement is the exclusive and proprietary property of
TopCoder, Inc. Any unauthorized use or reproduction of this information
without the prior written consent of TopCoder, Inc. is strictly prohibited.
(c)2003, TopCoder, Inc. All rights reserved.
Alright then - here is my [flawed] solution (It passes the example problem
and first 15 test cases)
import java.math.*;
import java.lang.*;
public class Travel{
double sin(double x){return Math.sin(x);};
double cos(double x){return Math.cos(x);};
double[][] di;
void calc(String[] cities, int radius){
double r = (double) radius;
double[][] p = new double[cities.length][2];
for(int i=0;i<cities.length;i++){
p[0] =
Math.toRadians((double)java.lang.Integer.parseInt(cities.substring(0,cities.indexOf("
"))));
p[1] =
Math.toRadians((double)java.lang.Integer.parseInt(cities.substring(cities.indexOf("
")+1)));
}
for(int i=0;i<cities.length;i++)
for(int j=0;j<cities.length;j++){
di[j] = (double) r* Math.acos(sin(p[0]) * sin(p[j][0]) +
cos(p[0]) * cos(p[j][0]) * cos(p[1] - p[j][1]) );
}
}
int[] newPerm(int c, int[] pr){ // c>=0 && c<=pr.length
int[] ret = new int[pr.length+1];
for(int i=0;i<pr.length;i++)
ret = pr;
ret[pr.length] = ret[c];
ret[c] = pr.length+1;
return ret;
}
public int shortest(String[] cities, int radius){
di = new double[cities.length][cities.length];
calc(cities, radius);
int NP = 1;
int[][][] perms = new int[cities.length][][];
perms[0] = new int[0][0]; //empty set
for(int i=1;i<cities.length;i++){ //remember home cities is always start
and end point, ignore
NP*=i;
perms = new int[NP][];
}
perms[1][0] = new int[1];
perms[1][0][0]=1;
for(int i = 2; i<perms.length;i++){
int cp=0;
for(int j=0;j<perms[i-1].length;j++)
for(int c=0;c<i;c++)
perms[cp++] = newPerm(c, perms[i-1][j]);
}
int[][] my = perms[perms.length-1]; // used to reference
perms[perms.length-1] to aid with clarity
double min = 0.0;
for(int i=0;i<di.length;i++)
for(int j=0;j<di.length;j++)
min+=di[j];
for(int i=0;i<my.length;i++){
double len = di[0][my[0]];
len+= di[0][my[my.length-1]];
for(int j=1;j<my.length;j++)
len += di[my[j-1]][my[j]];
if(len<min)
min = len;
}
return (int)(min+0.5); //remember to round up
}
}
This is the report I got
Failed system test 16 on the 300-point problem with args: [{"52 -150",
"-16 -166", "-88 -166", "58 -157", "58 147", "-32 41"}, 125]
EXPECTED: 790
RECEIVED: 0
I am fairly unfamiliar with spherical geometry so I used this wikipedia
article here to get my distance formula (this is my best guess as to where
the problem lies)
http://en.wikipedia.org/wiki/Great-circle_distance#The_formula
It says that the formula I used suffered from rounding errors in a real
world environment, but the function itself is theoretically always accurate.
Since they were talking from a historical perspective, I was under the
assumption that the other formulae were simply there to facilitate with hand
calculations. (I did initially try one of the other fomulae but I think I
typed it wrong.)
I believe the lowest theortical score you can get on a top coder problem is
30% of the total points available, and I am within 1 point of this on the
exponential decay curve. In other words, I have failed! But that doesn't
mean I don't want to set it right.
I'll probably come back later and try to figure it out again, but for now I
am very frustrated. Any help would be appreciated. I have struggled with
every part of this. I tried to use a method for generating permutations in
which I could avoid overuse of the modulus operator, and I was forced to put
part of it in a function because it was exceptionally convoluted inline.
Appologies on the variable names. I wasn't planning on showing this to
anyone. Here is a brief synopsis (most variables are truncated english
words, shortened for easier typing):
Class:
di = distance between two cities
Calc Function (for calculating distances and putting in table)
r = radius, was originally used extensively so a shortened precasted
double was needed
p = the latitude and longitude of a location extracted from the string
array, but converted to rtadians
newPerm function (For generating a single permuation of X items 1 through X
given a permuation of X-1, by inserting X at location c)
ret = abbreviation for return value, holds the permutation
shortest function (As defined in the problem)
note: since the starting and ending city are always index 0,
index 0 is ommitted from the permutations
NP - holds the number of total permutations and is used incrementally
for declaring array sizes
perms - a holder for the permutations
cp - current position (a counter) simply a way of keeping track of which
permutation we are currently populating
my - a shortcut to perms[perms.length-1] and a variable name I
anticipate criticism for
min - the current minimum distance, initialized to the sum of all the
values in the di table (assumed all positive) which should be [greatly]
larger than the first permutation, so it will be reset in the first
iteration.
len - a temporary variable for holding the length of the trip to compare
against min. (The length is obviously just the sum of the distances
between all cities visited.)
Sorry if I missed any of them.
Thanks in advance for any help!
Oh if anyone cares, or it helps anyone this is practice room 14 300 point
(easy LOL) problem corresponding to the 2002 TopCoder Invitational Semifinal
Round 3. Here is a link to the problem, but I don't see where to get the
solution as they were submitted. It looks like 3 of the 4 contestants
submitted and they all three got it right.
http://www.topcoder.com/stat?c=problem_statement&pm=996&rd=4372
Am I making this problem way harder than I need to?
I spent all day (5 hours) working on a top coder problem and now it is
failing the test cases after I thought I finally had it.
I was wondering if anyone could tell me what is going wrong.
Here is the problem. (If I am misusing the word permutation and should be
using the word combination, please forgive me, but at least I will be
consistent!)
Problem Statement
A traveling salesman has recently decided to go international
and sell his wares around the globe. He has done in depth research and has
come up with a list of cities which he thinks will provide the best market
for his goods. In planning his trip, the salesman wants to minimize the
total distance he has to travel because he does not particularly like
traveling (which is unfortunate for him, as he is a traveling salesman) and
furthermore, he figures the less distance he has to travel, the cheaper his
trip will be. However, this salesman is not particularly good at math, and
so you must write a computer program to help him find his way in the least
distance.
You will be given a set of cities defined by their longitudes and
latitudes. In addition, you will be given the radius of the planet that this
traveling salesman resides on. Assume that there are direct flights, both
ways, between every pair of cities that the salesman wants to visit, and
that the flights follow the shortest path possible (over the surface of the
planet). In addition, the first element of the input String[] will be the
city in which the salesman lives, and thus his trip must start and end at
this city.
Each city is defined by two numbers, a latitude and a longitude. The
latitude is the number of degrees above the equator, with 90 being the north
pole, and -90 being the south pole. The longitude is the number of degrees
east or west of some arbitrary, predefined point. Thus, 90 degrees east is
one quarter of the way around the globe in the eastern direction.
If the result is not an integer, round it to the nearest integer (.5
rounds up)
Definition
Class: Travel
Method: shortest
Parameters: String[], int
Returns: int
Method signature: int shortest(String[] cities, int radius)
(be sure your method is public)
Notes
- Assume the planet is a perfect sphere.
- To find the cartesion coordinates of a city, assuming the center of
the planet is at (0,0,0), use the following formulas:
x = r*cos(latitude)*cos(longitude)
y = r*cos(latitude)*sin(longitude)
z = r*sin(latitude)
Constraints
- cities contains between 2 and 9 elements, inclusive.
- Each element of cities represents a unique point on the globe.
- Each element of cities is formatted as "<latitude> <longitude>"
where <latitude> is an integer in the range -90 to 90, inclusive, and
<longitude> is an integer in the range -180 to 180, inclusive.
- radius is an integer between 1 and 1,000, inclusive.
- to avoid rounding errors, the shortest path, prior to rounding,
will not be within 0.001 of <x>+0.5 for any integer <x>.
Examples
0)
{"0 0","0 1"}
1000
Returns: 35
The two cities are located one degree apart at the same
latitude
1)
{"0 0","0 1","0 -1","-1 0","1 0","-1 -1","1 1","1 -1","-1 1"}
1
Returns: 0
2)
{"40 -82","-27 -59","-40 48"
,"26 -12","-31 -37","-30 42"
,"-36 -23","-26 71","-19 83","8 63"}
698
Returns: 4505
This problem statement is the exclusive and proprietary property of
TopCoder, Inc. Any unauthorized use or reproduction of this information
without the prior written consent of TopCoder, Inc. is strictly prohibited.
(c)2003, TopCoder, Inc. All rights reserved.
Alright then - here is my [flawed] solution (It passes the example problem
and first 15 test cases)
import java.math.*;
import java.lang.*;
public class Travel{
double sin(double x){return Math.sin(x);};
double cos(double x){return Math.cos(x);};
double[][] di;
void calc(String[] cities, int radius){
double r = (double) radius;
double[][] p = new double[cities.length][2];
for(int i=0;i<cities.length;i++){
p[0] =
Math.toRadians((double)java.lang.Integer.parseInt(cities.substring(0,cities.indexOf("
"))));
p[1] =
Math.toRadians((double)java.lang.Integer.parseInt(cities.substring(cities.indexOf("
")+1)));
}
for(int i=0;i<cities.length;i++)
for(int j=0;j<cities.length;j++){
di[j] = (double) r* Math.acos(sin(p[0]) * sin(p[j][0]) +
cos(p[0]) * cos(p[j][0]) * cos(p[1] - p[j][1]) );
}
}
int[] newPerm(int c, int[] pr){ // c>=0 && c<=pr.length
int[] ret = new int[pr.length+1];
for(int i=0;i<pr.length;i++)
ret = pr;
ret[pr.length] = ret[c];
ret[c] = pr.length+1;
return ret;
}
public int shortest(String[] cities, int radius){
di = new double[cities.length][cities.length];
calc(cities, radius);
int NP = 1;
int[][][] perms = new int[cities.length][][];
perms[0] = new int[0][0]; //empty set
for(int i=1;i<cities.length;i++){ //remember home cities is always start
and end point, ignore
NP*=i;
perms = new int[NP][];
}
perms[1][0] = new int[1];
perms[1][0][0]=1;
for(int i = 2; i<perms.length;i++){
int cp=0;
for(int j=0;j<perms[i-1].length;j++)
for(int c=0;c<i;c++)
perms[cp++] = newPerm(c, perms[i-1][j]);
}
int[][] my = perms[perms.length-1]; // used to reference
perms[perms.length-1] to aid with clarity
double min = 0.0;
for(int i=0;i<di.length;i++)
for(int j=0;j<di.length;j++)
min+=di[j];
for(int i=0;i<my.length;i++){
double len = di[0][my[0]];
len+= di[0][my[my.length-1]];
for(int j=1;j<my.length;j++)
len += di[my[j-1]][my[j]];
if(len<min)
min = len;
}
return (int)(min+0.5); //remember to round up
}
}
This is the report I got
Failed system test 16 on the 300-point problem with args: [{"52 -150",
"-16 -166", "-88 -166", "58 -157", "58 147", "-32 41"}, 125]
EXPECTED: 790
RECEIVED: 0
I am fairly unfamiliar with spherical geometry so I used this wikipedia
article here to get my distance formula (this is my best guess as to where
the problem lies)
http://en.wikipedia.org/wiki/Great-circle_distance#The_formula
It says that the formula I used suffered from rounding errors in a real
world environment, but the function itself is theoretically always accurate.
Since they were talking from a historical perspective, I was under the
assumption that the other formulae were simply there to facilitate with hand
calculations. (I did initially try one of the other fomulae but I think I
typed it wrong.)
I believe the lowest theortical score you can get on a top coder problem is
30% of the total points available, and I am within 1 point of this on the
exponential decay curve. In other words, I have failed! But that doesn't
mean I don't want to set it right.
I'll probably come back later and try to figure it out again, but for now I
am very frustrated. Any help would be appreciated. I have struggled with
every part of this. I tried to use a method for generating permutations in
which I could avoid overuse of the modulus operator, and I was forced to put
part of it in a function because it was exceptionally convoluted inline.
Appologies on the variable names. I wasn't planning on showing this to
anyone. Here is a brief synopsis (most variables are truncated english
words, shortened for easier typing):
Class:
di = distance between two cities
Calc Function (for calculating distances and putting in table)
r = radius, was originally used extensively so a shortened precasted
double was needed
p = the latitude and longitude of a location extracted from the string
array, but converted to rtadians
newPerm function (For generating a single permuation of X items 1 through X
given a permuation of X-1, by inserting X at location c)
ret = abbreviation for return value, holds the permutation
shortest function (As defined in the problem)
note: since the starting and ending city are always index 0,
index 0 is ommitted from the permutations
NP - holds the number of total permutations and is used incrementally
for declaring array sizes
perms - a holder for the permutations
cp - current position (a counter) simply a way of keeping track of which
permutation we are currently populating
my - a shortcut to perms[perms.length-1] and a variable name I
anticipate criticism for
min - the current minimum distance, initialized to the sum of all the
values in the di table (assumed all positive) which should be [greatly]
larger than the first permutation, so it will be reset in the first
iteration.
len - a temporary variable for holding the length of the trip to compare
against min. (The length is obviously just the sum of the distances
between all cities visited.)
Sorry if I missed any of them.
Thanks in advance for any help!
Oh if anyone cares, or it helps anyone this is practice room 14 300 point
(easy LOL) problem corresponding to the 2002 TopCoder Invitational Semifinal
Round 3. Here is a link to the problem, but I don't see where to get the
solution as they were submitted. It looks like 3 of the 4 contestants
submitted and they all three got it right.
http://www.topcoder.com/stat?c=problem_statement&pm=996&rd=4372
Am I making this problem way harder than I need to?
