Google Codejam 2006 Round 2

I managed a very bad performance in the latest round of GCJ, ending up on place 286. Even if I would have been in good shape I very much doubt that I would have been able to finish in the first 100 and qualify to the onsite. Long story short: the problem were nice so I want to share them and their solutions.

Easy

This problem was tricky, lots of people missed something. It said that you are given a string and you should decide whether it is a valid fraction of the form "/" such that (1) integers do not have leading zeros, (2) integers are not greater than 2³¹, (3) integers are non-negative (i.e., no `minus' sign), (4) the denominator is not zero, and (5) no extra characters (such as spaces) are allowed. For example "3/4" is valid, while " 0/0" is guilty on two counts (has space and the denominator is zero). You should return the index of the first character that makes the input bad, or -1 if the input is valid.

During the match I implemented an automaton, very similar to what is used to detect a regular expression.

Medium

The medium problem gives an integer with at most 50 digits (as a string with no leading zeros) and asks for the minimum number of digits that need to be changed (digits to the left can be changed into zeros) such that the resulting number is a multiple of m, which is at least 1 and at most 50000.

This problem can be solved by first writing in mathematical language what is being asked: we want to know the minimum number of digits to change in x such that x=0 (modulo m). For problems that involve multiplication and very big numbers it pays of to look at the digits one by one. So we write x=10x'+d, where d is the last digit of x. The condition then becomes 10x'=-d (modulo m). This suggests one solution. First we generalize the problem to finding how many digits should be changed in x such that x=a (modulo m). Then we can try all possibilities for d (keeping track if that means a changed digit or not) and check how many digits should be changed in x' such that x'=(a-d)/10 (modulo m), which is the same problem. All that is left is figuring out the base case and computing division by 10 modulo m. Both are easy tasks.

Here is the relevant part of my code.

  int getMin(string t, int m) {
    int n = t.size();
    int i, j, k, d;

    vector<vector<int> > inv10(m);
    for (j = 0; j < m; ++j)
      inv10[(10 * j) % m].push_back(j);

    for (i = 0; i < n; ++i) for (j = 0; j < m; ++j)
      c[i][j] = INF;

    int msd = t[0] - '0';
    for (j = m - 1; j >= 0; --j) {
      for (d = 9; d >= 0; --d) {
        if (d % m == j)
          c[n-1][j] = min(c[n-1][j], int(d != msd)) ;
      }
    }

    for (i = n - 2; i >= 0; --i) {
      int dx = t[n-i-1] - '0';
      for (j = m - 1; j >= 0; --j) {
        for (d = 9; d >= 0; --d) {
          int nm = ((j - d) % m + m) % m;
          for (k = 0; k < inv10[nm].size(); ++k)
            c[i][j] = min(c[i][j], (d!=dx) + c[i+1][inv10[nm][k]]);
        }
      }
    }

    return c[0][0];
  }

Hard

This problem gives a rooted tree with weighted edges and a budget. It askes how many nodes can be connected to the root using that budget. The number of nodes is at most 100, while the budget is (an integer) at most 1000000000.

Since we are given a tree we have a natural way of breaking the problem into subproblems. Let's consider some arbitrary node n with children n₁, ..., n_q, the costs toward the children being respectively c₁, ..., c_q. Let us now denote the number of nodes in tree t that can be connected with a budget of b by N(t, b). How can we construct this number from N(t_i, b')? It turns out we can't because there are just too many ways to split the money between the children. So, instead, we'll ask them how much money they need to connect a certain number of nodes. There are only 100 nodes so it should be easier. Let's then denote by B(t, n) the budget necessary to cover n nodes in the tree rooted at t.

We can now compute B(t, n) = min_n1+...+nq=n sum_i B(t_i, n_i) + [n_i != 0] c_i. This can be done efficiently by a simple dynamic programming, basically updating B(t, *) incrementaly after considering each child. The only remaining problem is to make sure we process the children first and then their parrents -- a classic job for DFS.

Here is the code. It contains some parsing necessary because the graph was given in a text. Just think of adj as being adjacency lists and the corresponding positions in cst represent costs. Also, m is the number of nodes, r is the index of the root, and bm is the available (maximal) budget.

typedef long long i64;
int m;
vector<int> adj[128];
vector<int> cst[128];

i64 b[128][128];

const i64 INF = 0x7fffffffLL * 100;


void dfs(int nn, int n) {
  int i, j, k;
  for (i = 0; i < adj[n].size(); ++i) if (adj[n][i] != nn) {
    dfs(n, adj[n][i]);

    for (j = m; j >= 0; --j) {
      for (k = 0; k <= j; ++k) 
        b[n][j] = min(b[n][j], b[n][j-k] + b[adj[n][i]][k] + !!k * cst[n][i]);
    }
  }
}

struct HighwayBuilding {
  int getMaxCities(int m_, int r, vector <string> gs, int bm) {
    m = m_;
    int i, j;
    for (i = 0; i < gs.size(); ++i) {
      replace(ALL(gs[i]), ',', ' ');
      istringstream iss(gs[i]);
      int f, t, c;
      while (iss >> f >> t >> c) {
        adj[f].push_back(t);
        cst[f].push_back(c);
        adj[t].push_back(f);
        cst[t].push_back(c);
      }
    }

    for (i = 0; i < m; ++i)
      for (j = 2; j <= m; ++j) b[i][j] = INF;
    
    dfs(-1, r);

    for (i = 1; i < m && b[r][i+1] <= bm; ++i);
    return i - 1;
  }
};