Match Editorial

Match summary

This match was marked by Petr achieving a new record high TopCoder rating of 3756, 3 points higher than the record he set nearly a year ago. Congratulations, Petr!

In division I, coders faced a simulation-based easy problem, followed by a medium that required a lot of thinking but a relatively small amount of coding, and a hard that was tricky to implement correctly. The top three coders in the division, Petr, yuhch123 and ardiankp were all placed in the same room, which is unfortunate considering that prizes were available this match.

In division II, the hard problem was too tricky to get any passing submissions, so competitors fought it out on the easy and medium problems. ngg won the division, division II veteran dimitarmisev made the jump to division I after capturing second place and guilherme took third place.

The Problems

Value	250
Submission Rate	725 / 808 (89.73%)
Success Rate	675 / 725 (93.10%)
High Score	dilse for 249.68 points (1 mins 1 secs)
Average Score	197.16 (for 675 correct submissions)

Consider each time unit in turn. At each step, we either reach the end of the journey or we continue driving for the whole time unit. If the remaining distance we have to travel at the beginning of time unit i is d_i, and this value is less than speedLimit[i], then the extra amount of time it'll take us to complete our journey is d_i / speedLimit[i]. Otherwise we move on to the next time unit with d_i+1 = d_i - speedLimit[i]. Because the minimum speed limit is 1, we never have to simulate this for more than 100,000 time steps. C++ code follows.

int N = speedLimit.size();
for (int i=0; ;i++)
  if (journeyLength < speedLimit[i % N])
    return (double) journeyLength / speedLimit[i % N] + i;
  else
    journeyLength -= speedLimit[i % N];

Value	500
Submission Rate	390 / 808 (48.27%)
Success Rate	220 / 390 (56.41%)
High Score	guilherme for 465.37 points (7 mins 52 secs)
Average Score	280.85 (for 220 correct submissions)

Value	250
Submission Rate	559 / 581 (96.21%)
Success Rate	467 / 559 (83.54%)
High Score	JongMan for 247.58 points (2 mins 48 secs)
Average Score	193.91 (for 467 correct submissions)

To those coders who got a sense of déjà vu reading this problem I apologise! It was found after the match to be identical to InstantRunoff from SRM 175. We do make an effort to check that problems are original, at least within TopCoder, but unfortunately this one slipped through the net.

The problem itself is pure simulation, so simply follow the instructions carefully to get to the right answer. Many competitors misread the statement and took the voter preferences to be the candidates in the order that the voters will vote for them on subsequent rounds. This is not the case, because a voter will vote for the candidate highest on his list who has not yet been eliminated, regardless of what round he is voting in. Another common mistake was to be careless with the terminating condition, leading to an infinite loop after all candidates have been eliminated.

For an example solution, see humblefool's code.

Value	1000
Submission Rate	30 / 808 (3.71%)
Success Rate	0 / 30 (0.00%)
High Score	No correct submissions
Average Score	No correct submissions

This problem elicited plenty of submissions, but unfortunately none were correct. A big hint here is the constaint on the number of elements in itinerary: whenever you see a constaint of 16 items or fewer in a problem where you are trying to build a set of something from some subsets, you should immediately consider solutions that are exponential in this dimension (i.e., the state-space is determined by some subset of these items). This problem is no exception to this rule.

Firstly, however, let's rewrite the problem in graph theory language. The countries clearly form the vertices of a graph and the adapters become directed edges. Jane can charge her laptop in any country if the vertex representing that country is reachable from the vertex representing homeCountry. The question therefore becomes, "what is the minimum number of edges that we must add to the graph to ensure that every vertex in itinerary is reachable from homeCountry?"

The next key point is to realise that we might as well only add edges that originate at homeCountry. To see this, consider that if we want to make a vertex connected, we can ether add an edge to it directly from homeCountry or we can add an edge from some other connected vertex. Either way, the effect is exactly the same, so we might as well only consider connecting vertices directly to homeCountry. This reduces the number of new edges that we need to consider to N, where N is the total number of countries (be careful, there can be up to 117 different countries).

We now need to work out what is the minimum number of these edges we should add, in order that all the vertices in itinerary are reachable. This is a fairly standard dynamic programming problem: the state-space we need to explore is f(i, S), where we have already considered all the edges up to index i and S is the subset of vertices in itinerary that are already reachable from homeCountry. We can then consider either adding the current edge with index i, or omitting it to get the recursion relation. If T is the subset of additional vertices that would be connected due to edge i then:

In order to work out what additional vertices are connected due to an edge, it helps to pre-calculate the transitive closure. C++ code follows.

class PowerAdapters{
public:
  int needed(vector <string> adapters, 
             vector <string> itinerary, string homeCountry){
    map <string,int> names;
    
    // First we need to translate from names to indexes
    // Assign each name we come across a unique index
    int N = 0;
    names[homeCountry] = N++;
    for (int i=0;i<itinerary.size();i++)
      if (names.find(itinerary[i]) == names.end())
        names[itinerary[i]] = N++;
    for (int i=0;i<adapters.size();i++){
      stringstream ss(adapters[i]);
      string s1,s2;
      ss >> s1 >> s2;
      if (names.find(s1) == names.end())
        names[s1] = N++;
      if (names.find(s2) == names.end())
        names[s2] = N++;
    }
    
    // Now work out what is connected to what
    vector <vector <int> > conn(N,vector <int> (N));
    for (int i=0;i<adapters.size();i++){
      stringstream ss(adapters[i]);
      string s1,s2;
      ss >> s1 >> s2;
      conn[names[s1]][names[s2]] = true;
    }
    for (int i=0;i<N;i++)
      conn[i][i] = true;
      
    // Transitive closure
    for (int k = 0;k < N;k++)
      for (int i = 0;i < N;i++)
        for (int j = 0;j < N;j++)
          conn[i][j] |= conn[i][k] && conn[k][j];
          
    int M = itinerary.size();

    // Now work out which countries cover which countries in itinerary
    vector <int> cover(N);
    for (int i = 0;i < N;i++)
      for (int j = 0;j < M;j++)
        if (conn[i][names[itinerary[j]]])
          cover[i] |= (1<<j);
          
    int mem[1 << M];
    
    // initialize mem to large values
    memset(mem,0x1f,sizeof(mem)); 
    
    // At the start we are already covering all the vertices connected from 
    // homeCountry
    mem[cover[0]] = 0;
    
    // Run our dynamic program
    for (int i=0;i<N;i++)
      for (int j=(1 << M) - 1;j>=0;j--)
        mem[j | cover[i]] = min(mem[j | cover[i]], mem[j] + 1);
        
    return mem[(1 << M) -1];
  }
};

Value	500
Submission Rate	265 / 581 (45.61%)
Success Rate	194 / 265 (73.21%)
High Score	Petr for 456.18 points (8 mins 58 secs)
Average Score	267.34 (for 194 correct submissions)

This problem required clear thinking, but actually isn't very difficult once you see what to do. The definitions in the notes section are key here:

• A segment can be considered definitely to be working, if no configuration exists, consistent with the described behavior, in which it is broken.
• A segment can be considered definitely to be broken, if no configuration exists, consistent with the described behavior, in which it is working.
• If neither of the above conditions is true for a segment, there is no way of being sure whether it is broken or not.

Consider any configuration of working/broken segments and ask, "Is it possible to check whether such a configuration is valid?" This is quite easy, since once we know whether the segments are broken or not, we can simulate the display for every symbol in the allowed set and work out what it would show. So we just check that each of the patterns corresponds to some symbol. If there is a pattern that cannot be generated using the allowed symbols, then the configuration cannot be consistent with the data given. Using arrays, this check takes O(N*M*S) time, where N is the number of symbols, P is the number of patterns and S is the number of segments. Using 64-bit bitmasks, this can be reduced to O(N*M).

boolean valid(String [] symbols, String [] patterns,boolean [] working){
  // For each pattern, try to find a symbol that is consistent
  for (int i=0;i<patterns.length;i++){
    boolean found = false;
    for (int j=0;j<symbols.length;j++){
      boolean valid = true;
      for (int k=0;k<patterns[i].length();k++)
        if ( (working[k] && symbols[j].charAt(k) == '1' ? '1' : '0') != patterns[i].charAt(k))
          valid = false;
      if (valid) found = true;
    }
    if (!found) return false;
  }
  return true;
}

A first-pass attempt might therefore be to consider every possible configuration, check for validity, and keep track of which segments have only appeared as working, which have only appeared as broken, and which have appeared in both states. Unfortunately, with 50 segments, there are 2⁵⁰ possible configurations, so such an approach is bound to time out.

We therefore need to prune our search somewhat. Consider a segment that has been observed in an on-state in some pattern. There is no way that this segment could be consistent with the behaviour, "...remains permanently in an off state...", so it has to be working. Any other segment does remain permanently in an off-state, so there is no way that its behaviour could be inconsistent with it being broken. We can therefore check that a consistent solution exists: create a configuration where each segment which has been observed on is working, every other segment is broken and check this for validity. If this is not a valid configuration, we can return "INCONSISTENT" straight away, because changing any of the working segments to broken would only ensure that the configuration is inconsistent, and changing any of the broken segments to working cannot make a difference, since these segments have never been observed in an on-state anyway.

We can then check whether any of the broken segments could be working. For each one in turn, set it to working and check whether the configuration is still valid. If so, then we have found configurations where it is both broken and working, so by the initial definitions, its state is uncertain. Otherwise, no change to the other segments will ever make this configuration valid, so again by the definitions, this segment must be broken.

public String brokenSegments(String [] symbols, String [] patterns){
  
  boolean [] working = new boolean[symbols[0].length()];

  // Find all of the segments that have been observed in an on-state
  for (int i=0;i<patterns.length;i++)
    for (int j=0;j<patterns[i].length();j++)
      if (patterns[i].charAt(j) == '1')
        working[j] = true;

  if (!valid(symbols,patterns,working)) return "INCONSISTENT";

  String ret = "";
  
  // Now try each segment in turn and set it to working
  for (int i=0;i<working.length;i++){
    if (working[i])
      ret += 'Y';
    else {
      working[i] = true;
      if (valid(symbols,patterns,working)) ret += '?';
      else ret += 'N';
      working[i] = false;
    }
  }

  return ret;
}

The solution here is much simpler to implement using bitmasks, because the set operations union, intersection and complement correspond to the boolean operators '|', '&', and '~' and it is therefore possible to consider all segments simultaneously. After parsing the input strings into bitmasks, the code becomes:

  long long working = 0;
    
  for (int i=0;i<p.size();i++)
    working |= p[i];
      
  long long broken = 0;
  
  for (int i=0;i<p.size();i++){
    long long newBroken = (1LL << N) - 1LL;
    bool consistent = false;
    for (int j=0;j<s.size();j++)
      if ((s[j] & working) == p[i]){
        consistent = true;
        newBroken &= s[j] & ~p[i];
      }
    broken |= newBroken;
    if (!consistent) return "INCONSISTENT";
  }
  
  string ret(N,' ');
  for (int i=0;i<N;i++)
    ret[i] = working & (1LL<<i) ? 
                        'Y' : broken & (1LL<<i) ? 'N' : '?';

  return ret;

Value	1000
Submission Rate	8 / 581 (1.38%)
Success Rate	3 / 8 (37.50%)
High Score	yuhch123 for 512.96 points (35 mins 52 secs)
Average Score	476.86 (for 3 correct submissions)

While not theoretically too challenging, this problem required a lot of care to code properly. Many coders will have quickly seen that the way to proceed is by binary search on the transceiver radius R. This function is obviously monotonic, so as long as we can answer the question, "given a value of R, are the aircraft connected to the Internet for all time?" we will be able to converge to the correct answer.

We therefore need to consider how the connectivity of the graph changes in time. For time T < 0, we know that all the aircraft are sitting at airports, so they are all a distance of 0 from an airport, so must be connected. As time gets large, all the aircraft land, so they are once again connected. Now we just need to determine whether there is a period of time in between where some aircraft becomes disconnected. The way to do this is by realising that if the graph connectivity has changed, then it means that some aircraft has either come into range or gone out of range of an airport or another aircraft. So right at the point in time where the connectivity changes, the distance between two aircraft, or an aircraft and an airport must be exactly R. These "events" mark the only points in time where the graph connectivity can change. We can therefore divide time up into ranges by these points and we only need to due a single connectivity check in each range, since the connectivity must be constant for the duration of the range. Doing a connectivity check at a known point in time with a known transceiver radius is simple using either depth-first search or breadth-first search.

The time complexity of the above method is O(N⁴ * log(M)), where N is the number of aircraft and M represents the initial binary search limits. With the low constraints (N = 20), this runs in time reasonably comfortably. For an example of this method but using Floyd's algorithm for the connectivity check, see yuhch123's code.