PHCUL - Editorial

Thank you so much.

O(n^3) with 0.00 sec, wow :stuck_out_tongue_winking_eye:

Your is not O(n2) ,you are using map each operation of map take O(logN) time
remove map from your solution.

1 Like

@vickyvanshaj,
I am also having the same doubt. Let me know whenever you find any solution.

Thanks @savaliya_vivek. I have removed maps and replace it with vector for memoization.

https://www.codechef.com/viewsolution/27888449

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: https://www.geeksforgeeks.org/greedy-algorithms/
Where Greediness fails: https://matheducators.stackexchange.com/questions/10692/counterexamples-to-the-greedy-algorithm

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

Thank you! @ssjgz @shridharravi97

2 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.

https://www.codechef.com/viewsolution/27714952

Can anyone please tell me why I am getting WA?

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.