Match Editorial

In this round, another set of 100 coders made it to the final round, with only 12 non-zero scores being cut. This was mostly due to a very simple level one problem, and a brute-forceable level two. Competition was fierce, as the top 5 coders were separated by less than 50 points. Too bad there wasn't a challenge phase!

The Problems

Value	250
Submission Rate	121 / 139 (87.05%)
Success Rate	110 / 121 (90.91%)
High Score	k_m for 245.18 points (3 mins 12 secs)
Average Score	210.99 (for 110 correct submissions)

Problems don't get much simpler than this. Follow the directions and return the answer. You are given a function, with its output values for each possible input value. You are then asked to iterate it for bound times. Then, you are to iterate the function until it returns the same value you started with. The problem can be solved in one loop:

int t = x;
int n = 0;
while(n <= bound || t != x)
{
  t = f[t];
  n++;
}
return n;

Simply stated, we continue to call the function on t until we have called it more than bound times and t is equal to x. By converting to a for-loop, we can compress the code to a 3-line solution:

int n, t;
for(n = 0, t = x; n <= bound || t != x; n++, t=f[t]);
return n;

Value	550
Submission Rate	82 / 139 (58.99%)
Success Rate	45 / 82 (54.88%)
High Score	Jan_Kuipers for 486.79 points (8 mins 25 secs)
Average Score	325.99 (for 45 correct submissions)

This problem can be solved by brute force. A path that a person can take can be described with the points at which the person moves to the right, and the points at which the person moves down. For the worst case of a 7x7 grid, The person moves exactly 12 times, 6 times to the right and 6 times down. For example, a path on a 7x7 grid can be described as "RDDDRRRDRRDD". The number of possible paths is therefore defined by the choice function C(12, 6), because there are that many ways to put 6 R's in a field of 12 characters (with the rest being D's). Therefore, the maximum number of paths for an individual is 924. with two individuals, 924² is the maximum number of combinations of paths, giving us about a million possibilities to check. This is probably best done through a recursive function, where at each point, all possibilities are tried, and money which is picked up is put back when the function exits to try another path.

Of course, with a higher maximum, such as a 50x50 grid, brute force would not be possible, as C(98,49)² would be way too many possibilities. However, there is another way to process the paths, using memoization. First we assume that each person moves at the same speed and starts at the same time (this is an important point!). The logic is, if we get to a point where you are at position (x₁, y₁), and your friend is at position, (x₂, y₂), then the maximum amount of money you can subsequently pick up is not affected by your path to that location. Therefore, we define a function maxMoney(x₁, y₁, x₂, y₂), which is memoized on the four input values. The answer then is simply maxMoney(0, 0, 0, 0). The function can be written as follows:

int cache[MAXC][MAXR][MAXC][MAXR]; // initialized all to -1
vector<string> grid;
int maxMoney(int x1, int y1, int x2, int y2)
{
  if(x1 >= MAXC || y1 >= MAXR || x2 >= MAXC || y2 >= MAXR)
    return 0;
  if(cache[x1][y1][x2][y2] != -1)
    return cache[x1][y1][x2][y2];
  int money = grid[y1][x1] - '0';
  if(x1 != x2 || y1 != y2)
    money += grid[y2][x2] - '0';
  return cache[x1][y1][x2][y2] = money + max(
    max(maxMoney(x1 + 1, y1, x2 + 1, y2), maxMoney(x1, y1 + 1, x2 + 1, y2)),
    max(maxMoney(x1 + 1, y1, x2, y2 + 1), maxMoney(x1, y1 + 1, x2, y2 + 1)));
}

With MAXC and MAXR = 50, this would probably get past topcoder systests, but if MAXC and MAXR were 200, the above O(n⁴) solution would certainly time out. See if you can solve this problem in O(n³), and I will post the answer to the algorithms round table.