Online Round 4 Saturday, March 8, 2008 Match summaryRound 4 of the 2008 TopCoder Open saw 147 of the best competitors battling for 72 spots at the onsite finals in Las Vegas. Excitement was high. There were at least twice as many observers as coders in the Arena – some rooting for the their fellow countrymen, some for their favorite coder. The challenge began slowly. Unlike the other online rounds, no one solved the easy problem quickly, with the first submission coming from Eryx in a little less than 12 minutes. As solutions to the easy trickled in, Ted, who had skipped the easy to work directly on the medium, submitted the medium to take the lead with 50 minutes of coding time left. Soon after Petr, to the cheers and adulation of his massive fan club in the Arena, jumped to first with a rapid submission of the medium after resubmitting the easy. A bunch of medium solutions soon followed. With 20 minutes remaining, about 2530 coders were working on the hard problem, and it seemed as if at least a couple people would solve it. However, only K.O.T. submitted a solution to the hard before the challenge phase came to an end. In the first few mintues of the challenge phase, K.O.T.'s hard went down and Petr jumped back into the lead by a sizeable margin with a string of challenges on top of his fast time for the medium. Observers watched as a few targets and high ranking reds lost their easy and medium solutions, and fell out of contention. System tests took out more solutions and the cutoff for the onsite round fell to 153.18 points. In the end, Petr came out ahead and went above a 3700 rating for the first time since last June. He was followed by firsttime target tomekkulczynski, krijgertje, marek.cygan and ahyangyi. A few observations about the upcoming TCO onsites:
Congratulations to all the advancers! The ProblemsMagicLabelingUsed as: Division One  Level One:
This problem looks deceptively easy, but it actually takes quite a bit of time and focus to create a working solution. First, count the number of vertices with 0 edges. These vertices can be labeled with any number between 1 and M. Next, look at each connected component. By the restrictions, all the vertices connected to any single vertex must have the same label. This means, for each independent component, there is either 1 or 2 distinct numbers which label all the vertices. Deciding whether or not a component can have two labels is the same as deciding whether or not it can be twocolored, which is an easy problem to solve by DFS. Once we have the number of solitary nodes, the number of twocolorable components, and the number of monocolor components, we can find the solution by iterating through each possible edge sum and calculating the number of labeling possibilities for each component based on that sum. Code below: const int MOD = 1000003; int color[55], visit[55]; int G[55][55]; int N; int dfs(int a, int col) { if(visit[a]) { if(color[a] != col) return 0; else return 1; } visit[a] = 1; color[a] = col; int ok = 1; for(int i = 0; i < N; i++) { if(G[a][i]) { if(!dfs(i,1col)) ok = 0; } } return ok; } class MagicLabeling { public: int count(vector<string> a, int M) { N = a.size(); memset(visit,0,sizeof(visit)); int solitary = 0, two_color = 0, one_color = 0; for(int i = 0; i < N; i++) { int edges = 0; for(int j = 0; j < N; j++) { if(a[i][j] == 'Y') { G[i][j] = 1; edges++; } else G[i][j] = 0; } if(edges == 0) { solitary++; visit[i] = 1; } } if(solitary == N) { int res = 1; for(int i = 0; i < N; i++) res = (res * M) % MOD; return res; } //find the components for(int i = 0; i < N; i++) { if(visit[i] == 1) continue; if(dfs(i,0)) two_color++; else one_color++; } long long res = 0; for(int edge_sum = 2; edge_sum <= 2*M; edge_sum++) { if(one_color > 0 && edge_sum % 2 == 1) continue; long long pairs = 0, labels = 1; for(int label = 1; label <= M; label++) { if(edge_sum <= label  (edge_sum  label > M)) continue; pairs++; } for(int i = 0; i < two_color; i++) labels = (labels * pairs) % MOD; for(int i = 0; i < solitary; i++) labels = (labels * M) % MOD; res = (res + labels) % MOD; } return res; } };OlympicGames Used as: Division One  Level Two:
Solution #1: Dynamic ProgrammingTo me, this problem suggests a Dynamic Programming solution. In the beginning, we find the number of teams already beating team 0, after all remaining gold medals are added to team 0, and then look for the optimal placement of the remaining silver and bronze medals. When we are looking for parameters to recurse on, the first thing that comes to mind is a DP that looks like this:
dp[M][N] = max # of teams that beat team 0 with M silver medals assigned and N bronze medals assigned. However, because M and N can be as great as 10,000, this gives a total state space of up to 100,000,000 – which is about an order of magnitude more memory than allowed in the Arena. So we have to look for an optimization. Consider reordering the three numbers related to each other by the above DP. We saw that dp[M][N] = MAX, didn't work, so what about dp[M][MAX] = N? In other words this would be a dp such that
dp[M][T] = Minimum # of bronze medals needed to have T teams beat team 0 after M silver medals are assigned. This would give us a state space of up to 10,000 * 50 = 500,000, well within our limits. See Petr's code for a clear implementation. Solution #2: Greedy ApproachBy reading the forums, I discovered that there is also a greedy solution to this problem, based on the observation that you can sort all teams 1…N first on silver[0]silver[i] and then on bronze[0] – bronze[i]. Then, when deciding if M teams can beat team 0, we choose the first M teams of our sorted array. To show why this works: Consider M teams that can beat team 0, but are not the first M teams of the array. If any skipped team p has an equal difference in silver medals with any team q, then it is better to include p than q (p has a smaller difference in bronze medals). Otherwise, if skipped team p has a smaller difference in silver but a greater difference in bronze than added team q, then add all the extra silver medals q needs more than p, to p. This arrangement would require p to have 0 bronze medals, as team p would beat team 0 on silver medals alone, which is at least as good as the assignment where q is included and p is not. Once we have this figured out, the solution follows: class OlympicGames { public: int worstPlace(vector<string> T, int games) { int N = T.size(); int g[N], s[N], b[N]; int res = 1; vector<pair<int,int> > medals; for(int i = 0; i < N; i++) { sscanf(T[i].c_str(),"%d %d %d",&g[i],&s[i],&b[i]); if(i==0) g[i] += games; else { if(g[0] < g[i]) { res++; continue; } if(g[0] > g[i]) continue; if(s[0] < s[i]  (s[0]==s[i] && b[0] < b[i])) { res++; continue; } int sdiff = s[0]s[i], bdiff = b[0]b[i]; if(sdiff > games  (sdiff == games && bdiff > 0)) continue; medals.push_back(make_pair(sdiff,bdiff)); } } sort(medals.begin(),medals.end()); for(int beat = medals.size()1; beat >= 0; beat) { int silver = 0, bronze = 0; vector<int> need; for(int i = 0; i <= beat; i++) { if(medals[i].second + medals[i].first == games) { silver += medals[i].first + 1; continue; } silver += medals[i].first; if(medals[i].second >= 0) { bronze += medals[i].second+1; need.push_back(medals[i].second+1); } } if(silver > games) continue; sort(need.begin(),need.end()); while(silver < games && need.size()) { silver++; bronze = need.back(); need.pop_back(); } if(bronze <= games) return res + beat + 1; } return res; } };Collect Used as: Division One  Level Three:
Primarily, this problem was a test of optimization skills. To find a solution which passes system tests under the time limit, there are a variety of approaches. Lookup tableThe idea behind a lookup table is to precalculate the answers to all possible combinations of inputs (in this case, 1000) and store them in an array to overcome time constraint issues. Petr almost finished this lookup table before the coding phase ended. DP with pruning and lockingConsider some roll R – what are the parameters we need to describe the state? Well, the value of each die, and the number of rolls remaining. This leads to state space of 7^10 * 100 = ~28,000,000,000 – more than we can map to memory. However, we can also define the state space by the number of dice = 1..6, leading to a state space of 11^6 * 100 = 177,156,100, still more memory than we can allocate. We can get this down further to 2*1,777,156 by considering one roll at a time. However, the challenge is still to make the code run in time, which requires pruning and other optimizations. There is a good discussion in this thread about possible optimizations for a dynamic programming solution. Read it, and be enlightened. 
