PHCUL - Editorial

[coder7297]

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

[rbjoshi1309]

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

[srb27199]

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

Can anyone please tell me why I am getting WA?

[shridharravi97]

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

[shridharravi97]

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

[coder7297]

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?

[ashhad]

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

[shridharravi97]

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.

[coder7297]

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.

[ankushkhanna]

This problem had pretty weak tests. Something should be done about it. Please refer to this thread.

Weak test cases for PHCUL (NOV Long Challenge) and Unfair problem for Python users

Problem PHCUL of NOV Long Challenge 2019 has weak test cases. Test cases generated here : https://www.codechef.com/viewsolution/27876282 The solution in the above link fails to pass the above test case as Time complexity of the code in the worst case is O(N^3). But it still gets AC due to weak test cases. Also, this problem was very unfair to Python users as one of my friend @ankushkhanna, when implemented his optimised code in Python in Practice Section (originally written in C++ du…

@admin @vijju123 @alei @vladprog @yash_chandnani @watcher

[anshuman_hunt]

My code uses a similar logic and has the same time complexity (according to my naive brain) but it is still getting TLE in subtask 2. Can you help me make it more efficient and point out where I am going wrong?

The link to my code is: CodeChef: Practical coding for everyone

[strang]

I’m unable to understand the solution even after reading the editorial and the comments.
Can anyone explain, using an algorithm?

[praty_u_s_h]

@savaliya_vivek
@ssjgz

Sir, can you debug this code …It’s giving AC for the last two test cases
and WA for the rest.
submission link: https://www.codechef.com/viewsolution/27939145

for the sample test cases it gives correct for 2 case but not for the first case…please help

[blacksag]

@vladprog The approach given is great! Never thought that this can be achieved in a better way. Although I was wandering that if this approach can also be applied when,

The order of visiting the the nodes ‘a’ and ‘b’ is fixed.

Meaning, that starting from (x,y) we can only go to a ∈ A then b ∈ B then c ∈ C.
Can this be achieved in n^2 complexity or we have to simply do a brute force?

[vladprog]

This problem can be solved with the same solution as in editorial

[blacksag]

Thanx for the tip! I will try to figure out a way for this.

Also here is my solution, which I think is cleaner and also slightly optimized for,

@watcher

ans=min({ans, ab1[i]+dist(a[i],b[i],c[j],d[j])+cd2[j], cd1[j]+dist(c[j],d[j],a[i],b[i])+ab2[i]});

Here, distance between the point ‘a’ and ‘b’ is calculated twice which will remain same and thus need to be calculated only once.

temp = min( ab1[i]+cd2[j], cd1[j]+ab2[i]) + dist(a[i],b[i],c[j],d[j]);
if(temp<ans) ans=temp;

[satyamchulania]

Can someone check this please. I am unable to understand why am i getting WA?
https://www.codechef.com/viewsolution/28483342

[ssjgz]

That’s not a link to you solution

[satyamchulania]

Edited. Please check.

[cfacto]

Tried using Skip conditions with O(n^3) complexity but the last test case went wrong. Can this sol. be made correct with little changes ?
https://www.codechef.com/viewsolution/28510869