ACM ICPC World Finals -- UVa 208 Firetruck

Hello everyone,  I'm starting a new section on my blog related to solving UVa Online Judge programming problems. I recently picked up "From Baylor to Baylor" which includes several ACM ICPC World Finals questions, and their corresponding UVa numbers for you to submit your code to.

This question is the very first question you see if you open the book, Firetruck. Initially this may seem like a straightforward graph problem, and a solution that uses a form of backtracking/DFS would work and be correct. However, if you were to code this, you'll realize that this approach fails, not with wrong answer, but with Time Limit Exceeded.

 Why might this problem fail with TLE? I would guess that some of the input  leads to a very large path down a graph that gets you further and further away from the goal node, hence wasting a lot of precious computational time.Perhaps the graph is disconnected and iterating over all nodes is fruitless. So the idea here is to do a pre-processing step and find out which nodes are actually reachable from the goal. This way  we never visit the nodes that don't lead us towards the goal. We can accomplish this by doing a basic DFS from the destination:

void dfs(int n, int largest_node)
{
 visit[n] = true;
 for(int i  = 1; i <= largest_node; ++i)
 {
  if(matrix[n][i] && !visit[i])
   dfs(i,largest_node);

 }
}

So we know which nodes can lead us towards the goal, but the problem now is figuring out all the paths. Despite the fact that the program has to run fast, the clue here is that we need to find all possible paths and thus we will need a form of backtracking search. Luckily, we can prune unfruitful search paths early due to our pre-processing.  >The rest of the code is straightforward backtracking with the additional fact that we need to form our actual path, so we keep updating a string variable within the backtrack search so that when we reach the goal, we have the path formed. Another thing we need to consider is the fact that we cannot have cycles in our paths. If we choose to from node 1 to node 2 (1->2), we cannot have node 2 go back to node 1. So one way of doing it is to have a separate bool array which we constantly toggle, but the way I prefer is to use a bitmask, and toggling (using OR) whenever we choose to add a node to our path. This way we can check inclusion of node X by checking if bitmask & (1 << X) != 0. A 32-bit integer will have no problems storing every configuration, since the largest number possible formed would be (1 << 21) - 1. In the backtracking search, we only continue with nodes for which visit[x] == true, which we setup during the DFS. So here is our backtracking search routine:

void backtrack(int i, int largest_node,int dest, int bitmask,string cur)
{
 if(visit[i])
 {
  if(i == dest)
  {
   ++total;
   cout << cur << "\n";
   return;
  }
  else
  {
   for(int x = 1; x <= largest_node; ++x)
   {
    if(matrix[i][x] && !(bitmask & (1 << x)))
    {
     backtrack(x,largest_node,dest,bitmask | (1 << x),cur + " " + to_string(x));
    }
   }
  }


 }
}

We initiate backtrack with backtrack(1,largest_node,destination,2,"1"); Why? The We will always start from streetcorner 1, so the backtrack must start with node 1, we've explained above why we need largest_node, its pretty intuitive as to why we need destination (psst.. it's where our backtrack routine should end), the bitmask starts at 2 because in binary it would be "00000010", so if we were to test if node 1 were in the current path, bitmask & (1 << 1) would yield us 1. For similar reasons, we start the string with "1", since we always start at 1.

So that's the meat and potatoes of our program, the only other things to code would be the actual input, memset()'ing the visit and matrix arrays, and such. Hopefully you understood this code snippet :) Here's the code I used to get Accepted from UVa,

#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
bool visit[22];
int matrix[22][22];
int total =0;
void backtrack(int i, int largest_node,int dest, int bitmask,string cur)
{
 if(visit[i])
 {
  if(i == dest)
  {
   ++total;
   cout << cur << "\n";
   return;
  }
  else
  {
   for(int x = 1; x <= largest_node; ++x)
   {
    if(matrix[i][x] && !(bitmask & (1 << x)))
    {
     backtrack(x,largest_node,dest,bitmask | (1 << x),cur + " " + to_string(x));
    }
   }
  }


 }
}
void dfs(int n, int largest_node)
{
 visit[n] = true;
 for(int i  = 1; i <= largest_node; ++i)
 {
  if(matrix[n][i] && !visit[i])
   dfs(i,largest_node);

 }
}
int main()
{
 ios_base::sync_with_stdio(false);
 string line;
 int nearest;
 int cases =1;
 while(cin >> nearest)
 {
  int n1,n2;
  memset(matrix,0,sizeof matrix);
  int largest_node = 1;
  while(cin >> n1 >> n2 && n1 && n2)
  {
   matrix[n1][n2] = matrix[n2][n1]= 1;
   largest_node = max(largest_node,max(n1,n2));
  }
  memset(visit,false,sizeof visit);
  dfs(nearest,largest_node);
  total = 0;
  cout << "CASE " << cases++ << ":\n";
  backtrack(1,largest_node,nearest,2,"1");
  cout << "There are " << total << " routes from the firestation to streetcorner " << nearest << ".\n";
 }
 return 0;
}

Thanks for reading :) If you have comments,questions, or suggestions, please leave me a comment below :)