Optimizing a dynamic programming solution for "Oil Well"

Question

I'm trying to solve the Oil Well problem on Hackerrank using dynamic programming and it works. However, it times out for some of the test cases. I wanted to know how this program can be improved so that it runs faster.

The challenge is, given a matrix \$M\$ of size \$r \times c\$ (at most \50ドル \times 50\$), where each \$M_{x,y}\$ is either 0 or 1, find the minimum cost path \$E\$ for a spanning tree that connects all the entries where \$M_{x,y} = 1\$. The cost metric is based on ACME distance: \$\max(\left|x - x_1\right|, \left|y - y_1\right|)\$ where \$x, y\$ is the position of the existing wells, and \$x_1, y_1\$ is the position of the new well.

My basic idea is:

$$f(\mathrm{vertices}) = \min( \max(v_i \to \{\mathrm{vertices} - v_i\}) + f(\mathrm{vertices} - v_i))$$

for all vertices \$v_i\$.

The Hackerrank editorial shows a different logic but I'm trying to optimize my solution.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <climits>
#include <map>
#include <sstream>
using namespace std;
map<string,int> cache;
map<pair<int,int>,int> pd;
string has(vector<int>& vertices)
{
 ostringstream s;
 for(int i = 0; i < vertices.size(); i++)
 {
 s << vertices[i] << "|";
 }
 return s.str();
}
int dist(vector<int>& vertices)
{
 if(vertices.size() <= 1)
 return 0;
 string h = has(vertices);
 if(cache.count(h) != 0) {
 return cache[h];
 }
 int mind = INT_MAX;
 for(int i = 0; i < vertices.size(); i++) {
 int iv = vertices[i]; 
 int x = 0;
 for(int j = 0; j < vertices.size(); j++) {
 int ov = vertices[j]; 
 x = max(x,pd[make_pair(min(iv,ov),max(iv,ov))]);
 } 
 vertices.erase(vertices.begin()+i);
 mind = min(x + dist(vertices), mind);
 vertices.insert(vertices.begin()+i,iv);
 }
 cache[h]=mind;
 return mind;
}
int main() {
 int r, c;
 cin >> r >> c;
 vector<pair<int,int>> vertices;
 int a;
 for(int i = 0; i < r; i++) {
 for(int j = 0; j < c; j++) {
 cin >> a;
 if(a) {
 vertices.push_back(make_pair(i,j));
 }
 }
 }
 vector<int> vv;
 for(int i = 0; i < vertices.size(); i++) {
 vv.push_back(i);
 for(int j = i+1; j < vertices.size();j++) {
 pair<int,int> ip = vertices[i];
 pair<int,int> op = vertices[j];
 int d = max(abs(ip.first - op.first),abs(ip.second - op.second));
 pd[make_pair(i,j)] = d;
 }
 }
 cout << dist(vv) << endl;
 return 0;
}

• nwp: The site does not display the challange for me.
• ssh: @nwp I clicked on the same hyperlink in your comment but it shows me the problem. The question has been edited to include the problem.

Answer 1

It is not possible to make this solution fast enough. The number of states in your dynamic programming is O(2^numberOfVertices)(the number of subsets of a set with numberOfVertices elements), which is 2^2500 in the worst case under given constraints. So a more efficient algorithm is required.