WA in the Problem PHCUL

Problem Code: https://www.codechef.com/NOV19B/problems/PHCUL

Can anyone help me with this code regarding Problem PHCUL

I am doing the same doing as stated in the Problem.

Code link:https://www.codechef.com/viewsolution/27845303

#include <bits/stdc++.h>
using namespace std;

int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t–)
{
long double x,y,n,m,k,a,d1=0,d2=0,d3=0,minm=1000000001.0,s=0,ans1=0,ans2=0,s1=0,s2=0,s3=0,s4=0,s5=0;
cin>>x>>y;
cin>>n>>m>>k;
vectorn1;
vectorm1;
vectork1;
vector<pair<int,int>>n2;
vector<pair<int,int>>m2;
vector<pair<int,int>>k2;

    for(int i=0;i<2*n;i++){cin>>a; n1.push_back(a);}
    for(int i=0;i<2*m;i++){cin>>a; m1.push_back(a);}
    for(int i=0;i<2*k;i++){cin>>a; k1.push_back(a);}
    for(int i=0;i<2*n;i=i+2){ n2.push_back(make_pair(n1[i],n1[i+1])); }
    for(int i=0;i<2*m;i=i+2){ m2.push_back(make_pair(m1[i],m1[i+1])); }
    for(int i=0;i<2*k;i=i+2){ k2.push_back(make_pair(k1[i],k1[i+1]));}


    //calculating distance from (x,y)
    for(int i=0;i<n2.size();i++)
    {
       d1=sqrt((x-n2[i].first)*(x-n2[i].first) + (y-n2[i].second)*(y-n2[i].second));
       if(d1<minm){ minm=d1;s=i;}
    }
     ans1+=minm;
     minm=INT_MAX;
    //calc. from (a,b)
    for(int i=0;i<m2.size();i++)
    {
       d2=sqrt((n2[s].first-m2[i].first)*(n2[s].first-m2[i].first) + (n2[s].second-m2[i].second)*(n2[s].second-m2[i].second));
       if(d2<minm){minm=d2;s1=i;}
    }

     ans1+=minm;
     minm=INT_MAX;
     //calc from (c,d)
    for(int i=0;i<k2.size();i++)
    {
       d3=sqrt((m2[s1].first-k2[i].first)*(m2[s1].first-k2[i].first) + (m2[s1].second-k2[i].second)*(m2[s1].second-k2[i].second));
       if(d3<minm){minm=d3;s2=i;}
    }
    ans1+=minm;
    minm=INT_MAX;


    //-------------------------------------------------------------

    for(int i=0;i<m2.size();i++)
    {
       d1=sqrt((x-m2[i].first)*(x-m2[i].first)  + (y-m2[i].second)*(y-m2[i].second));
       if(d1<minm){minm=d1;s3=i;}
    }
    //cout<<m2[s].first<<" "<<m2[s].second<<endl;

     ans2+=minm;
     minm=INT_MAX;

    //calc. from (c,d)
    for(int i=0;i<n2.size();i++)
    {
       d2=sqrt((m2[s3].first-n2[i].first)*(m2[s3].first-n2[i].first) + (m2[s3].second-n2[i].second)*(m2[s3].first-n2[i].first));
       if(d2<minm)
       {
         minm=d2;s4=i;
       }
    }

    ans2+=minm;
     minm=INT_MAX;

     //calc from (a,b)
    for(int i=0;i<k2.size();i++)
    {
        d3=sqrt((n2[s4].first-k2[i].first)*(n2[s4].first-k2[i].first) + (n2[s4].second-k2[i].second)*(n2[s4].second-k2[i].second));
       if(d3<minm){minm=d3;s5=i;}
    }
    ans2+=minm;

  cout<<fixed<<setprecision(16)<<min(ans1,ans2)<<endl;




}
return 0;

}

You are finding the minimum distance from the starting point (x,y) to a point in set N (or M).
Then you are finding the minimum distance from that point onwards to a point in set M (or N). And then you proceed from that point to the end point from set K
The path you have chosen till now is not necessarily the path with the minimum distance. You have to find the path with minimum distance overall

2 Likes

@shridharravi97,Thanks for replying,Can you explain your statement so that i could Solve this Problem.

Consider this test case:
1
0 0
2 2 1
1 0 1 1
2 2 4 3
3 3

Here we have starting point (x,y) as (0,0)
Points in N as (1,0) and (1,1)
Points in M as (2,2) and (4,3)
Points in K as (3,3)

Let us consider the path as start -> N -> M -> K (for now)
Step 1: Distance of points in N from (0,0)
i) point (1,0) lies at a distance of 1.00
ii) point (1,1) lies at a distance of 1.41

Your approach selects point (i). Lets go with it
Step 2: Distance of points in M from (1,0)
i) point (2,2) lies at a distance of 2.23
ii) point (4,3) lies at a distance of 4.24

Your approach selects point (i). Lets go with it
Step 3: Distance of points in K from (2,2)
i) point (3,3) lies at a distance of 1.41

Path selected: (0,0) -> (1,0) -> (2,2) -> (3,3)
Total distance=1.00+3.23+1.41=7.47
This is your output. However there exists a better path with minimum distance.

In Step 1, if you select point (ii) then,
Step A: Distance of points in M from (1,1)
a)point (2,2) lies at a distance of 1.41
b) point (4,3) lies at a distance of 3.61

If we select point (a), then
Step B: Distance of points in K from (2,2)
a) point (3,3) lies at a distance of 1.41

Path selected: (0,0) -> (1,1) -> (2,2) -> (3,3)
Total distance=1.41+1.41+1.41=4.23

This is the path with minimum distance.
Your approach only looked at the local minimum. However, you should be looking for the global minimum. Hope you understood!

6 Likes

Can you give me a test case where my code is failing
Link: https://ideone.com/m0q8B1

Someone please check this.only last tc is giving WA.
https://www.codechef.com/viewsolution/27695570

replace your float with long double it will pass alll the cases.
https://www.codechef.com/viewsolution/27872716
Done this on your code. Kudos!

2 Likes

Lots of Regrets😭

@sshridharravi97 , Thanks for replying and giving the best explaination.
You mean to say that i have to check for every point regardless of its local distance?

Yes. Although you can skip path if the distance to that point till now is already greater than the minimum distance calculated till now

1 Like