Codeforces Round #287 Problem E - Breaking Good

Problem Statement:
507E - Breaking Good

Solution:
[Off topic: btw, Breaking Bad is damn awesome!]
This problem employs an interesting trick using Dijkstra Algorithm, which is quite intuitive to discover.

First suppose there are no broken roads, i.e. every edges are valid edges. In this case, we can simply run a BFS to find the shortest path between node 1 (city) and node N (headquarter), and for all other roads not in this path, we just blow them up. However, in the problem, we can have roads which must be repaired before it can be used. Hence naturally BFS is not applicable to this case anymore and we need something else to account for the cost of repairing a road. Yet, we also need the property that the shortest path will still have the same length as the ones that are produced if we are to run BFS.

Codeforces 449B - Jzzhu and Cities

Problem Statement:
449B - Jzzhu and Cities

Solution:
An interesting graph problem. In both Bellman-Ford and Dijkstra single source shortest path algorithms, we have the concept of "relaxed" edges, in which intuitively can be viewed this way: We are given a set of balls connected together with strings. If we choose a ball as the "source" and pick it up, other balls will be hanging with some strings tight and some strings slack. The tight strings are the "relaxed" edges in single source shortest path algorithm. Those which are not relaxed can actually be removed from the shortest path graph.

Codeforces Round 270 Problem D - Design Tutorial: Inverse The Problem

Problem Statement:
472D - Design Tutorial: Inverse The Problem

Solution:
Pretty interesting problem. Given a matrix of distances between nodes dist[u][v], return a weighted tree that satisfies this matrix. Here is my approach (I believe this is not the most efficient (or even efficient) or clever idea, but it worked :P)

Topcoder SRM 638 Div. 1 Hard - CandleTimer

Follow up to this post

Problem Statement:
Topcoder SRM 638 Div. 1 HARD - CandleTimer

Solution:
Just solved this problem, and I must say that this problem is very challenging (at least for me) in a sense that there are quite a lot of stuff going on. The way the candles are burnt rings some bells to the intuition behind Dijkstra algorithm, and indeed the way to solve this problem is through some modification of Dijkstra.

a bit of graph dp: SPOJ - ROADS

Problem Statement:
SPOJ - ROADS

Summary:
Given a directed graph where each edge has attributes cost and distance, find the shortest distance possible from the vertex \(v_1\) to \(v_N\) while the total cost is at most \(K\).
\(N \leq 100, K \leq 10^4, |E| \leq 10^4\). Costs can be zero, and two nodes may be connected by multiple edges.

Solution:
I have two ways of solving this problem, firstly with a more intuitive and straight forward dynamic programming approach:
Let \(S(c, n)\) be the shortest distance possible to reach vertex n from vertex 1 incurring at most c total cost. Then we have S(c, n) = min [for each edge v into n] { S(c-1, n), S(c - cost[v to n]) + dist[v to n] }
But we have to take care of the case where \(c = 0\), which can be treated as a special case. We store another information of minimum distances between vertices which requires 0 cost to travel to. Then for each \(n\), after taking care of updates required for all \(c \neq 0\), we check each pairs of nodes if they are connected using 0 cost path, and update the distances accordingly.
This approach takes \(O(K(N^2+|E|))\) time, and I am surprised that it is accepted by the judge.

The better solution is using Dijkstra algorithm by modeling vertices as representing states state[vertex, total cost already incurred]. We can have the similar table \(D(n, c)\) representing the shortest distance required to travel from state[1, 0] to state[n, c]. Implementation using STL priority_queue is blazingly fast but take note that we need to terminate the algorithm once we have vertex N on top of our priority_queue since the corresponding distance is indeed the shortest distance.

a bit of graph: Dijkstra's Shortest Path Algorithm

Problem Statement:
Given a undirected graph with non-negative weighted edges, a starting point s, and a destination t, find the path with minimum weight.

Dijkstra's Algorithm:
A greedy algorithm can be devised to solve this problem. Suppose we already have a minimum path using several nodes. Then the intuitive thing to do is to add a node to the last node in our path such that its weight is the lowest. This is basically the intuition behind Dijkstra's algorithm, which resembles Prim's algorithm for Minimum Spanning Tree. However, there are a few important details which ensure the correctness of the algorithm:

Definition:
s: starting point
t: destination
d[i]: array of distances from s
w(u,v): weigh of edge u to v

1. Initially, we have an array of distances d[i] which values are all infinity. This means that we do not know yet whether the node i is reachable from our starting point. However, we do know that s is reachable (since it's our starting point anyway) so d[s] = 0 and d[i] = INF for i != s.

2. For an edge with nodes u and v at its end points, an important operation called relax(u,v) is performed as follows: if d[u] > d[v] + w(u,v) then update d[u] = d[v] + w(u,v) (we can also say that the edge u-v is relaxed).

3. Let S be the set of nodes in which the distance from s has already known (that is, if u in S, then d[u] is guaranteed to be the total weight of the minimum path between s and u). At first, S = {s}. Then for each element in S, we examine its edges and perform the relax(u,v) operation.

4. After we have iterated through all element in S, we choose the node that is not yet inside S which has the smallest d[i], and add it in S (hence the greedy choice!). If the node happens to be t, then we've found d[t] which is the total weight of the minimum path from s (which is how we defined S earlier). If the node is not t, then repeat 3 until we cannot add anymore nodes into S in which case t is not reachable from s.

It remains to prove that in step 4, the node that we added to S indeed has the property that d[i] is the value of its minimum weight path from s, and the proof can be very interesting :D.

The implementation of this algorithm is usually done using a heap data structure such as priority queue to choose the minimum node in step 4, although a normal array can also be used if the number of nodes are not too big. Below is a sample implementation in C++:

typedef pair<int, int> pii;

struct nd{
 int v; //neighboring vertex
 int w; //weight of edge u-v
};

vector<vector<nd> > G;
vector<int> p; //parent attr
vector<int> d; //dist attr

void init(int N){//no of nodes, no of edges
 G = vector<vector<nd> >(N+1);
 p = vector<int>(N+1);
 d = vector<int>(N+1);
 for(int i=0;i<N+1;++i)
  p[i]=-1, d[i]=MAX;
}

void djikstra(int s, int f){ //starting pt
 priority_queue<pii> q;
 d[s]=0;
 p[s]=-1;
 q.push(make_pair(d[s] ,s));
 while(!q.empty()){
  pii cur = q.top();
  q.pop();
  int u = cur.second;
  int nE = G[u].size();
  for(int i=0;i<nE;++i){
   int v = G[u][i].v;
   int w = G[u][i].w;
   if(d[v] > d[u] + w){
    d[v] = d[u]+w;
    p[v] = u;
    q.push(make_pair(-d[v],v));
   }
  }
 }
}