Monday, October 18, 2004 Match summary It was not an easy night for Division 1 participants as all three problems proved both unusual and challenging, each in their own way. Many strong competitors were thrown off by this and ended up with scores of 0, which makes tomek's intimidating 1641.97 points all the more impressive  congratulations! He was followed by fellow Pole Eryx in second, and kalinov in third. It was also nice to see a new face among the top scorers with ivan_metelsky finishing in fourth place in his fourth TopCoder competition. There were many more submissions in Division 2, but the system tests were anything but easy. It was a tight race near the top as AnonnymousT took first place with three successful challenges, followed by newcomers zjq and tesh11. The ProblemsCultureShockUsed as: Division Two  Level One:
The most natural approach to this problem is to split the given text into an array of words, and to then check if each word is "ZEE". You can then reconstruct the string by concatenating the words, adding spaces as necessary. In C++, this can be done as follows: string result, temp; istringstream in(text); while (in >> temp) { if (temp == "ZEE") result += " ZED"; else result += " " + temp; } return temp.substr(1);In Java, you can use StringTokenizers, following Sleeve's solution, or you can use the very handy split function. If you do not use builtin parsing tools, you have to be careful that you only replace complete words, an oversight that accounted for many of the incorrect submissions for this problem. If you a real guru, you can actually solve the problem in a single line. Here is one such solution: return (" "+text+" ").replaceAll(" ZEE "," ZEE ").replaceAll(" ZEE "," ZED ").replaceAll(" "," ").trim();Spaces are added at the beginning and end of text as advised here. I leave it as a little puzzle to figure out why the first and third replaceAll calls are needed. By the way, for
those wondering who Bob and Doug are, I refer you to Google.
RockStar
Used as: Division Two  Level Two: Used as: Division One  Level One:
This problem is as much about logic as it as about coding, a fact that threw off many competitors. For such a problem, the first thing you need to do is just organize your thoughts. In this case, a few observations turn out to be key:
if (fs+ff > 0) { if (fs == 0) return ff; else if (sf >= fs) return ff + ss + 2*fs; else return ff + ss + 2*sf+1; } else return ss + min(sf, 1);Of course, it is easy to make a mistake on one or more of these cases, even with the fairly broad range of examples. I did not really see any pattern in the mistakes here  you just had to be careful. Although it is probably not very helpful for solving the problem, the scenario can also be related to the question of Eulerian paths on a multigraph with two vertices (fast and slow), where each song corresponds to a directed edge. Using this insight, you can actually efficiently solve a more general version of the problem where there are more than two possible song speeds. TournamentRankerUsed as: Division Two  Level Three:
Not surprisingly, the key to solving this problem is being able to determine which of two competitors should be ranked higher. There are a couple ways of approaching this, but I think the cleanest is to follow the problem directions precisely as given. First of all, make sure you know the number of wins that each competitor has, and to whom each competitor lost. Then, you can translate the ranking description almost directly into a recursive function. In C++, for example, it might look like this: map<string, int> wins; map<string, string> lostTo; bool isRankedHigher(const string &s1, const string &s2) { if (wins[s1] != wins[s2]) return wins[s1] > wins[s2]; else return isRankedHigher(lostTo[s1], lostTo[s2]); }You could then sort the competitors in one line: sort(names.begin(), names.end(), isRankedHigher) . This can also be done in Java, although the syntax is a little more
cumbersome. See, for example, Rakot's
solution.
If you are not comfortable with recursion, one other approach is to build the sorted list one competitor at a time. You only consider adding competitors with a maximal number of wins, and then the competitors they lost to will have already been sorted, so they can be compared directly without recursion. See theMadhouse's solution for a variation on this method. RefactoringUsed as: Division One  Level Two:
It only takes one quick look at the statistics to see that this was an unusual problem. With only 29 correct solutions, it was clearly not easy. On the other hand, battyone solved it really fast. So how do you do it? I think there are three things you have to realize. First of all, you have to see that this is a level 2 problem, not a level 3 problem. You are not going to need crazy math, so you should not even be trying that. The next thing you should realize is that factorizations and recursion go very well together. Specifically, if n = a * m, then a * m is a factorization of n, as is a multiplied by any factorization of m. Indeed, we can find all factorizations of n by iterating over all of its divisors a, and then recursively finding all factorizations of n/a. Unfortunately, this will find certain factorizations more than once. For example, 2*3*4 and 4*3*2 might both be counted, even though they are the same factorization. To solve this, it suffices to generate the factors in nondecreasing order. This can be done as follows: int count(int n, int lastFactor) { int result = 0; for (int a = lastFactor; a*a <= n; a++) if (n % a == 0) result += count(n/a, a) + 1; return result; }So what is the final thing you have to realize? Just that this solution is already fast enough! This is not at all obvious, but the examples give you the worst case, so you can easily check. Indeed, written in Java, this code never takes more than about 4.5 seconds. If, for some reason, your program is not quite fast enough, there are still a couple optimizations you can try. If you precompute the factors of n, and then use memoization with a hash table, for example, you can make everything run in under a second. RoxorUsed as: Division One  Level Three:
I was not sure if anybody would solve this problem, and if I saw a way to make it easier, I gladly would have taken it. Although one competitor confided that "I can do little more than cry in the face of this problem", it actually ended up being a little easier than I expected. For twoplayer games like this, it is helpful to think in terms of winning and losing positions. Specifically, if two perfect players are playing, then either the first player wins or he loses. If he wins, call the starting position winning; otherwise call it losing. It is then easy to check that (a) all moves from a losing position change the game to a winning position, and (b) winning moves are precisely those moves that change the game from a winning position to a losing position. Thus, it is helpful here to find winning and losing positions, and to worry about winning moves from there. So how do you do that? It turns out that example 1 is a big, big hint, and the key is reducing modulo 2 the number of stones in each pile. Specifically, given a position P, we let P' denote the same position with the number of stones in each pile reduced modulo 2 to either 0 or 1. Then, call P bad if P' is a losing position. We claim that if player 1 is in a bad position P, then player 2 can ensure that player 1 will always be in a bad position. To see this, consider any move that player 1 could make:
Case 1: Suppose he does not remove the last stone from a pile. Then, player 2 can simply copy his move to get to a new position Q that also reduces to P'. Since P' is a losing position, Q is a bad position, and player 1 is still stuck. In particular, note that player 2 always has a legal move after any of player 1's moves, so player 1 cannot possibly make the last move, and thus, cannot win. It follows that every bad position is, in fact, a losing position. From here, it is easy to see that, in fact, P is a winning position if and only if P' is a winning position! This turns out to be a very important observation, as it reduces the game to just 2^{15} states (since there are 2 meaningful possibilities for the number of stones in each pile). At this point, one can just do a complete search over all positions using memoization. If we represent each state as a 15bit integer, for example, we could check if a position is a winnable like this: map<int,bool> isWinnable; boolean getIsWinnable(int pos, int n) { if (isWinnable.count(pos)) return isWinnable[pos]; boolean result = false; for (int i = 0; i < n; i++) if ( (pos & (1<<i)) != 0) for (int j = i+1; j < n; j++) for (int k = j; k < n; k++) result = !getIsWinnable(pos ^ (1<<i) ^ (1<<j) ^ (1<<k), n); isWinnable[pos] = result; return result; }Finding the appropriate winning move with this information is fairly straightforward. See kalinov's solution for a very clean implementation. As a random caveat, I did not have a fully mathematical solution to this problem (ie without the memoized search at the end), and I did not really expect there to be one. Although five of the six correct solutions to the problem used the method described here, it looks like ivan_metelsky's solution is purely mathematical. I have not had a chance to look at it yet, but it should give another interesting approach. 
