Search for the minimum required gas container volume

Question

I found this problem somewhere in the competition and still could not find a solution.

There are N cities with coordinates (x, y). I need to go first to the city and get to the second city. Each city has a gas station. Therefore, I must find the minimum required volume of a gas cylinder to reach the last city. For instance:

Input: 3 17 4 19 4 18 5 Output: 1.414 

Here is my way: 1->3->2

I use a simple brute force method, but it is so slow. How can I optimize my code? Maybe there is a better solution?

 #include <iostream> #include <algorithm> #include <stack> #include <math.h> #include <cstring> #include <iomanip> #include <map> #include <queue> #include <fstream> using namespace std; int n, used[203]; double min_dist; struct pc { int x, y; }; pc a[202]; double find_dist(pc a, pc b) { double dist = sqrt( (ax - bx)*(ax - bx) + (ay - by)*(ay - by) ); return dist; } void functio(double d, int used[], int k, int step) { used[k] = 1; if(k == 1) { if(d < min_dist) { min_dist = d; } used[k] = 0; return; } for(int i = 1; i < n; ++i) { if(i != k && used[i] == 0) { double temp = find_dist(a[k], a[i]); if(temp > d) { if(temp < min_dist) functio(temp, used, i, step + 1); } else { if(d < min_dist) functio(d, used, i, step + 1); } } } used[k] = 0; } int main() { cin >> n; for(int i = 0; i < n; ++i) cin >> a[i].x >> a[i].y; min_dist = 1000000; memset(used, 0, sizeof(used)); functio(0, used, 0, 0); cout << fixed << setprecision(3) << min_dist << endl; } 

Answer 1

A minimal spanning tree has the neat property of encoding all paths between vertices that minimize the length of the longest edge on the path. For the Euclidean MST, you can calculate the Delaunay triangulation, and then run your favorite O (m log n) -time algorithm (on a graph with edges m = O (n)) for the total running time O (n log n). In addition, you can run Prim with a naive priority queue for the O (n ^ 2) -time algorithm with a good constant (especially if you use SIMD).

Answer 2

So, what are you trying to optimize in your algorithm, this is the longest distance that you travel between two cities. Because how big your gas bottle should be. This is the shortest path option because you are trying to optimize the enire path length.

I think you could get away from this:

• make a list of edges. (distance between each pair of cities)

• remove the longest edge from the list if this does not make the destination inaccessible.

• as soon as you can no longer remove the longest path, this means that this is your limiting factor when moving to your destination. The rest of the route no longer matters.

Then, at the end, you should have a list of edges that make up the path between the source and destination.

I have not proved that this solution is optimal, so there are no guarantees. But consider the following: if you delete the longest path, there are only shorter paths, so the maximum distance between the legs will not increase.

---

About complexity, time complexity O(n log n) , because you need to sort the edges.
Memory Complexity - O (n ^ 2)

This is probably not the most efficient algorithm, since it is a graph algorithm and does not use the fact that cities are on the Euclidean plane. There is probably some kind of optimization ...

Answer 3

You can reduce the time complexity to O(n^2*log(n)) using a binary search that will work for 1 second. The idea of ​​a binary search is that if we can reach city 2 from city 1 using volume x , there is no need to check a larger container. If we cannot use this, we need more than x volume. To check if we can get to city 2 using x volume, you can use BFS . If two cities are at a distance x from each other, then it can be moved from one to the other, and we can say that they are connected by edges.

the code:

 int vis[203]; double eps=1e-8; struct pc { double x, y; }; double find_dist(pc &a, pc &b) { double dist=sqrt((ax - bx)*(ax - bx) + (ay - by)*(ay - by)); return dist; } bool can(vector<pc> &v, double x) { // can we reach 2nd city with volume x int n=v.size(); vector<vector<int>> graph(n, vector<int>(n, 0)); // graph in adjacency matrix form // set edges in graph for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { if(i==j) continue; //same city double d=find_dist(v[i], v[j]); if(d<=x) graph[i][j]=1; // can reach from city i to city j using x volume } } // perform BFS memset(vis, 0, sizeof(vis)); queue<int> q; q.push(0); // we start from city 0 (0 absed index) vis[0]=1; while(!q.empty()) { int top=q.front(); q.pop(); if(top==1) return true; // can reach city 2 (1 in 0-based index) for(int i=0; i<n; i++) { if(top!=i && !vis[i] && graph[top][i]==1) { q.push(i); vis[i]=1; } } } return false; // can't reach city 2 } double calc(vector<pc> &v) { // calculates minimum volume using binary search double lo=0, hi=1e18; while(abs(hi-lo)>eps) { double mid=(lo+hi)/2; if(can(v, mid)) { hi=mid; // we need at most x volume } else{ lo=mid; // we need more than x volumer } } return lo; }