Match Editorial

Match summary

The second round of this year's TopCoder Open used a rather easy problemset. More than 80 coders scored more than 1,000 points each. However, many top rated coders overlooked a tricky case in the hard problem. Some of the "big names" later discovered the case and resubmitted their solutions. The random numbers generator slightly influenced this round as well, by putting five targets into a single room.

Also during the challenge phase the top spot in the rankings often changed. After the system tests it belonged to pashka. The next four spots were claimed by nya, marek.cygan, msg555, and crazyb0y. All four of them reached their new highest rating after this match.

The Problems

Value	250
Submission Rate	702 / 824 (85.19%)
Success Rate	513 / 702 (73.08%)
High Score	Petr for 247.69 points (2 mins 45 secs)
Average Score	196.95 (for 513 correct submissions)

The problem statement can be rephrased as follows: Given a graph with both directed and undirected edges, is it possible to pick directions for the undirected edges so that the resulting graph will contain no cycles?

One important observation about this problem could be made by analyzing the examples. The observation is: If the directed edges form a cycle somewhere in the network, the answer is "NO". The reason is clear: the king can't change these edges, and thus the cycle will remain there.

The second part of solving this problem was realizing that the converse holds as well.

Consider example 4 – a complete undirected graph. Here one possible solution is to direct each edge so that its target has a larger number than its source. This will clearly make the graph acyclic. And a similar strategy can be used in all cases.

More precisely, suppose that there are no directed cycles in the original graph. In other words, if we throw away all undirected edges, we'll have an acyclic graph. Each acyclic graph has got a topological ordering. This means that we can order the vertices into a sequence such that for each edge the source vertex occurs before the target vertex.

If there are more possible orderings, pick any one of them. Now we'll add all the undirected edges back. When adding an edge, find its two endpoints in our topological order. The one that occurs earlier will be the source vertex.

In this way, we ensure that the topological ordering remains valid all the time, and thus the resulting graph is still acyclic.

Of course, this was just the reasoning behind our algorithm, we don't actually need to implement any of this. We just argued that the answer is "YES" if and only if the input graph contains no directed cycles. And this is the only thing we need to check.

For a 50-vertex graph the easiest way how to check for presence of a cycle is to use Floyd's algorithm to find the transitive closure of the graph. This is a special case of the better-known Floyd-Warshall algorithm for all-pairs shortest paths in a graph. In our case, we don't care about lengths, we only need to know whether a path exists or not.

Java code follows.

  public String canChange(String[] roads) {
    int N = roads.length;
    boolean[][] G = new boolean[N][N];
    for (int i=0; i<N; i++)
      Arrays.fill(G[i],false);

    for (int i=0; i<N; i++)
      for (int j=0; j<N; j++)
        if (roads[i].charAt(j)=='Y' && roads[j].charAt(i)=='N')
          G[i][j] = true;

    for (int k=0; k<N; k++)
      for (int i=0; i<N; i++)
        for (int j=0; j<N; j++)
          G[i][j] |= G[i][k] && G[k][j];

    for (int i=0; i<N; i++)
      if (G[i][i])
        return "NO";
    return "YES";
  }

Value	500
Submission Rate	590 / 824 (71.60%)
Success Rate	363 / 590 (61.53%)
High Score	ACRush for 489.43 points (4 mins 11 secs)
Average Score	314.35 (for 363 correct submissions)

We are given total freedom in how we do the upgrades. When looking for the optimal algorithm, freedom is bad – it gives us too many possibilities to try. How can we constrain the search?

We can decide to be a bit systematic in doing the upgrades. We will start by spending some (possibly zero) days upgrading level 0 creatures, then we'll upgrade some level 1 creatures, and so on. Clearly, in this way we'll be able to achieve the optimal total power. (If we have an optimal solution that makes the upgrades in some other order, we can easily rearrange them and do them in our order.)

Now we could easily write a recursive solution that would try all the possibilities. Of course, we would like to memoize the computed values to avoid exponential time complexity. To do this, we need to identify precisely what describes the state of the computation.

Two parameters are obvious: the level L of the creatures we are currently upgrading, and the number D of days left. However, this is not all, there is one more important issue. We might have done some previous upgrades, and thus the current number of level L creatures may be higher than the input value. This difference will be the third, and final, parameter.

There are at most N=50 levels, and at most D=100 days. Obviously, the third parameter can never exceed D. Thus there are at most N*D*D=500,000 states. The time complexity of computing one state is O(D), leading to the overall time complexity O(N*D³).

C++ code follows.

  long long memo[52][102][102];
  long long counts[52], powers[52];
  int N;

  long long solve(int level, int add, long long upgrades) {
    long long &res = memo[level][add][upgrades];
    if (res >= 0) return res;
    res = 0;
    if (level==N) return res;
    int maxUpgrades = min( upgrades, counts[level]+add );
    for (int now=0; now<=maxUpgrades; now++) {
      long long thisLevel = powers[level] * (counts[level]+add-now);
      long long nextLevels = solve(level+1,now,upgrades-now);
      res = max( res, thisLevel+nextLevels );
    }
    return res;
  }

  long long maximumPower(vector <int> _count, vector <int> _power, int D) {
    memset(memo,-1,sizeof(memo));
    N = _count.size();
    for (int i=0; i<N; i++) counts[i] = _count[i];
    for (int i=0; i<N; i++) powers[i] = _power[i];
    return solve(0,0,D);
  }

Value	1000
Submission Rate	235 / 824 (28.52%)
Success Rate	122 / 235 (51.91%)
High Score	msg555 for 896.87 points (9 mins 51 secs)
Average Score	618.70 (for 122 correct submissions)

Greedy solution

First of all, when reading the constraints, we should note a nasty special case – stones where gold=silver=0. We will throw such stones away immediately. In the rest of this solution, each stone contains at least one ore type.

After playing around with the examples, we can get a feeling that some greedy approach could work here. But this is always dangerous ground, and being careful pays off.

Imagine that the two doctors will be taking turns. In each turn, each doctor will take one microgram of the ore he likes. (If they don't use the metric system, they may take twelfths of a grain instead.) Now, note that if we are out of pure gold, dr. Austin will not only get his microgram of gold but also some silver. This silver will be thrown away. Now dr. Austin's optimal choice becomes obvious: pick a piece from the stone where the gold/silver ratio is largest, and thus minimize the amount of silver that gets thrown away. The opposite strategy can be used by Dr. Agnew.

Thus the optimal strategy looks as follows: We sort the stones according to their gold/silver ratio. Dr. Austin will start picking from one end, dr. Agnew from the other, and they will meet somewhere in the middle, possibly splitting the last stone.

(An exact proof should, of course, use the continuous nature of the problem, not the discrete approximation we used above. One possibility how to do the proof: suppose that the optimal way of splitting the stones differs from the one our algorithm produces. Then dr. Agnew got a piece that's "further to the left", and dr. Austin a piece that's "further to the right" than in our solution. If they swap appropriate parts of these pieces, the solution's value will increase, which is a contradiction.)

An elegant way how to implement this solution is to use binary search on the final amount of ore the doctors get. For a given amount of ore, we can easily count how many stones each of them gets, and check whether their desired intervals overlap.

C++ code follows.

  class Stone {
    public:
      int gold, silver;
      Stone(int g, int s) { gold=g; silver=s; }
  };

  bool myLess(const Stone &A, const Stone &B) {
    if (A.gold+A.silver==0) return false;
    if (B.gold+B.silver==0) return true;
    return A.gold*B.silver > A.silver*B.gold;
  }

  double howManyStones(const vector<int> &stuff, double bound) {
    int N = stuff.size();
    int whole = 0;
    double total = 0;
    while (whole<N && total+stuff[whole]<=bound) total += stuff[whole++];
    if (whole==N) return N;
    return whole + (bound-total) / stuff[whole];
  }

  double value(vector <int> _silver, vector <int> _gold) {
    vector<Stone> S;
    for (unsigned i=0; i<_silver.size(); i++)
      if (_silver[i]+_gold[i] > 0)
        S.push_back( Stone(_silver[i],_gold[i]) );

    int N = S.size();
    if (N==0) return 0;
    sort( S.begin(), S.end(), myLess );

    vector<int> gold, silver;
    for (int i=0; i<N; i++) gold.push_back( S[i].gold );
    for (int i=0; i<N; i++) silver.push_back( S[N-1-i].silver );

    double mn=0, mx=6000;
    for (int loop=0; loop<300; loop++) {
      double md=(mn+mx)/2;
      if (howManyStones(gold,md) + howManyStones(silver,md) <= N) mn=md; else mx=md;
    }
    return mn;
  }

Linear programming solution

One final note: This problem can be converted to a linear programming instance. Several coders used pre-written LP solvers to achieve high scores for this problem.

More precisely, for N stones we will have 2N variables, x₀ to x_2N-1. The variable x_i is the part of i-th stone given to dr. Agnew, and x_N+i is the part of i-th stone given to dr. Austin. We get N obvious constraints: for each i, x_i + x_N+i ≤ 1. (The problem statement requires =1, but clearly the optimal solution will use all the stones anyway.)

Now comes the tricky part: we will try to maximize the amount of silver taken by dr. Agnew, subject to one more constraint: this amount of silver must not exceed the amount of gold left for dr. Austin to take.

This final constraint can be expressed as follows: The amount of silver taken is:
silver₀*x₀ + ... + silver_N-1*x_N-1
The amount of gold left is: gold₀*(1-x₀) + ... + gold_N-1*(1-x_N-1)
We get the inequality:
silver₀*x₀ + ... + silver_N-1*x_N-1 ≤ gold₀*(1-x₀) + ... + gold_N-1*(1-x_N-1)
And this can be rewritten as:
(silver₀+gold₀)*x₀ + ... + (silver_N-1+gold_N-1)*x_N-1 ≤ gold₀ + ... + gold_N-1.

See nya's solution for an implementation of this approach.