I competed in the Top Coder Open 2009 Round 1 last Saturday after qualifying the previous week. My friends Nick and Oleg also competed. You had to finish in the top 720 to qualify for the next round, but only Oleg managed to do that out of the three of us. I was very close, but unfortunately an off by one error caused me to fail system tests.
The first problem was pretty easy. You were given a number N between 1 and 10^10 and another number L between 2 and 100 and you wanted to find a sequence of numbers of length at least L that summed to N.
I realized that candidate numbers would be close to N/L for L up to 100. So my algorithm tries all numbers and their sums within those ranges keeping track of the best one.
vector<int> sequence(int N, int L) {
if(L > 100) return vector(0);
vector<int> r, best;
for(int j = L; j <= 100 ; j++) {
int mid = N / j;
// define an arbitrary range of numbers to try
int start = max(mid - 1000, 0);
int end = mid + 1000;
// try all numbers
for(int i = start; i <= end; i++) {
int sum = 0;
for(int k = i; k <= N; k++) {
sum += k;
r.push_back(k);
if(sum > N) break;
if(sum == N && r.size() >= L
&& r.size() <= 100 && (r.size() < best.size()
|| (!best.size() && r.size() <= 100)) {
best = r;
}
}
r.clear();
}
}
return best;
}
I got the code implement pretty quickly and submitted for a pretty decent score. Provided I passed the system tests, with the one problem solved I would have been close to qualifying for the next round. Unfortunately, when I submitted my loop from k=i to k <= N was written as k=i to k < N. That simple mistake cost me the competition :-). There are nicer ways to solve this problem using the sum formula, but I still like my semi-bruteforce approach.
I got stuck on the 500 problem and glanced quickly at the 1000 out of desperation. I should have moved onto the 1000 point problem because I think it was easier than the 500 even though it required a lot more code. I solved the 1000 point problem yesterday.
In that problem, you are given the description of a new chess piece called a “Unicorn”. It moves by choosing any of the 4 basic directions and moving more than 2 squares in that direction, then turning orthogonally in one of the two possible directions and moving more than 1 square in that direction. You are given a randomly generated chessboard of size up to 300×300 where each square or cell has a letter (A through Z). You are also given a word that can be spelled out on the chessboard by moving a unicorn piece. You have to determine how many possible ways you can generate the given word by moving a unicorn piece around the chessboard.
For example, consider the chessboard below:
ABCD
AAAA
AABC
AAAB
If we want to construct the word “AB”, there’s only two ways to do this. We place our unicorn piece in the top left-hand corner getting the “A”. We can then move our chess piece 3 places to the bottom left-hand corner, turn orthogonally to the right, and move 3 places to the right to get a “B”. We can also reach the bottom right-hand “B” by placing our unicorn in cell (1,0).
The key to solving this problem is to realize that assuming you arrived in a cell, there’s a fairly small number of cells that you could not possibly have been at previously to reach this cell. You can keep track of the number of paths to reach a given cell by counting the number of ways to reach all previous letters and subtracting off the cells that you could not possibly have come from.
Moving back to our example from before, initially we can get to any cell with an A in one step. Meaning that you can travel to that cell one way, essentially place the unicorn directly on it. Represented as a matrix it looks like this:
1000
1111
1100
1110
Now we can consider any cells with a B. The first is cell (0,1). There’s a total of 10 possible A’s that we could have used to arrive at this B. We can cross off all the cells that we could not possibly have jumped from to reach this location. This includes B’s row, column, previous column, next column, previous row, next row, and a few others.
XBXX
XXXX
XXXX
XXXB
We can count all the A’s that were crossed off, which turns out to be 10 and remove this from the total number of A’s, which is also 10. This means there are zero ways that this particular cell could be the second position in a valid path to form the word “AB”. We can continue doing this. Once we reach cell (3,3), the crossed off matrix looks like this:
AXXX
AXXX
XXXX
XXXB
There were 8 “A”s crossed off, so there are 2 ways to get to this “B”.
For longer words, the process is much the same. There’s a few catches in the problem, like making sure you handle large sums appropriately as you can potentially get a very large number of paths. Also, there’s a small trick to get the algorithm to run in O(N^2) rather than (N^3).
