# PHCUL - Editorial

**URL:** <https://discuss.codechef.com/t/phcul-editorial/43712>\
**Category:** editorial\
**Tags:** challenge, editorial, nov19, watcher\
**Created:** [November 4, 2019, 7:31pm UTC](https://discuss.codechef.com/t/phcul-editorial/43712 "2019-11-04T19:31:23Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![watcher](https://discuss.codechef.com/user_avatar/discuss.codechef.com/watcher/32/3653_2.png) [@watcher](https://discuss.codechef.com/u/watcher)\
**Post date:** [November 4, 2019, 7:31pm UTC](https://discuss.codechef.com/t/phcul-editorial/43712/1 "2019-11-04T19:31:23Z")

</div>

# PROBLEM LINK:

[Practice](https://www.codechef.com/problems/PHCUL)  
[Div-2 Contest](https://www.codechef.com/NOV19B/problems/PHCUL)  
[Div-1 Contest](https://www.codechef.com/NOV19A/problems/PHCUL)

_ **Author:** _[Vlad](https://www.codechef.com/users/vladprog)  
_ **Tester:** _[Yash Chandnani](https://www.codechef.com/users/yash_chandnani)  
_ **Editorialist:** _[Michael Nematollahi](https://www.codechef.com/users/watcher)

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

---

<div class="post-metadata">

**Author:** ![vickyvanshaj](https://discuss.codechef.com/user_avatar/discuss.codechef.com/vickyvanshaj/32/25967_2.png) [@vickyvanshaj](https://discuss.codechef.com/u/vickyvanshaj)\
**Post date:** [November 11, 2019, 8:53pm UTC](https://discuss.codechef.com/t/phcul-editorial/43712/2 "2019-11-11T20:53:50Z")

</div>

[https://www.codechef.com/viewsolution/27801062](https://www.codechef.com/viewsolution/27801062)

[https://www.codechef.com/viewsolution/27874701](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?

---

<div class="post-metadata">

**Author:** ![gourab19964u](https://discuss.codechef.com/user_avatar/discuss.codechef.com/gourab19964u/32/29306_2.png) [@gourab19964u](https://discuss.codechef.com/u/gourab19964u)\
**Post date:** [November 11, 2019, 9:54pm UTC](https://discuss.codechef.com/t/phcul-editorial/43712/3 "2019-11-11T21:54:17Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![david\_s](https://discuss.codechef.com/user_avatar/discuss.codechef.com/david_s/32/247319_2.png) [@david\_s](https://discuss.codechef.com/u/david_s)\
**Post date:** [November 12, 2019, 2:45am UTC](https://discuss.codechef.com/t/phcul-editorial/43712/4 "2019-11-12T02:45:58Z")

</div>

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 [CodeChef: Practical coding for everyone](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.

---

<div class="post-metadata">

**Author:** ![violetval](https://discuss.codechef.com/user_avatar/discuss.codechef.com/violetval/32/24644_2.png) [@violetval](https://discuss.codechef.com/u/violetval)\
**Post date:** [November 12, 2019, 7:16am UTC](https://discuss.codechef.com/t/phcul-editorial/43712/5 "2019-11-12T07:16:21Z")

</div>

[https://www.codechef.com/viewsolution/27876385](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?

---

<div class="post-metadata">

**Author:** ![savaliya\_vivek](https://discuss.codechef.com/user_avatar/discuss.codechef.com/savaliya_vivek/32/4976_2.png) [@savaliya\_vivek](https://discuss.codechef.com/u/savaliya_vivek)\
**Post date:** [November 12, 2019, 8:04am UTC](https://discuss.codechef.com/t/phcul-editorial/43712/6 "2019-11-12T08:04:44Z")

</div>

don’t past full code,provide code link.

---

<div class="post-metadata">

**Author:** ![vinayskywalker](https://discuss.codechef.com/user_avatar/discuss.codechef.com/vinayskywalker/32/3653_2.png) [@vinayskywalker](https://discuss.codechef.com/u/vinayskywalker)\
**Post date:** [November 12, 2019, 9:29am UTC](https://discuss.codechef.com/t/phcul-editorial/43712/7 "2019-11-12T09:29:26Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![mohilllll](https://discuss.codechef.com/user_avatar/discuss.codechef.com/mohilllll/32/25488_2.png) [@mohilllll](https://discuss.codechef.com/u/mohilllll)\
**Post date:** [November 12, 2019, 9:35am UTC](https://discuss.codechef.com/t/phcul-editorial/43712/8 "2019-11-12T09:35:51Z")

</div>

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: [CodeChef: Practical coding for everyone](https://www.codechef.com/viewsolution/27833310)

---

<div class="post-metadata">

**Author:** ![striker22](https://discuss.codechef.com/user_avatar/discuss.codechef.com/striker22/32/123420_2.png) [@striker22](https://discuss.codechef.com/u/striker22)\
**Post date:** [November 12, 2019, 11:17am UTC](https://discuss.codechef.com/t/phcul-editorial/43712/9 "2019-11-12T11:17:19Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![alter123](https://discuss.codechef.com/user_avatar/discuss.codechef.com/alter123/32/6864_2.png) [@alter123](https://discuss.codechef.com/u/alter123)\
**Post date:** [November 12, 2019, 2:50pm UTC](https://discuss.codechef.com/t/phcul-editorial/43712/10 "2019-11-12T14:50:06Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![pankaj2kumar](https://discuss.codechef.com/user_avatar/discuss.codechef.com/pankaj2kumar/32/3653_2.png) [@pankaj2kumar](https://discuss.codechef.com/u/pankaj2kumar)\
**Post date:** [November 12, 2019, 3:40pm UTC](https://discuss.codechef.com/t/phcul-editorial/43712/11 "2019-11-12T15:40:33Z")

</div>

I can’t understand the editorial.

---

<div class="post-metadata">

**Author:** ![pawankotak](https://discuss.codechef.com/user_avatar/discuss.codechef.com/pawankotak/32/228013_2.png) [@pawankotak](https://discuss.codechef.com/u/pawankotak)\
**Post date:** [November 12, 2019, 5:17pm UTC](https://discuss.codechef.com/t/phcul-editorial/43712/12 "2019-11-12T17:17:35Z")

</div>

Hi All,

[CodeChef: Practical coding for everyone](https://www.codechef.com/viewsolution/27877993) O(n3)  
[CodeChef: Practical coding for everyone](https://www.codechef.com/viewsolution/27881805) O(n2)

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

---

<div class="post-metadata">

**Author:** ![silent\_1](https://discuss.codechef.com/user_avatar/discuss.codechef.com/silent_1/32/26656_2.png) [@silent\_1](https://discuss.codechef.com/u/silent_1)\
**Post date:** [November 12, 2019, 5:25pm UTC](https://discuss.codechef.com/t/phcul-editorial/43712/13 "2019-11-12T17:25:11Z")

</div>

Accepted in O(n^3)  
[check it here](https://www.codechef.com/viewsolution/27724287)

---

<div class="post-metadata">

**Author:** ![david\_s](https://discuss.codechef.com/user_avatar/discuss.codechef.com/david_s/32/247319_2.png) [@david\_s](https://discuss.codechef.com/u/david_s)\
**Post date:** [November 13, 2019, 12:32am UTC](https://discuss.codechef.com/t/phcul-editorial/43712/14 "2019-11-13T00:32:40Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![alter123](https://discuss.codechef.com/user_avatar/discuss.codechef.com/alter123/32/6864_2.png) [@alter123](https://discuss.codechef.com/u/alter123)\
**Post date:** [November 13, 2019, 3:09am UTC](https://discuss.codechef.com/t/phcul-editorial/43712/15 "2019-11-13T03:09:46Z")

</div>

Thank you so much.

---

<div class="post-metadata">

**Author:** ![savaliya\_vivek](https://discuss.codechef.com/user_avatar/discuss.codechef.com/savaliya_vivek/32/4976_2.png) [@savaliya\_vivek](https://discuss.codechef.com/u/savaliya_vivek)\
**Post date:** [November 13, 2019, 4:03am UTC](https://discuss.codechef.com/t/phcul-editorial/43712/16 "2019-11-13T04:03:03Z")

</div>

O(n^3) with 0.00 sec, wow 😜

---

<div class="post-metadata">

**Author:** ![savaliya\_vivek](https://discuss.codechef.com/user_avatar/discuss.codechef.com/savaliya_vivek/32/4976_2.png) [@savaliya\_vivek](https://discuss.codechef.com/u/savaliya_vivek)\
**Post date:** [November 13, 2019, 4:07am UTC](https://discuss.codechef.com/t/phcul-editorial/43712/17 "2019-11-13T04:07:22Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![hitman333](https://discuss.codechef.com/user_avatar/discuss.codechef.com/hitman333/32/3653_2.png) [@hitman333](https://discuss.codechef.com/u/hitman333)\
**Post date:** [November 13, 2019, 8:31am UTC](https://discuss.codechef.com/t/phcul-editorial/43712/18 "2019-11-13T08:31:53Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![pawankotak](https://discuss.codechef.com/user_avatar/discuss.codechef.com/pawankotak/32/228013_2.png) [@pawankotak](https://discuss.codechef.com/u/pawankotak)\
**Post date:** [November 13, 2019, 9:03am UTC](https://discuss.codechef.com/t/phcul-editorial/43712/19 "2019-11-13T09:03:01Z")

</div>

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

[https://www.codechef.com/viewsolution/27888449](https://www.codechef.com/viewsolution/27888449)

---

<div class="post-metadata">

**Author:** ![rohithdsouza](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@rohithdsouza](https://discuss.codechef.com/u/rohithdsouza)\
**Post date:** [November 13, 2019, 9:36am UTC](https://discuss.codechef.com/t/phcul-editorial/43712/20 "2019-11-13T09:36:55Z")

</div>

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](https://www.codechef.com/viewsolution/27869846)

[Next page](https://discuss.codechef.com/t/phcul-editorial/43712.md?page=2)