Wednesday, September 14, 2005 Match summary For Division 1 coders, Wednesday's SRM proved to be quite challenging. krijgertje took home the gold on a problem set with a 500pointer solved by only 44 coders, and a 1050pointer 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 secondplace finisher onyx by over 65 points. Newcomers eric0 and elimgta took third and fourth place, respectively. The ProblemsPartyUsed as: Division Two  Level One:
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; }DVDPlayer Used as: Division Two  Level Two: Used as: Division One  Level One:
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[i1], pos.get(moviesWatched[i])); else pos.put(moviesWatched[i1], moviesWatched[i]); } List<String> ans = new ArrayList<String>(); for (String s : pos.keySet()) { if (s.equals(moviesWatched[moviesWatched.length1])  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; }Deque Sort Used as: Division Two  Level Three:
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(); }HardDequeSort Used as: Division One  Level Two:
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. Robot RaceUsed as: Division One  Level Three:
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 breadthfirst 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 highervalued 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]. 
