Match Editorial

The Problems

Value	300 points
Submission Rate	210 / 223 (94.17%)
Success Rate	198 / 210 (94.29%)
Average Score	246.07 points
High Score	CowGame for 292.27 points

Nothing too tricky in this problem. The most straightforward way to solve this was to look at each pair of two adjacent characters and figuring out if the second character was clockwise or counter-clockwise from the first. It was easy enough to just use a bunch of if statements, since there were only 6 cases. A little bit of modular arithmetic and could save some typing, but probably wasn't worth the trouble.

Div-II stats
Value	500 points
Submission Rate	159 / 223 (69.96%)
Success Rate	111 / 159 (69.81%)
Average Score	300.22 points
High Score	grepjava for 481.65 points

Div-I stats
Value	250 points
Submission Rate	136 / 136 (100.00%)
Success Rate	119 / 136 (87.50%)
Average Score	199.93 points
High Score	venco for 242.55 points

For each encounter with the boss, there are two numbers which are interesting. The obvious one is the sum of all attacks for the encounter. We know that this number is enough to defeat the boss, so the minimum of this number over all encounters is the second element of the return. For example, if one encounter totaled 10 damage, and another encounter totaled 8 damage, we know that 8 damage is enough to defeat the boss. The second number of interest is the sum of all of the attacks except the last. We know that each time, this sum was not enough to defeat the boss, and thus the boss has at least this sum plus one health. So, the first element must be the maximum of the sum of all numbers but the last, plus one. The only other thing to do is map the names of the attacks to the amount of damage they do. Java's HashMap, or it equivalent does this pretty easily.

Value	1100 points
Submission Rate	49 / 223 (21.97%)
Success Rate	3 / 49 (6.12%)
Average Score	531.17 points
High Score	smai for 536.88 points

This problem can be decomposed into two parts. The first is finding which phone companies will given the minimum rate for each call. The second is to determine the fewest number of phone companies that can be used to get all of the calls at the minimum rate. For the first part we have to be able to evaluate the lowest rate that we can get for a given call, with some phone company. There are only a few cases for this, which can be handled without too much trouble. The first is when the per minute rate is cheaper for the extra minutes, than it is for the initial minutes. In this case, there is no reason to call back. In the other case, when it is cheaper per minute for the initial minutes, it makes sense to call back whenever there are more minutes left to talk then the initial minutes of that company. For this second case, there may be a few extra minutes left over at the end, and it must be determined if those few extra minutes would be cheaper at the per minute rate, or the initial rate. Once you figure out which companies will give you the cheapest rate on each call, you remember those companies and go on the second part of the problem.

In the second part, you have to figure out the fewest number of times you can switch phone companies, which is the same as the fewest companies that you can use. The simplest way to do this is to set up a bit mask for each call, which represents which companies give you the lowest rate for each call. So, you have an int[], whose elements correspond to the calls, and the bits of the elements correspond to the companies that will give you the lowest rate. Then you iterate though all possible combinations of companies, and check the bit mask for each call.

int[] callBitMasks;
for(int i = 0; i<(1<<(numberOfCompanies)); i++){
   boolean acceptable = true;
   for(int j = 0; j<callBitMasks.length; j++){
      acceptable = acceptable && (i&callBitMasks[j])>0;
   }
   if(acceptable)ret = min(ret,cardinality(i));
}

Value	600 points
Submission Rate	52 / 136 (38.24%)
Success Rate	9 / 52 (17.31%)
Average Score	310.40 points
High Score	SnapDragon for 403.30 points

This problem looks very difficult at first, but turns out to have a very simple, greedy solution. Everyone want to bid as low as they can, but no one wants to bid so low that someone else will be willing to bid more than them, but less than they value the item at. The key two sentences in the problem statement are: "Let V be equal to the amount that he or she believes the item to be worth. The contestant should bid an amount, B, as low as possible (definitely less than or equal to V) such that no other contestant will bid an amount between B and V, inclusive." To solve this, lets start by looking at the two highest values, call them v₁ and v₂, with v₂>v₁, and let b_i be what the person valuing the item at v_i bids for the item. If the b₂ bid comes after b₁, then b₁ should equal v₁, and b₂ should be v₁+1. If b₁ were anything less than v₁ (b₁ can't be greater than v₁), then the person bidding b₂ could bid b₁+1, which would be between b₁ and v₁, which is undesirable by the rules. Now, given the bid of b₁, b₂ should clearly be b₁+1, as that is the minimum bid that is greater than b₁ and less than v₂. So, if values were {50,100}, the return would be {50,51}. If the order were reversed, and the b₂ bid came first, then b₂ would be v₁, as anything less would allow b₁ to be between b₂ and v₂. This leaves the b₁ bidder with no possible bids, and thus he has to bid -1. So if values were {100,50} the return would be {50,-1}.

Once you understand the behavior of the top two people, you can then inductively determine the behavior of the next two. Since the top two people both bid at least the minimum of the top two values, the next two people don't have to worry about them, as they will value the item lower than either of the two bids are for. If there are an odd number of people, then the person who values the item the lowest doesn't have to worry about anyone else, and can just bid 1.

So, the key to solving this problem is to observe that the bids of the two people who value the item the highest will not effect the bids of anyone else, and then use this observation inductively.

Value	1100 points
Submission Rate	9 / 136 (6.62%)
Success Rate	4 / 9 (44.44%)
Average Score	561.60 points
High Score	John Dethridge for 706.68 points

This problem turned out two be a case of optimized brute force. If you tried to enumerate all of the possible programs, you ended up with somewhere around 729,000,000 possible programs. However, a lot of those programs do the same thing as a lot of other programs, and the trick is to try to reduce the number of programs looked at when generating them. Here are a few optimizations that I came up with, and I imagine there are some more.

1. Never use instruction 5 anywhere but the end of sub or main. This is done easily be generating main and sub with any length from 1 to 6. direction, and there is no point in being able to turn around to both the left and the right.
2. Only try to pick up after a move, a call to sub, or at the beginning of sub or main.
3. Only turn (possibly a U-Turn) after a move, a call to sub, or at the beginning of sub or main.

Just these three optimizations reduce the search space to less than half a million possible programs, which is quite manageable.

After you generate sub and main, you essentially run the program, and collect the nuts. You have to watch out that you don't collect the same nuts more than once, but it isn't too difficult.