Match Editorial

		MATCH EDITORIAL LINKS:
	Room 1 Review Archive   Rookie Review Discuss this match   Problem Set Want to write a feature?

Division 1 - 275 - Shade
Everyone pretty much took the same approach to solving this problem: create a big two-dimensional array, fill it in according to the elements in the coordinates array, and then count all the ones filled in. The two most common mistakes that I saw were people getting their indices backwards, and people making the incorrect assumption that x1 < x2 and y1 < y2.

Division 1 - 475 - Dial
The first step to solving this problem is to parse all of the relationships between the digits. For each rule, there is a relationship between two digits that says that the two digits must come, one after the other. Once you have this figured out you can solve the problem using recurrence. First, check that the first digit doesn't have to be after some other digit and that there are no digits which must be before or after two distinct digits. If those conditions are not met, return 0, otherwise, try to find valid sequences by recursively adding one digit at time and keeping track of which digits have been used. If at any point the last digit in the sequence must come before another digit, then use that digit next. If there are not restrictions, then recursively try to add each unused digit to the sequence. See malpt's solution for an examples of exactly this. The quickest solution to code was to use the C++ function next_permutation and then just look at every sequence to check if it was valid. See DjinnKahn's solution for an examples of this.

Division 1 - 1000 - Battery
Solving this problem required more intuition than knowledge of any algorithmic technique. With up to 50 candles, it is obviously impossible to try every combination, or even to try some small subset of every combination. The key is to note that a candle contributes the most when it is burning in conjunction with the most candles. So, if we ignore the restriction about minimum recharge time, then the best way to burn them is to start them all at once. In order to take the minimum burn time into account, we take the longest burning candles, and start them later than the rest, so that we can have some candle burning for the minimum time. We select the longest burning ones because they have the lowest contribution to burn time ratios. Thus, the basic algorithm is to sort the candles by length and select enough of the candles, starting with the longest, that the minimum will be exceeded. Since we don't want to exceed the minimum if possible, we will overlap two of these candles so that the minimum is exactly reached. Then, all of the other candles are started at the same time as the overlap and burn for their duration. thekcc's beat everyone else by implementing this in fourteen minutes.