Solution 4 for Scaler Topics Fortnightly Contest - 27
Spaceship on Mission
This article is part of the Scaler Topics Fortnightly Contest - 27
Transform Your Career
Choose from our industry-leading programs designed for career success
Modern Software and AI Engineering Program
Master full-stack development with AI integration
+1000 moreModern Data Science and ML with specialisation in AI
Advanced data science techniques with AI specialization
+1000 moreAdvanced AIML with Specialisation in Agentic AI
Deep dive into AIML with focus on Agentic systems
+1000 moreDevOps, Cloud & AI Platform Engineering
Build and manage AI-powered cloud infrastructure
+1000 moreAI Engineering Advanced Certification by IIT-Roorkee
Premier AI engineering certification from IIT-Roorkee
Solution Approach
Let x1= A[0] , x2= A[2] , x3= A[4] , y1=A[1], y2=A[3], y3=A[5] Let d(P1,P2) be the Manhattan distance between points P1=(x1,y1) and P2=(x2,y2). Then d(P1,P2)=|x1−x2|+|y1−y2|.
Note that if you are going from P1 to P2 (or to P3) along the shortest path, the Manhattan distance will be decreasing with each move. So we have to find the next cell that is closer to both P2 and P3.
Now note that if they are in the bounding box of cells P2 and P3 then there are no such “next cell”, since d(X,P2)+d(X,P3) is constant and equal to d(P1,P2) if X is in the bounding box.
Let’s look at the total distance spaceship will travel: from one side it’s d(P1,P2)+d(P1,P3). But from the other side it’s 2⋅d(P1,X)+d(X,P2)+d(X,P3).
So,d(P1,X)=(d(P1,P2)+d(P1,P3)−(d(X,P2)+d(X,P3)))/2 .But since d(X,P2)+d(X,P3)=d(P2,P3) whichever X is chosen we can calculate answer as (d(P1,P2)+d(P1,P3)−d(P2,P3))/2+1 where +1 is because we are talking about cells P1, P2 and P3 and not just points.
Time complexity : O(1) Space complexity : O(1)
C++ Implementation
Java Implementation
Scaler Placement Report and Statistics
Scaler learners achieved 2.5x salary growth with average post-Scaler CTC reaching ₹23L.
Google
Amazon
Microsoft
Flipkart
Adobe1200+ more
