Thank you so much.
O(n^3) with 0.00 sec, wow 
Your is not O(n2) ,you are using map each operation of map take O(logN) time
remove map from your solution.
1 Like
I know my logic is wrong but can anyone answer “WHY” my approach is wrong?
I start from sharechat find closest A or B point then move on to the next closest B point if i visited A or viceversa,then from this point find the shortest distance C, point.
Essentially I’m moving to shortest distance point in every iteration.
But this approach does not lead to shortest distance can anyone share why?
my solution link:
https://www.codechef.com/viewsolution/27869846
It’s wrong for the reason that most Greedy algorithms are wrong; inability to make a short-term sacrifice for a long-term gain.
Consider the testcase:
1
10 10
2 1 1
9 10 11 10
12 10
13 10
2 Likes
Thanks, I’m new to CP and do not really know about Greedy algorithms etc. I do not exactly understand this “inability to make short term sacrifice for longterm gain” could just brief a bit more on that?
I think that explains why my approach is wrong and would be helpful if i understand it properly so that i could know when or when not to use the approach again.
Check these links:
Greediness in general: Greedy Algorithms - GeeksforGeeks
Where Greediness fails: examples - Counterexamples to the Greedy Algorithm - Mathematics Educators Stack Exchange
2 Likes
You are only looking at local minimum, instead of focussing on the global minimum.
Here is my explanation on another solution with an approach similar to yours. Hope it helps!
https://discuss.codechef.com/t/wa-in-the-problem-phcul/44226/4?u=shridharravi97
5 Likes
Sorry about the codepasta below but can anyone tell me what I am doing wrong? It’s giving me the weird result of
7.576491222541474
9.660424813608417
for the sample input and I am tired of trying to figure out where the error is.
public static void main (String[] args) throws java.lang.Exception
{
InputReader in = new InputReader(System.in);
int t = in.nextInt();
StringBuilder s = new StringBuilder();
while(t-- > 0) {
String[] input = in.nextLine().split(" ");
long x = Long.parseLong(input[0]);
long y = Long.parseLong(input[1]);
input = in.nextLine().split(" ");
int n = Integer.parseInt(input[0]);
int m = Integer.parseInt(input[1]);
int k = Integer.parseInt(input[2]);
input = in.nextLine().split(" ");
Pair[] aarray = new Pair[n];
for (int i=0, j = 0; i<n * 2; i+=2, ++j) {
aarray[j] = new Pair(Long.parseLong(input[i]), Long.parseLong(input[i+1]));
}
input = in.nextLine().split(" ");
Pair[] barray = new Pair[m];
for (int i=0, j = 0; i<m * 2; i+=2, ++j) {
barray[j] = new Pair(Long.parseLong(input[i]), Long.parseLong(input[i+1]));
}
input = in.nextLine().split(" ");
Pair[] carray = new Pair[k];
for (int i=0, j = 0; i<k * 2; i+=2, ++j) {
carray[j] = new Pair(Long.parseLong(input[i]), Long.parseLong(input[i+1]));
}
double besta2c = Double.MAX_VALUE, bestb2c = Double.MAX_VALUE;
for (int i=0; i<k; ++i) {
for (int j=0; j<n; ++j)
besta2c = Math.min(besta2c, Math.sqrt(Math.pow(carray[i].x - aarray[j].x, 2) + Math.pow(carray[i].y - aarray[j].y, 2)));
}
for (int i=0; i<k; ++i) {
for (int j=0; j<m; ++j)
bestb2c = Math.min(bestb2c, Math.sqrt(Math.pow(carray[i].x - barray[j].x, 2) + Math.pow(carray[i].y - barray[j].y, 2)));
}
double bestp2a = Double.MAX_VALUE, besta2b = Double.MAX_VALUE, bestp2b = Double.MAX_VALUE;
for (int i=0; i<n; ++i) {
bestp2a = Math.min(bestp2a, Math.sqrt(Math.pow(x - aarray[i].x, 2) + Math.pow(y - aarray[i].y, 2)));
}
for (int i=0; i<m; ++i) {
bestp2b = Math.min(bestp2b, Math.sqrt(Math.pow(x - barray[i].x, 2) + Math.pow(y - barray[i].y, 2)));
}
for (int i=0; i<n; ++i) {
for (int j=0; j<m; ++j)
besta2b = Math.min(besta2b, Math.sqrt(Math.pow(aarray[i].x - barray[j].x, 2) + Math.pow(aarray[i].y - barray[j].y, 2)));
}
s.append(Math.min(bestp2a + besta2b + besta2c, bestp2b + besta2b + bestb2c)).append("\n");
}
System.out.print(s);
}
static class Pair {
public long x;
public long y;
Pair(long x, long y) {
this.x = x;
this.y = y;
}
}@vickyvanshaj
In the first solution, min is your final result.
While we calculate distance(newPath) each time, we compare it with min.
If distance(newPath) >= min, then whether we are at point a / b, distance(newPath) will ultimately increase(except at point c which is final point) or remains same, if final point c overlaps with a / b, so there is no meaning of further calculation.
Without the if statement, complexity of problem is O(n * m * k), but I’m not sure of complexity when we include the if statements.
You have found the minimum distance for the paths (x -> n), (n -> m) and (m -> k)
It works well till now. However, after this step you have used the wrong indexes from line 66. Hence the wrong answer.
You are referring to i th index of mx & my and j th index of nx & ny, but it should be the other way around. Make these changes and you will get partially correct answer.
As for the TLE, You are making unnecessary calculations for large test cases. If I have final already less than the minimum distances for the paths (x -> n) or (x -> m), should I still go ahead and calculate the distance for the entire path? Give it a thought
2 Likes
You are committing a common mistake for this problem. Adding up the minimum distances from individual paths will not be the minimum distance for the overall path.
Here is my explanation on another solution with an approach similar to yours.
https://discuss.codechef.com/t/wa-in-the-problem-phcul/44226/4?u=shridharravi97
2 Likes
Thanks! I was beginning to suspect as much but still wasn’t sure if it really was that way.
But how do you realize that it’s a mistake? Because at a first glance, it seems logical to take only the min distances. How do you prove that it’s not so?
Edit: Also, the result for the first sample input is 7.57 for my solution which is below the 8.18 given in the sample output. Isn’t that a better answer? Where is the issue?
Hey, can anyone help me in this code, I am looping over all the points, only if the distance_till_now < ans_distance
https://www.codechef.com/viewsolution/27895908
It doesn’t seem right because there isn’t any connection between the paths you have chosen. The problem wants us to find the path with the overall minimum distance.
If You choose a path A->B and then choose a path C->D, there isnt any connection between B & C here. We need a proper continuous path. This should even answer your second question as to why 7.57 is wrong.
Hmm, yeah I know the obvious reason why it’s giving a smaller answer is because some path is not getting added. But I think I am adding all the paths in that last line
Math.min(bestp2a + besta2b + besta2c, bestp2b + besta2b + bestb2c)
p2a is from the point to the first set
a2b is in between first and second set
a2c is in between second and last set
Same for the second way from p -> b -> a -> c
So it should be adding all the paths but something is missing somewhere, I guess. Thanks anyway.