
Match Editorial 
2004 TopCoder Collegiate Challenge
Qualification Problem Set 5February 2324, 2004
Summary
In this round, another set of 100 coders made it to the final round, with only
12 nonzero scores being cut. This was mostly due to a very simple level one
problem, and a bruteforceable 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
FunctionIter
Used as: Division One  Level One:
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 forloop, we
can compress the code to a 3line solution:
int n, t;
for(n = 0, t = x; n <= bound  t != x; n++, t=f[t]);
return n;
MoneyRun
Used as: Division One  Level Two:
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^{2} 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)^{2} 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_{1}, y_{1}), and your friend is
at position, (x_{2}, y_{2}), 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_{1}, y_{1},
x_{2}, y_{2}), 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^{4}) solution would certainly
time out. See if you can solve this problem in O(n^{3}), and I will
post the answer to the algorithms round table.
By
schveiguy
TopCoder Member