Match Editorial

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

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;
}

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)

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;
while(true)
{
    Arrays.sort(candles);
    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]--;
    ret++;
}

}

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.

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 2^d2-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;



}

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;
    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 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
    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[N1-1-seed]=="")
        {
            finalSeeds[N1-1-seed] = 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;

}