Match Editorial

Match summary

Round 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 25-30 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 cut-off 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 first-time target tomekkulczynski, krijgertje, marek.cygan and ahyangyi.

A few observations about the upcoming TCO onsites:

• 10 out of the current 11 targets will be there (SnapDragon overslept the first round).
• The lowest rated coder will be bhzhan, who started the tournament seeded 742.
• There are 4 coders who will compete in both the TCHS and TCO finals: Loner, Petr, Petr, and ahyangyi.

Congratulations to all the advancers!

The Problems

Value	250
Submission Rate	140 / 146 (95.89%)
Success Rate	106 / 140 (75.71%)
High Score	Eryx for 215.07 points (11 mins 51 secs)
Average Score	159.49 (for 106 correct submissions)

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 two-colored, which is an easy problem to solve by DFS.

Once we have the number of solitary nodes, the number of two-colorable components, and the number of mono-color 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,1-col)) 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;
  }
};

Value	500
Submission Rate	91 / 146 (62.33%)
Success Rate	39 / 91 (42.86%)
High Score	Petr for 411.10 points (13 mins 50 secs)
Average Score	271.29 (for 39 correct submissions)

Solution #1: Dynamic Programming

To 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 Approach

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

Value	1000
Submission Rate	1 / 146 (0.68%)
Success Rate	0 / 1 (0.00%)
High Score	No correct submissions
Average Score	No correct submissions

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 table

The idea behind a lookup table is to pre-calculate 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 locking

Consider 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.