Match Editorial

In an exciting matchup between tomek and SnapDragon, the two coders at TopCoder who keep swapping first and second place, SnapDragon walked away the clear winner, even though he didn't win the division. Instead that honor went to venco, whose coding alone carried him to the top of the chart. Vedensky, a barely blue coder, propelled himself up 525 rating points when he took second place in his third competition. Another new coder, texel, took third, and has an impressive rating of 2545 after only 5 matches. tomek, whose score would have been good enough for 3rd place if not for his flawed level 3, dropped 175 rating points for coming in 52nd. SnapDragon, who finished very early in the match with a score which would have taken first, dropped to fifth due to a resubmission of his hard problem. He made up for it with a couple of successful challenges (using the test case that caused him to resubmit) to get into second place. But when he tried for the sweep of the 950's in his room with a killer timeout challenge against venco's correct 950 he dropped back to fourth. bstanescu (who was temporarily gray due to a bug in the ratings system) rounded out the top 5.

Division 2 had a harder time, having a level 3 problem that was quite similar to the Division 1 level 3 that only 4 coders were able to solve. Frodo_Baggins, the fastest submitter on the 1100 point hard, was still green dispite winning his division. In fact only 4 of the top 10 coders in division 2 made it to division 1, only one of those being a new coder.

One thing that made this match a little more hairy was a contradiction in the Div 1 250 / Div 2 500. Although it didn't affect most coders since the constraints were changed to disallow test cases which exploited the contradiction, some were left to swallow unnecessary resubmissions when they noticed the contradiction.

The Problems

Value	250
Submission Rate	176 / 186 (94.62%)
Success Rate	142 / 176 (80.68%)
High Score	Krzysan for 248.76 points (2 mins 0 secs)
Average Score	217.94 (for 142 correct submissions)

They don't get much simpler than this. The simplest method to solve this involves searching for a divisible number forwards and backwards. A number can be determined to be divisible by a base if the number MOD base is 0. Since the base can only be at most 500, you will have to search through at most 500 numbers to find the two limits. Once you have them, subtract them from the original number to get the difference. If the differences are equal, return the upper, otherwise, return the closest.

A shorter solution involves using the properties of integer division. If you divide an integer by an integer, then multiply the result by the base, you get the lower bound we are searching for. If you add base to the number before dividing, you can get the upper bound. Then you can perform the difference check. We can simplify this even further by adding half the base before dividing, which has the effect of producing the answer without having to check the differences! Thus the code can be written in one line:

return ((number + (base / 2)) / base) * base;

Value	500
Submission Rate	107 / 186 (57.53%)
Success Rate	95 / 107 (88.79%)
High Score	Krzysan for 454.37 points (9 mins 11 secs)
Average Score	295.00 (for 95 correct submissions)

Value	250
Submission Rate	155 / 163 (95.09%)
Success Rate	150 / 155 (96.77%)
High Score	SnapDragon for 245.60 points (3 mins 48 secs)
Average Score	190.29 (for 150 correct submissions)

At first glance, it seems like this problem may be NP-hard, since it asks you to verify that all sets of fans of size X or less can fail. However, the problem can be solved with a greedy algorithm which looks at the fans in order of increasing capacity.

First, we determine the Maximum Failure Set count. If the set of the smallest N fans can be a failure set, then the maximum failure set must have a count of N or greater. The reason is because any other set of fans with count N or greater is going to have the same or greater capacity. If the smallest N fans cannot be a failure set, then the MFS must have a count of less than N fans, for the same reason. Therefore, the count of the MFS is going to be N, where the smallest N fans is a valid failure set, but the smallest N+1 fans are not.

Next, we determine the Maximum Failure Count. For this, we want to find the minimum number of fans that would cause the system to fail, and the answer will be one less than that. Essentially, we can repeat the MFS algorithm but use the largest fans instead of the smallest. Any other set of N or less fans is going to have the same or less capacity, and therefore will not cause the system to fail. So the answer to the MFC is N-1, where the N largest fans are not a valid failure set, but the N-1 largest fans are.

Value	1100
Submission Rate	6 / 186 (3.23%)
Success Rate	4 / 6 (66.67%)
High Score	Frodo_Baggins for 764.32 points (20 mins 51 secs)
Average Score	605.53 (for 4 correct submissions)

Seasoned topcoders should be able to look at the limits on this problem and immediately realize that brute force is not the answer. With 50 types of coins, and a possible 1 billion cents to make up, brute force will most certainly time out. There actually is a trick to this problem, which lies in the constraints on the return money. Since there must be exactly one way to make up each amount of money, each coin must evenly divide the next highest denomination coin, and the highest denomination coin must evenly divide value + 1. Some intuition and working out on paper will give this fact away, but I shall actually prove it is true.

For the first part, I shall prove that when a coin type is the highest denomination, the only valid configuration is to use as many coins of that type as possible. Let's assign a value of N to that coin. If we use as many coins as possible, then the amount left over in value is less than N. Let's assume we could have used a maximum of X coins of denomination N, with a value < N left over. Let's try using Y coins of denomination N, where 1 <= Y < X. This means that the amount left over is greater than N. We'll call the set of coins that make up the remaining non-N coins S, and the sum of all the coin values in S will be denoted as |S|. For the next step, we'll repeatedly remove the smallest coin in S, and put it in another set S'. We do this until the value left in S is <= N. If the value of S is now N, then we have a contradiction because there can be only one means of paying the value N, but we could either use the coins in the set S, or a single N coin. In the case where the value of S is now < N, we just removed a coin valued at M. |S| + M is greater than N, because otherwise we would have stopped at N. Therefore 0 < N - |S| < M. Due to the rules, we must be able to make the value N - |S|, but we cannot use any coins from S, because all the coins are valued at M or greater. Therefore, the coins to make N - |S| must come from S'. If we take these coins, and add them back to S, |S| is now equal to N, and we again have a contradiction. Therefore, by contradiction, you must use all the coins possible of value N.

OK, that was the hard part, now, we must prove that N is divisible into value + 1. All the non-N coins in the set must add up to N-1. If the add up to less than N-1, then you cannot make the value N-1, which is a requirement of the answer. If they add up to more than N-1, then you have a contradiction as proven above. Therefore, value must equal N*X + N-1. If we add one to each side, we get value+1 = N*(X+1). Therefore, value+1 must be divisible by N.

To prove that each subsequently smaller coin must divide the next largest coin evenly, we remove all the coins of value N. This leaves a value of N-1. We now have the same situation as above, except the next lowest coin is now the highest, and the value is N-1. Since we already have proven it must divide N evenly, we are done.

Given all this information, we can use a greedy approach to figuring out which coins should be present. If we sort the coins and start with the highest denomination, we don't have to do any comparisons. We use each coin if it can be used, and then move down to the next lowest coin. Each time we use a coin of a value v, we reduce the total value to v-1, and repeat on the next coin. This all adds up to about 5 lines of code.

The last step is to map back the sorted coin amounts to the original order of the coins. This step can be done with two for loops, as the input size will allow for.

Value	500
Submission Rate	106 / 163 (65.03%)
Success Rate	69 / 106 (65.09%)
High Score	SnapDragon for 442.44 points (10 mins 31 secs)
Average Score	292.96 (for 69 correct submissions)

This problem was inspired by my cell phone. It has 3 states, changed by holding down a button. One of the states vibrates when it is entered. Therefore, I can figure out what state it is in without looking at it by pressing the button until it vibrates, and then proceeding to the desired state.

To solve this problem, we'll simulate starting from any given state, and keep track of which states it is possible to be in. At the beginning, any state is possible. The order of feedback is dictated by which state the device is actually in. Each time we advance a state, we record which states are eliminated. I solved this by using a 50-bit integer where each 1-bit represented a possible state. Once there is only one state left, and it is the target state, we have found the answer.

A difficulty arises when the entire machine consists of a repeated sequence. Because the sequence repeats, we can't tell which part of the state machine we are in. In this case, we will never get down to one state. However, we can notice that in cases where the state machine is not repeating, we will go through at most all the states until we narrow down to one possible state. Therefore, we can limit our simulation to about 150 iterations, and if it is not done by then, return -1.

Value	950
Submission Rate	18 / 163 (11.04%)
Success Rate	9 / 18 (50.00%)
High Score	Eryx for 619.73 points (23 mins 33 secs)
Average Score	530.62 (for 9 correct submissions)

This problem is almost exactly the same as ChangePurse (the Div 2 hard), but for one small detail. We want the set with the smallest number of coins, regardless of denomination. Ties are broken by sets which have more higher denomination coins. The same explanation applies, however, we must now try every combination of coins since, as the problem statement shows, the answer may not contain the highest possible coin. Essentially, this requires some sort of dynamic programming or heuristics, as a DFS may time out. In one case, each coin was a power of two, meaning that all coins divided evenly into each other. This would turn a DFS into an O(2ⁿ) solution.