Tuesday, July 1, 2008 Match summarySRM 408 brought 1305 brave competitors together in coding combat. The competitors faced a grueling, greedy set that tempted them with points, only to pull them away during the challenge and system test phases if they hadn't coded carefully. The 250 was reasonably straight forward, but the 500 had a couple of tricky corner cases and the 1000 required very careful coding to implement. In the end, Smylic regained his red color as the only competitor able to find the greedy solutions to all three problems. Second and third place went to almelv and Burunduk1, with Egor being the only other competitor to successfully solve the 1000. Division 2 coders faced two greedy problems in the 250 and 500, and a 1000 that forced them to conserve memory in order to successfully pass. ramgopal1987 was victorious followed closely by c175353. The ProblemsTournamentJudgingUsed as: Division Two  Level One:
This problem has a reasonably straightforward solution. In order to round each quotient to the nearest integer, several paths are available. Some competitors used prebuilt libraries, while others simply added 0.5 to the raw score after division and before rounding. As some people worry about double imprecision when doing this, one can instead use only integers by adding conversionFactor/2 to the raw score prior to division; this guarantees that the result will round correctly. public int getPoints(int[] rawScore, int[] cF) { int ret = 0; for(int i=0; i < cF.length; i++) ret += (rawScore[i] + cF[i]/2)/cF[i]; return ret; }OlympicCandles Used as: Division Two  Level Two: Used as: Division One  Level One:
In order to maximize the number of days that one can light the candles, it is sufficient to take the k tallest candles on day k and light them. The proof for this is reasonably straightforward. Assume on day k you choose to light a candle A but not B (and A's height is less than B). If on some following day we light B but not A, then we can simply switch which days we use A and B, and this will be equivalent to our algorithm. On the other hand, if the rest of the time we light B and A at the same time, then it still acceptable to light B on day k instead of A (since B is taller than A). Thus, each day we light the k tallest candles remaining, and we stop when we cannot light k candles. The most common error on this problem was people forgetting to break out of their loops if the number of days exceeded the number of candles. public int numberOfNights(int[] candles) { int ret = 1; int N = candles.length; while(true) { Arrays.sort(candles); for(int i=0; i < ret; i++) if(N1i < 0  candles[N1i]==0) return ret1; else candles[N1i]; ret++; } }MarblesInABag Used as: Division Two  Level Three:
Assume that we currently have b blue marbles and r red marbles, and that it is our turn. You may draw a red marble from the bag; this will happen with probability r/(r+b), and after Sid's turn will leave you at the state (r1, b1). Similarly, if you instead draw a blue marble, you will move to the state (r, b2), with probability b/(b+r). This sets up a nice DP relation that normally would work well, but for the fact that the table will take up too much room in memory. Thus, we need to find a way to conserve memory. In the above recursion, you can see that there will always be b+r2 marbles after Sid's next turn. Thus, we can change the state to (total_marbles, red_marbles). We win if we reach any state (n, 0), and lose if we get to a state of (n, n); this is our base case. Since all calculations of n marbles are based only on the calculations from states involving n2 marbles, we can use O(n) memory by keeping two arrays; one containing the answers from the n2 marble state, and another where we build our answers for the n marble state. After building each row, we can swap the arrays, and compute the following step. Thus, our answer will be (b+r, r). See hsiehtm's solution for a clean implementation of this approach. An interesting observation was that the cases that forced memory errors had return values of much less than 10^{9} (as the probability of victory is so small). A couple of competitors took advantage of this, including tvs's solution that caught the memory error and returned 0 if the memorization table would be too large. CandyGameUsed as: Division One  Level Two:
First of all, if the graph is not strongly connected, then we can place an infinite number of candies on the nodes that have no path to the target, so we return 1 there. In all other cases, the graph that we have can be pictured as a tree; let us arbitrarily arrange that tree so that the root node is our target. We can show that any maximal arrangement of candy that cannot reach the goal must have a sequence of moves leading to an arrangement with exactly 1 piece of candy on each node (proof left for the reader). We can consider each piece of candy individually. To maximize the candy we put on the graph, we want to move each piece of candy as far away from the target as possible without moving it towards the target. If we move it from a depth of d1 to d2, then we can add 2^{d2d1} candies to that node (removing the candy from the original node). Once we have done this for each node, we simply return the sum (or 1 if the sum is too large). int[] depth; String[] g; void dfs(int cur, int d) { if(depth[cur] > 1) return ; depth[cur] = d; for(int i=0; i < g.length; i++) if(g[cur].charAt(i)=='Y' && depth[i]==1) dfs(i, d+1); } int maxdepth(int cur) { int ret = depth[cur]; for(int i=0; i<g.length; i++) if(g[cur].charAt(i)=='Y' && depth[i] > depth[cur]) ret = Math.max(ret, maxdepth(i)); return ret; } public int maximumCandy(String[] graph, int t) { g = graph; depth = new int[g.length]; Arrays.fill(depth, 1); dfs(t, 0); long ret = 0; for(int i=0; i < g.length; i++) if(i==t) continue; else if(depth[i] == 1) return 1; // Not connected else ret += 1l << (maxdepth(i)  depth[i]); if(ret > 2000000000) return 1; else return (int)ret; }TournamentSeeding Used as: Division One  Level Three:
To solve this problem, we can attempt to simulate the tournament. In each round, we have a list of teams that are currently in the round. Assume that we are in round R (indexed from 0). Let us sort the teams alphabetically, and go through in order. If a team has greater than R wins, then they played against their opponent that had R wins and 1 loss; if there is not exactly one such team, then the game list is invalid. We take the winner from that game and advance them to the next round (and remove the loser). Eventually we will be left with several teams that have R or less wins in the game list and no losses. Here there are several ways to arrange these teams, but in the lexicographically earliest seeding, the lowest seeded team among these teams must be the lexicographically first team, and the highest seed must be the last team. We pair these two teams, advance the lower seed, and continue. We can apply this algorithm repeatedly until we are left with only one team. That team is the team with seed 0, and we can work backwards from there to determine all seeds. C++ code follows: int played[512][512]; vector< string > INVALID(0); vector< string > getSeeds(vector< string > _team, vector< string >_game, vector< int > seeds) { // Parse teams vector< string > teams; string t; for(int i=0; i < _team.size(); i++) t += _team[i]; stringstream s1(t); while(!s1.eof() ) { string temp; s1 >> temp; teams.push_back(temp); } sort(teams.begin(), teams.end() ); map< string, int > teamtable; int N = teams.size(); for(int i=0; i<N; i++) teamtable[teams[i]] = i; // Parse games string g; for(int i=0; i<_game.size(); i++) g += _game[i]; vector<int> wins(N, 0), loss(N, 0); stringstream s2(g); string winner, loser; s2 >> winner; while(!s2.eof() ) { s2 >> loser; wins[teamtable[winner]]++; // If team already lost, invalid set if(loss[teamtable[loser]] > 0) return INVALID; // Otherwise update winloss records loss[teamtable[loser]] = 1; played[teamtable[winner]][teamtable[loser]] = 1; played[teamtable[loser]][teamtable[winner]] = 1; s2 >> winner; } vector< int > current(N, 0); for(int i=0; i < N; i++) current[i] = i; vector< vector< int > > gamesplayed(N); int r = 0; while(current.size() > 1) // Determine games in current round { sort(current.begin(), current.end() ); vector< int > advancers; for(int i=0; i < current.size(); i++) { if(wins[current[i]] > r) // if the game is defined in games { int j; for(j=0; j < N; j++) if(played[current[i]][j]==1 && wins[j]==r) break; // If no opponent has a record of r wins and 1 loss then INVALID if(j==N) return INVALID; // Otherwise the current team wins advancers.push_back(current[i]); gamesplayed[current[i]].push_back(j); gamesplayed[j].push_back(current[i]); } else if(loss[current[i]] == 0 && gamesplayed[current[i]].size()==r) { // otherwise if the opponent is not yet defined int j; for(j=current.size()1; j > 1; j) if(loss[current[j]]==0 && wins[current[j]] <=r) break; if(j < 0) return INVALID; // Greedily assign teams to games advancers.push_back(current[i]); gamesplayed[current[i]].push_back(current[j]); gamesplayed[current[j]].push_back(current[i]); loss[current[j]]++; } // in all other cases the team loses; those cases are above } current = advancers; r++; } // The winner is seed 0, now assign seeds vector< string > finalSeeds(N, ""); queue< int > q; q.push(current[0]); finalSeeds[0] = teams[current[0]]; while(!q.empty() ) { int cur = q.front(); q.pop(); int seed = 0; while(teams[cur]!=finalSeeds[seed]) seed++; int N1 = N; for(int i=0; i < gamesplayed[cur].size(); i++, N1/=2) { if(finalSeeds[N11seed]=="") { finalSeeds[N11seed] = teams[gamesplayed[cur][i]]; q.push(gamesplayed[cur][i]); } } } // Get return vector and return it vector<string> ret = vector < string > (seeds.size()); for(int i=0; i < seeds.size(); i++) ret[i] = finalSeeds[seeds[i]]; return ret; } 
