TC SRM446 D1 500 (AntOnGraph)

The problem statement can be accessed via:
http://www.topcoder.com/stat?c=problem_statement&pm=10516

The problem depicts an ant which travels around a weighted directed graph. The objective of this problem is to determine the maximum score in which the ant can have given that the score is defined by the sum of all the edge weights it travels. The ant is given at most timeLimit seconds to travel (it can use less than this) and each second is defined by a mandatory set of stepsPerSecond adjacent vertex traversals within the graph. An additional constraint is that the ant must end at vertex 1 at the end (the ant starts at vertex 0), it is also possible that the ant can't reach the vertex at the right interval in time or that the vertex is inaccessible.

Given the constraints it's rather obvious we can't simulate it by time (as it'll easily exceed the time limit). There are several clues in this problem which leads to an elegant solution - firstly, we must move exactly stepsPerSecond traversals each second. What does this mean? It means that we can compute the cost of moving exactly this many traversals per second. Let's assume timeLimit = 1 second, then the answer is simply the greatest value (which could be negative) from vertex 0 to vertex 1 using exactly stepsPerSecond vertex traversals.

How do we compute this? We can think of it in a dynamic programming manner. Let's define M(x,i,j) to be the maximum value we can achieve using exactly x steps from vertex i to vertex j. If this is unreachable then we define M(x,i,j) to be negative infinity. So now we define the relationship between step x and step x-1:

M(x,i,j) = max { M(x-1,i,k) + M(1,k,j) }       
     iff (i,k) and (k,j) are edges (not negative infinity)

We can iteratively compute this from 0 to stepsPerSecond traversals and the maximum score we can get is simply M(stepsPerSecond, 0, 1). Now we need to somehow incorporate this into the case where timeLimit > 1. We can now try and relate timeLimit and timeLimit-1 seconds. It can be seen that the optimal/maximal moves does not change inside each individual timeLimit (the stepsPerSecond matrix). To see this, let's say we are on vertex x and we just finished using the timeLimit-1 interval. We now wish to go from vertex x to vertex y on the next interval. Then the optimal score is simply M(stepsPerSecond, x, y) + currentScore. We simply reused the matrix we computed since it forms a "basic indivisible unit" due to the constraint that each second must have exactly stepsPerSecond vertex traversals.

We now attempt to define a recurrence between seconds (and not specific vertex traversals) using the matrix M as a basic unit:

N(t,i,j) = max { M(t-1,i,k) + M(1,k,j) }
     iff (i,k) and (k,j) are edges

There is a problem though, since the maximum timeLimit is 1 billion - this recurrence is too slow. To optimise it we need to make one observation. With basic expansion:

N(t,i,j) = N(1,i,k) + N(1,k,l) + N(1,l,m) + ... + N(1,o,j)   (t additions)

Then we can begin collapsing:

N(t,i,j) = N(2,i,l) + ... + N(2,n,j)   (t/2 additions)

etc.

As you can see we can recursively define N(t,i,j) in terms of additions of smaller values. Note that we can define it much like how you do exponentation squaring:

N(t,i,j) = N(t/2,i,k) + N(t/2,k,j)            iff (t is even)
         = N(t/2,i,k) + N(t/2,k,m) + N(1,m,j) otherwise

With this we can compute the maximal score for exactly "t" seconds. We need to make a minor modification to allow us to compute the correct score in case we don't need to use all of the allotted "t" seconds. Basically we need to add a dummy edge of 0 score going from the last vertex to itself (self loop) so it's a possible decision to terminate early. Given the recurrence and the self-loop modification on the finishing vertex we can simply implement:

class AntOnGraph {
public:
 string maximumBonus(vector <string>, vector <string>, 
   vector <string>, int, int);
};

long long tab[51][51];

#define INF (1LL<<50)

vector<vector<long long> > mat(const vector<vector<long long> 
    >& lhs, const vector<vector<long long> >& rhs) {
 vector<vector<long long> > res = vector<vector<long long> 
     >(lhs.size(), vector<long long>(lhs.size(), -INF));
 for (int i = 0; i < lhs.size(); i++) {
  for (int j = 0; j < lhs[0].size(); j++) {
   for (int k = 0; k < lhs.size(); k++) {
    if (lhs[i][k] > -INF && rhs[k][j] > -INF)
     res[i][j] >?= (lhs[i][k] + rhs[k][j]);
   }
  }
 }
 return res;
}

vector<vector<long long> > pow(const vector<vector<long long> 
    >& vec, long long n) {
 vector<vector<long long> > res;
 if (n == 1) {
  return vec;
 }
 vector<vector<long long> > base = pow(vec, n/2);
 res = mat(base, base);
 if (n % 2 != 0) {
  return mat(res, vec);
 }
 return res;
}

string AntOnGraph::maximumBonus(vector <string> p0, vector <string> p1, 
    vector <string> p2, int stepsPerSecond, int timeLimit) {
 string res;
 vector<vector<long long> > vec = vector<vector<long long> >(p0.size()
   ,vector<long long>(p0.size(),0));
 for (int i = 0; i < p0.size(); i++) {
  for (int j = 0; j < p0[i].size(); j++) {
   vec[i][j] = ((p0[i][j] - '0') * 100 + (p1[i][j] - '0') * 10 + (p2[i][j] 
       - '0')) - 500;
   if (vec[i][j] == -500) vec[i][j] = -INF;
  }
 }
 vector<vector<long long> > M = pow(vec, stepsPerSecond);
 if (M[1][1] < 0) M[1][1] = 0;
 vector<vector<long long> > M2 = pow(M, timeLimit);
 ostringstream oss; oss << M2[0][1];
 res = oss.str();
 return M2[0][1] == -INF ? "IMPOSSIBLE" : res;
}