Get Time
statistics_w  Match Editorial
SRM 408
Tuesday, July 1, 2008

Match summary

SRM 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 Problems

TournamentJudging rate it discuss it
Used as: Division Two - Level One:
Value 250
Submission Rate 622 / 654 (95.11%)
Success Rate 598 / 622 (96.14%)
High Score xgd_sixth for 249.33 points (1 mins 28 secs)
Average Score 217.33 (for 598 correct submissions)

This problem has a reasonably straightforward solution. In order to round each quotient to the nearest integer, several paths are available. Some competitors used pre-built 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 rate it discuss it
Used as: Division Two - Level Two:
Value 500
Submission Rate 525 / 654 (80.28%)
Success Rate 362 / 525 (68.95%)
High Score xgd_fifth for 495.54 points (2 mins 42 secs)
Average Score 341.66 (for 362 correct submissions)
Used as: Division One - Level One:
Value 250
Submission Rate 530 / 538 (98.51%)
Success Rate 447 / 530 (84.34%)
High Score ahmed_aly for 248.32 points (2 mins 20 secs)
Average Score 220.30 (for 447 correct submissions)

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;
    for(int i=0; i < ret; i++)
        if(N-1-i < 0 || candles[N-1-i]==0)
            return ret-1;
    else candles[N-1-i]--;


MarblesInABag rate it discuss it
Used as: Division Two - Level Three:
Value 1000
Submission Rate 151 / 654 (23.09%)
Success Rate 26 / 151 (17.22%)
High Score flashfox for 752.61 points (17 mins 32 secs)
Average Score 467.69 (for 26 correct submissions)

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 (r-1, b-1). Similarly, if you instead draw a blue marble, you will move to the state (r, b-2), 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+r-2 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 n-2 marbles, we can use O(n) memory by keeping two arrays; one containing the answers from the n-2 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.

CandyGame rate it discuss it
Used as: Division One - Level Two:
Value 500
Submission Rate 342 / 538 (63.57%)
Success Rate 128 / 342 (37.43%)
High Score crazyb0y for 448.68 points (9 mins 50 secs)
Average Score 235.24 (for 128 correct submissions)

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 2d2-d1 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 rate it discuss it
Used as: Division One - Level Three:
Value 1000
Submission Rate 5 / 538 (0.93%)
Success Rate 2 / 5 (40.00%)
High Score Smylic for 454.57 points (44 mins 33 secs)
Average Score 441.88 (for 2 correct submissions)

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;

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;
        // If team already lost, invalid set
    if(loss[teamtable[loser]] > 0) return INVALID;
        // Otherwise update win-loss 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
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
// in all other cases the team loses; those cases are above


current = advancers;


// The winner is seed 0, now assign seeds
vector< string > finalSeeds(N, "");
queue< int > q;
finalSeeds[0] = teams[current[0]];

while(!q.empty() )
    int cur = q.front();
    int seed = 0;
    while(teams[cur]!=finalSeeds[seed]) seed++;
    int N1 = N;
    for(int i=0; i < gamesplayed[cur].size(); i++, N1/=2)
            finalSeeds[N1-1-seed] = teams[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;


By connect4
TopCoder Member