Match Editorial

The Problems

Value	300
Submission Rate	161 / 186 (86.56%)
Success Rate	141 / 161 (87.58%)
High Score	TangentZ for 296.11 points

Implementation

To solve this problem, simply iterate through the input list, keeping track of how many parties each group has accumulated. This can be done by using a mapping container. For each group in the list, increment the value associated with that group in the map. If no value is associated, initialize it to zero and then increment. As soon as a group's value is incremented to 3, return that group's name. If, after processing the input, no group's value reached 3, return "".

Value	500
Submission Rate	127 / 186 (68.28%)
Success Rate	113 / 127 (88.98%)
High Score	Sleeve for 476.79 points

Implementation

This problem turns out to be more of a parsing problem than anything else. For each combination in the list, you must parse it to determine the price and which books are included. Then it's a simple matter of looking up the cost for each book and subtracting from the sum the combination cost. Do this for each combination and return the greatest difference. Also note that if the greatest difference is negative, the value 0 should be what is actually returned.

For parsing each combination, one could tokenize with the ':' and ',' characters as delimiters. Or, if using C++, one could replace all instances of these delimiters with whitespace and then extract the elements with a stringstream.

Value	1000
Submission Rate	39 / 186 (20.97%)
Success Rate	13 / 39 (33.33%)
High Score	ps31 for 755.46 points

Implementation

This is the classic breadth-first search problem, seen numerous times on TopCoder and in various other programming challenges. The map can be interpreted as a graph. Each location in the map is a vertex, and an implicit edge of weight 1 exists between it and each of its 4-neighbors (the neighbors in the four cardinal directions). When all edges have weight 1, breadth-first search consists of starting at some set of points and generating all the unvisited points adjacent to points in that set. The process then repeats with this new set, until the destination point becomes included in the set. The number of iterations to generate each set is then the minimum distance from any point in the original set to each point in that set.

So, we construct a queue with a maximum capacity which is the size of the map (this is actually more than we need). The queue will contain tuples, each tuple representing a location in the map and an integer representing the cost of reaching this location from the starting point. Initially the queue contains exactly one tuple, representing the start location and the value 0. We also maintain a boolean array that, for each point in the map, specifies whether or not it has been visited by the breadth-first search.

Then, while the queue is not empty, we remove the first tuple and examine its location. We iterate through its 4-neighbors, and for each neighbor that has not been visited, we add it to the queue. When adding a location to the queue, we mark it as visited in the boolean array. We then add one to the previous location's cost to get the cost of reaching its neighbor. If the neighbor is the destination point, we can immediately return its cost. Otherwise we combine the location with the cost into a tuple and add it to the queue, and continue searching.

If the queue ever becomes empty, then that means there is no path from the source to the destination and return -1.

Value	250
Submission Rate	93 / 96 (96.88%)
Success Rate	65 / 93 (69.89%)
High Score	b0b0b0b for 247.57 points

Implementation

This problem is the more difficult counterpart to Division-II's Alcohol problem. In this problem, a group goes on probation only if it has three parties within a span of five days or less. Furthermore, rather than returning the first group that goes on probation, you must find all groups that go on probation, sort them in order of when they go on probation, and return this list.

One method is to build a map from the information in the input. The mapping will be from group names to lists of days on which they hold parties. To build this map, iterate through the input (keeping track of which day we're on). For the group that throws a party on day i, append the value i to that group's list.

Once we have a list of party days for each group, we can then determine on which day, if any, that group goes on probation. Suppose that a group's list has length n. We then see if list[i + 2] - list[i] < 5 for any 0 <= i < n - 2 (if using 0-based indexing). If so, we only consider the minimum i for which this holds, construct a tuple consisting of the group's name and list[i + 2], and add it to our list of groups on probation.

Once we do this for each group, we can then sort the list of tuples representing groups on probation. Simply sort them in ascending order of the second value in the tuple. We can then throw away the second values and simply return a list of group names.

Value	500
Submission Rate	69 / 96 (71.88%)
Success Rate	42 / 69 (60.87%)
High Score	radeye for 458.32 points

Implementation

Although this problem shares some of the same concepts as its Division-II counterpart, Booksale, its solution is actually very different. First, we parse each of the book combinations and store them in a list. Note that the statement specifies that there will be at most 15 such combinations. Therefore we can easily iterate through each combination of book combinations in under eight seconds.

To do this we iterate from 0 to 2ⁿ - 1 inclusive, where n is the number of book combinations there are. The binary representation of each iterated value represents a combination of book combinations; if bit i in the binary representation is 1, then the ith book combination is present in that combination.

For each combination of book combinations, we determine if it is valid and how much money it saves us. We count how many references there are to each book in each book combination in the combination, and ensure that no book is referenced more times than it is being bought. If the combination of book combinations passes this test, then it is easy to calculate how much money is being saved. We then subtract this from the amount it would cost to purchase all of the books without any deals, and see if it's less than the best price found so far.

Value	900
Submission Rate	42 / 96 (43.75%)
Success Rate	23 / 42 (54.76%)
High Score	WishingBone for 746.86 points

Implementation

The solution to this problem just consists of some very minor changes to our solution to Division-II's Bikepath problem. The major difference in this problem is that our edges no longer have the same weights. The type of surface we are biking on affects how long it takes to traverse it. To keep the problem as similar as possible to how it was described for the Division-II version, we will specify that the surface type of a location (vertex) specifies the weights associated with each of its incoming edges.

Now, we must adapt our breadth-first traversal so that it works for edges of different weights. We can no longer use a simple queue, because an ordinary queue simply orders vertices so that we visit them in ascending order of distance defined in terms of number of edges. This will not work for this problem, because there may be one path that traverses 3 edges that has a smaller cost than one that traverses 2 edges. Therefore we need a data structure that will order vertices based on the actual cost of reaching them.

For this we need a priority queue. This is just a queue where elements are removed in order of descending priority. For elements with the same priority, they are ordered just like in an ordinary queue. In this problem, a location has higher priority if it has a lower cost.

C++ provides a priority_queue data type, for which we can define a custom comparison operator (because by default our tuples will be ordered in the reverse of what we need). For other languages, one would have to implement one's own priority queue. This isn't too difficult. Priority queues are typically implemented with a heap. The preceding link gives a reasonably thorough overview of what a heap is, and provides algorithms for building a heap data structure.

If one already has a solution for Bikepath, changing it to solve this problem is simple. First, change the queue data type to a priority queue. Second, instead of adding 1 to generate a new cost each time, add the cost associated with travelling over the terrain of the vertex we just reached. Third, add 'P' locations to the list of types of terrain that are impassible. Finally, prevent traversal of terrains with a travel cost >= 5 that are 8-adjacent to a location of type 'P'. Each of these changes are fairly simple to do, making this problem only marginally more difficult than the Division-II version.