Match Editorial

For Division 1 coders, Wednesday's SRM proved to be quite challenging. krijgertje took home the gold on a problem set with a 500-pointer solved by only 44 coders, and a 1050-pointer solved by no one. The problem set didn't sit well with tomek, whose resubmission of the easy problem (and unsuccessful attempt at solving the medium using a probabilistic algorithm) dropped his rating to 2996, causing him to lose his target for the first time in two years.

Meanwhile in Division 2, loveislife breezed through all three problems in a whopping 33 minutes and made two successful challenges, beating second-place finisher onyx by over 65 points. Newcomers eric0 and elimgta took third and fourth place, respectively.

The Problems

Value	250
Submission Rate	221 / 342 (64.62%)
Success Rate	183 / 221 (82.81%)
High Score	vlad_D for 242.05 points (5 mins 11 secs)
Average Score	166.03 (for 183 correct submissions)

The fastest way to solve this problem is to build a table of which people know which names, and simply walk through each handshake from first to last, updating the values in the table. The table can be stored as a two dimensional array of boolean values, or as an array (or map) of integer sets. Java code follows:

public double averageNames(int n, int[] personA, int[] personB) {
  boolean[][] know = new boolean[n][n];
  for (int i=0; i < n; ++i)
    know[i][i] = true; // everyone knows their own name
  for (int i=0; i < personA.length; ++i)
    for (int j=0; j < n; ++j)
      if (know[personA[i]][j] || know[personB[i]][j])
        know[personA[i]][j] = know[personB[i]][j] = true;
  double total = 0;
  for (int i=0; i < n; ++i)
    for (int j=0; j < n; ++j)
      if (i != j && know[i][j])
        total += 1;
  return total / n;
}

Value	500
Submission Rate	142 / 342 (41.52%)
Success Rate	104 / 142 (73.24%)
High Score	yiming for 462.72 points (8 mins 11 secs)
Average Score	278.07 (for 104 correct submissions)

Value	250
Submission Rate	292 / 315 (92.70%)
Success Rate	270 / 292 (92.47%)
High Score	haha for 239.44 points (6 mins 1 secs)
Average Score	175.12 (for 270 correct submissions)

To solve this problem, we must keep track of the matchings between DVDs and DVD cases (including the DVD player, which can be treated as if it were a case). Most solutions used a mapping of strings onto strings (HashMap<String, String> in Java, or map<string, string> in C++) to keep track of this mapping. It didn't matter whether the map's keys were the DVDs or the cases -- your program keeps track of the locations of DVDs in the first version, and the contents of the DVD cases in the second version. Java code follows:

public String[] findMovies(String[] moviesWatched) {
  Map<String, String> pos = new HashMap<String, String>(); // DVDs are the keys
  for (int i=1; i < moviesWatched.length; ++i) {
    if (pos.containsKey(moviesWatched[i]))
      pos.put(moviesWatched[i-1], pos.get(moviesWatched[i]));
    else
      pos.put(moviesWatched[i-1], moviesWatched[i]);
  }
  List<String> ans = new ArrayList<String>();
  for (String s : pos.keySet()) {
    if (s.equals(moviesWatched[moviesWatched.length-1])
        || pos.get(s).equals(s)) continue;
    ans.add(s + " is inside " + pos.get(s) + "'s case");
  }
  String[] ans2 = ans.toArray(new String[0]);
  Arrays.sort(ans2);
  return ans2;
}

Value	900
Submission Rate	44 / 342 (12.87%)
Success Rate	23 / 44 (52.27%)
High Score	phoenixinter for 870.73 points (5 mins 14 secs)
Average Score	632.93 (for 23 correct submissions)

To start off, you know that the contents of each deque will need to always be sorted, since they have to be combined into a single, sorted list at the end. As it turns out, this problem can be solved with a simple greedy solution. All you need are two arrays of ints to keep track of the first and last elements of each deque you've created. Then you iterate through each element in data, and decide if you can safely push it onto the front or back of any preexisting deque. You can safely push data[i] onto the front of deque d if and only if there are no numbers strictly between data[i] and d.front anywhere in the data; the same is true about pushing onto the back of a deque. If you can't safely push the number onto any deque, you have to create a new deque with it. C++ code follows:

int minDeques(vector<int> data) {
  vector<int> fronts, backs;
  for (int i=0; i < data.size(); i++) {
    bool hasBeenPushed = false;
    for (int j=0; j < fronts.size(); j++) {
      if (data[i] < fronts[j]) {
        bool isSafe = true;
        for (int k=0; k < data.size(); k++)
          if (data[i] < data[k] && data[k] < fronts[j])
            isSafe = false;
        if (isSafe) {
          fronts[j] = data[i];
          hasBeenPushed = true;
          break;
        }
      }
      if (data[i] > backs[j]) {
        bool isSafe = true;
        for (int k=0; k < data.size(); k++)
          if (data[i] > data[k] && data[k] > backs[j])
            isSafe = false;
        if (isSafe) {
          backs[j] = data[i];
          hasBeenPushed = true;
          break;
        }
      }
    }
    if (!hasBeenPushed) {
      fronts.push_back(data[i]);
      backs.push_back(data[i]);
    }
  }
  return fronts.size();
}

Value	500
Submission Rate	97 / 315 (30.79%)
Success Rate	44 / 97 (45.36%)
High Score	rem for 453.88 points (9 mins 14 secs)
Average Score	274.41 (for 44 correct submissions)

The only difference between this problem and DequeSort is that duplicate values are permitted in HardDequeSort's data. Because of this, the greedy solution outlined above will fail on inputs such as {3,6,0,9,6,3}. To solve this version, you can make a copy of the input into a new list, sort this list, and remove all duplicates from it. The elements of this new list ({0,3,6,9} for the above example) now correspond to the smallest, second smallest, third smallest, etc. values that we observe in data. From here, you need to calculate the largest deque that can be built which contains every instance of the n smallest observed values. In the example above, you could successfully build a deque out of all the 0's, and out of all the 0's and 3's, but it's impossible to build a sorted deque with all the 0's, 3's, and 6's (processed in the order specified in data, e.g. {3,6,0,6,3}). Afterwards, you simply increment the number of deques you've built by one, remove all the 0's and 3's from the input data, and repeat this process until the input data is empty.

Value	1050
Submission Rate	2 / 315 (0.63%)
Success Rate	0 / 2 (0.00%)
High Score	null for null points (NONE)
Average Score	No correct submissions

There were two parts to the solution of this problem. First, you have to figure out how many seconds it would take for any robot to obtain any token on the board. This time matrix can be built by running a breadth-first search of the board starting at each robot. Once the time matrix is calculated, the second part of this problem reduces to figuring out which tokens on a robot's list will be impossible for him to reach in time. This seems hard at first, because robot "a" might end up collecting token "X" even if robot "b" could reach it faster, if robot "b" finds a higher-valued token for himself that he can safely collect.

To solve this problem, imagine what would happen if every robot attempted to collect his $100 token. Either every robot will end up with a different token, in which case they all take home $100, or there will be at least one token that is desired by multiple robots. Let's say robots "a" and "b" both value token "X" at $100, but "a" can reach it within five seconds while "b" takes seven seconds. At this point, robot "b" knows that he will never be able to acquire token "X" -- either "a" will be holding the token by the time "b" arrives, or another robot even faster than "a" will be holding it. Therefore, "b" can cross his top choice, token "X", off his list. He then repeats the process, now hoping to be the first one to collect his $99 token. Every time that multiple robots desire the same token, one of them realizes that he will never reach it in time. Therefore, this process is guaranteed to eventually terminate.

For more information, try a Google search on [stable marriage algorithm].