PHCUL - Editorial

PROBLEM LINK:

Practice
Div-2 Contest
Div-1 Contest

Author: Vlad
Tester: Yash Chandnani
Editorialist: Michael Nematollahi

DIFFICULTY:

EASY

PREREQUISITES:

None

PROBLEM:

You are given three sets of points A, B, C \in \R^2. You’re also given a point p represented by its coordinates x and y.

You want to choose three points a \in A, b \in B, c \in C, start from p, visit a and b in any order and then visit c. Your goal is to make the total distance travelled minimum.

QUICK EXPLANATION:

For each point in A and B, find out what’s the distance to the closest point in C to this point.
Then, try all possible combinations of a point a \in A and a point b \in B. The optimal point to choose from C is the closest point to a or b depending on the order you’ve visited them.
You’ve already calculated the distance to this optimal point, so you can access it in O(1).

EXPLANATION:

We’ll solve this problem in two steps.

Step 1:

Let a_i be a point in A. We can find the closest point c \in C to a_i by looping through all elements of C and calculating the distance between a_i and this point.
This would take O(N \times K \times log(MAX)) (where MAX = 2 \times 10^{18} is the maximum value of the square of the distance between two points), as we’re doing this for every point in A. The log factor comes from the sqrt function required to calculate a distance.
Let best[0][a_i] denote the distance between c to a_i.

Similarly, we can calculate best[1][b_i], which represents the smallest distance from a point in C to b_i. This would take O(M \times K \times log(MAX)).

Step 2:

Without loss of generality, let’s assume we first visit a point in A, then a point in B and finally a point in C.
Let’s try all the possible combination of a point a \in A and a point b \in B. For a fixed pair of a and b, the resulting total distance travelled will be

dist(p, a) + dist(a, b) + dist(b, c)

where dist(u, v) is the euclidean distance between the points u and v and c is a point in C.
Note that the first two terms are fixed as a and b are fixed. The only part that is not known is dist(b, c). To make this distance minimum, we want dist(b, c) to be minimum.
On the other hand, we’ve already calculated best[1][b] in step 1, which is the minimum value of dist(b, c) for all possible c's.
Hence, we can use best[1][b] to find the minimum value of dist(p, a) + dist(a, b) + dist(b, c) in O(log(MAX)).

This gives us a complexity of O(N \times M \times log(MAX) for step 2.

This gives us a solution with the overall complexity of O((N \times M + N \times K + M \times K) \times log(MAX)).

To see an implementation of the described solution, refer to the editorialist’s code below.

SOLUTIONS:

Setter's Solution
// OK
 
#include<bits/stdc++.h>
 
using namespace std;
 
typedef long double ld;
 
ld dist(int x1,int y1,int x2,int y2)
{
    ld dx=abs(x1-x2);
    ld dy=abs(y1-y2);
    return sqrt(dx*dx+dy*dy);
}
 
const int N=5010;
const ld INF=1e10;
 
int a[N],b[N],c[N],d[N],e[N],f[N];
ld ab1[N],ab2[N],cd1[N],cd2[N];
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int q;
    cin>>q;
    while(q--)
    {
        int x,y,n,m,k;
        cin>>x>>y>>n>>m>>k;
        for(int i=1;i<=n;i++)
            cin>>a[i]>>b[i];
        for(int j=1;j<=m;j++)
            cin>>c[j]>>d[j];
        for(int t=1;t<=k;t++)
            cin>>e[t]>>f[t];
        for(int i=1;i<=n;i++)
        {
            ab1[i]=dist(x,y,a[i],b[i]);
            ab2[i]=INF;
            for(int t=1;t<=k;t++)
                ab2[i]=min(ab2[i],dist(a[i],b[i],e[t],f[t]));
        }
        for(int j=1;j<=m;j++)
        {
            cd1[j]=dist(x,y,c[j],d[j]);
            cd2[j]=INF;
            for(int t=1;t<=k;t++)
                cd2[j]=min(cd2[j],dist(c[j],d[j],e[t],f[t]));
        }
        ld ans=INF;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                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]});
        cout<<fixed<<setprecision(10)<<ans<<"\n";
    }
} 
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
 
 
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
 
#define rep(i, n)    for(int i = 0; i < (n); ++i)
#define repA(i, a, n)  for(int i = a; i <= (n); ++i)
#define repD(i, a, n)  for(int i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define fill(a)  memset(a, 0, sizeof (a))
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
 
void pre(){
 
 
}
int sum = 0;
ld dist(pii x,pii y){
	x.fst-=y.fst,x.snd-=y.snd;
	return sqrt(1ll*x.fst*x.fst+1ll*x.snd*x.snd);
}
void solve(){
	int x,y,n,m,k;
	scanf("%d %d\n",&x,&y);
	scanf("%d %d %d\n",&n,&m,&k);
	assert(x>=0&&y>=0&&x<=1e9&&y<=1e9);
	assert(min({n,m,k})>=1&&max({n,m,k})<=5000);
	sum+=n+m+k;
	assert(sum<=15000);
	vector<pii> v[3];
	rep(i,n){
		int a,b;scanf("%d %d\n",&a,&b);
		assert(min(a,b)>=0&&max(a,b)<=1e9);
		v[0].pb({a,b});
	}
	rep(i,m){
		int a,b;scanf("%d %d\n",&a,&b);
		assert(min(a,b)>=0&&max(a,b)<=1e9);
		v[1].pb({a,b});
	}
	rep(i,k){
		int a,b;scanf("%d %d\n",&a,&b);
		assert(min(a,b)>=0&&max(a,b)<=1e9);
		v[2].pb({a,b});
	}
	vector<ld> v0,v1,v2;
	rep(i,n){
		ld cur = 4e9;
		rep(j,m){
			cur = min(cur,dist(v[0][i],v[1][j])+dist(mp(x,y),v[1][j]));	
		}
		v0.pb(cur);
	}
	rep(j,m){
		ld cur = 4e9;
		rep(i,n){
			cur = min(cur,dist(v[0][i],v[1][j])+dist(mp(x,y),v[0][i]));	
		}
		v1.pb(cur);
	}
	ld ans = 1e10;
	rep(i,k){
		rep(j,m){
			ans = min(ans,dist(v[2][i],v[1][j])+v1[j]);	
		}
		rep(j,n){
			ans = min(ans,dist(v[2][i],v[0][j])+v0[j]);	
		}
	}
	cout<<setprecision(20)<<ans<<'\n';
}
 
int main() {
	cin.sync_with_stdio(0); cin.tie(0);
	cin.exceptions(cin.failbit);
	pre();
	int q;
	scanf("%d\n",&q);
	assert(q>=1&&q<=5000);
	rep(i,q) solve();
	return 0;
}
Editorialist's Solution
#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef long double ld;
 
#define F first
#define S second
 
const int MAXN = 5e3 + 10;
 
int n[3];
pii p[3][MAXN];
ld best[2][MAXN];
 
ld dist(pii a, pii b){
	return sqrt(1ll*(a.F-b.F)*(a.F-b.F) + 1ll*(a.S-b.S)*(a.S-b.S));
}
 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(12);
 
	int te;	cin >> te;
	while (te--){
		int x, y; cin >> x >> y;
		cin >> n[0] >> n[1] >> n[2];
		for (int w = 0; w < 3; w++)
			for (int i = 0; i < n[w]; i++)
				cin >> p[w][i].F >> p[w][i].S;
 
		for (int w = 0; w < 2; w++)
			for (int i = 0; i < n[w]; i++) {
				best[w][i] = 3e18;
				for (int j = 0; j < n[2]; j++)
					best[w][i] = min(best[w][i], dist(p[w][i], p[2][j]));
			}
 
		ld ans = 1e18;
		for (int i = 0; i < n[0]; i++)
			for (int j = 0; j < n[1]; j++)
				ans = min({ans, dist({x, y}, p[0][i])
						+ dist(p[0][i], p[1][j])
						+ best[1][j], 
						dist({x, y}, p[1][j])
						+ dist(p[1][j], p[0][i])
						+ best[0][i]});
		cout << ans << "\n";
	}
	return 0;
}
6 Likes

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

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

Can anyone see this above two solution and tell me why only just putting an if condition resulted in converting partly solved solution to fully solved solution?

1 Like

#include<bits/stdc++.h>
#include <boost/functional/hash.hpp>
using namespace std;

#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long long int ll;
typedef long double ld;
ld Distance(ll x,ll y,ll a,ll b)
{
ll ans = ll(pow(x-a,2))+ll(pow(y-b,2));
return ld(sqrt(ans));
}

void TakeInput(pair<ll,ll>* points,ll size)
{
ll a,b;
for(ll i=0;i<size;i++)
{
cin>>a>>b;
points[i].first = a;
points[i].second = b;
}
}

void GetDistance(pair<ll,ll>* firstset,pair<ll,ll>* thirdset,ll n,ll k,unordered_map<pair<ll,ll>,ld, boost::hash<pair<ll, ll>>>& AK)
{
for(ll i=0;i<n;i++)
{
ll a = firstset[i].first;
ll b = firstset[i].second;
pair<ll,ll> point = firstset[i];
AK[point] = 1e12;
ll x,y;
for(ll j=0;j<k;j++)
{
ll c = thirdset[j].first;
ll d = thirdset[j].second;
ld dist = Distance(a,b,c,d);
if(AK[point]>dist)
{
AK[point] = dist;
x = c;
y = d;
}
}
// cout<<a<<" “<<b<<” “<<x<<” “<<y<<” "<<AK[point]<<endl;
}
}

void GetDistanceWithXY(pair<ll,ll>* firstset,unordered_map<pair<ll,ll>,ld, boost::hash<pair<ll, ll>>>& AXY,ll n,ll x,ll y)
{
ll a,b;
for(ll i=0;i<n;i++)
{
a = firstset[i].first;
b = firstset[i].second;
ld dist = Distance(a,b,x,y);
AXY[firstset[i]] = dist;
// cout<<a<<" “<<b<<” “<<AXY[firstset[i]]<<endl;
}
}
int main()
{
ll t;
cin>>t;
while(t–)
{
//MinDistance = 1e18;
ll n,m,k;
ll x,y;
cin>>x>>y;
cin>>n>>m>>k;
pair<ll,ll>* firstset = new pair<ll,ll>[n];
pair<ll,ll>* secondset = new pair<ll,ll>[m];
pair<ll,ll>* thirdset = new pair<ll,ll>[k];
TakeInput(firstset,n);
TakeInput(secondset,m);
TakeInput(thirdset,k);
unordered_map<pair<ll,ll>,ld, boost::hash<pair<ll, ll>>> AK;
unordered_map<pair<ll,ll>,ld, boost::hash<pair<ll, ll>>> BK;
unordered_map<pair<ll,ll>,ld, boost::hash<pair<ll, ll>>> AXY;
unordered_map<pair<ll,ll>,ld, boost::hash<pair<ll, ll>>> BXY;
//cout<<“First\n”;
GetDistance(firstset,thirdset,n,k,AK);
// cout<<endl;
// cout<<“Second\n”;
GetDistance(secondset,thirdset,m,k,BK);
// cout<<endl;
// cout<<“Third\n”;
GetDistanceWithXY(firstset,AXY,n,x,y);
// cout<<endl;
// cout<<“Fourth\n”;
GetDistanceWithXY(secondset,BXY,m,x,y);
ld MinDistance = 1e18;
ll a,b,c,d;
// cout<<“CROSS\n”;
for(ll i=0;i<n;i++)
{
a = firstset[i].first;
b = firstset[i].second;
for(ll j=0;j<m;j++)
{
c = secondset[j].first;
d = secondset[j].second;
ld dist1 = AXY[firstset[i]]+Distance(a,b,c,d)+BK[secondset[j]];
// cout<<a<<” “<<b<<” “<<c<<” “<<d<<” “<<dist1<<endl;
ld dist2 = BXY[secondset[j]]+Distance(c,d,a,b)+AK[firstset[i]];
// cout<<a<<” “<<b<<” “<<c<<” “<<d<<” "<<dist2<<endl;
MinDistance = min(MinDistance,min(dist1,dist2));
}
}
cout<<fixed<<setprecision(10)<<MinDistance<<endl;

}

}

I kept getting tle for the last case of subtask 2. Can anyone tell the reason? i did the same which has been explained. first I have found out the nearest point present in the set C for everypoint present in the set A and B. Then I did A x B which will take O(NxM) to find out the points between two A and B and then check find out the distance considering A set point is the starting and B set point is followed by a point present in set C and vice versa.

If you divide the points into zones, the closest point in C to each point in A and B can generally be found much faster. I say generally because there may be a corner case in which most of the points in C are in the same zone.

In addition, the use of zones means that there is generally no need to visit every point in A and every point in B.

In my solution https://www.codechef.com/viewsolution/27762936 I missed precalculation of the closest point in C to each point in B and in A, but instead calculated the closest point every time needed. It still took only 0.05 seconds.

4 Likes

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

I understand why my above code gets TLE for large testcases, but I can’t see why I’m getting a wrong answer for Task #4. I tried generating random testcases, but that didn’t help. What is wrong with my code?

don’t past full code,provide code link.

2 Likes

does my approach means that i did not understand the problem correctly and why is it wrong ??
https://www.codechef.com/viewsolution/27746222

Using skip conditions in brute force worked well for me. The idea was I declared the the distance from X->A->B->C as minimum distance D and I skipped the iterations where dist(X->A) > D or dist(X->A->B) > D and same for the case if the person goes X->B->A->C that I feel significantly reduced the computation time and gave me an AC.

Solution: https://www.codechef.com/viewsolution/27833310

2 Likes

Why my solution is giving wrong answers? @vladprog @watcher
https://www.codechef.com/viewsolution/27881729

Really great approach indeed. Although I wasn’t able to understand since you’re using zones, how did you handled overlapping between different zones.

I can’t understand the editorial.

4 Likes

Hi All,

https://www.codechef.com/viewsolution/27877993 O(n3)
https://www.codechef.com/viewsolution/27881805 O(n2)

Please help I am getting TLE for my o(n2) solution.

Accepted in O(n^3)
check it here

The zones themselves don’t overlap. To find the closest point to a given point:

  1. Identify the zone containing the given point.
  2. Find the closest point in the zone, if any.
  3. If no closest point, search in adjacent zones.
  4. Compare the distance to the closest point to the distance to each of the adjacent zones.
  5. If the closest point could be in any of the adjacent zones, search them too.
  6. If there is no point in this zone or any adjacent zone, search the whole lot instead.

For details, see function public Point PointArray.Closest(Point here, ref double distance) starting at line 235 in my submission, from link in my original post.

Another speed-up which is in my solution, which I did not mention previously, is that at the start I search for closest point in A, then closest point in B, then in C, and similarly in the order B, A, C. The smaller of the total distances in these two routes gives a possible solution. Then during the main search as soon I find a distance greater than the best so far, I don’t look further. For example suppose that the shortest total distance so far is D, then when I find a point in A that is further than D from the start point, there is no need to consider this point in A further.

2 Likes

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