
Match Editorial 
SRM 116Tuesday, October 15, 2002
The Problems
BinaryPad
Used as: DivisionII, Level 1:
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 counterclockwise 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.
BossFight
Used as: Division II  Level 2 & Division I  Level 1:
DivII 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

DivI 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.
LongDistance
Used as: Division II  Level 3:
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));
}
PriceIsRight
Used as: Division I  Level 2:
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_{1} and v_{2}, with v_{2}>v_{1}, and let b_{i} be what the person valuing the item at v_{i} bids for the item. If the b_{2} bid comes after b_{1}, then b_{1} should equal v_{1}, and b_{2} should be v_{1}+1. If b_{1} were anything less than v_{1} (b_{1} can't be greater than v_{1}), then the person bidding b_{2} could bid b_{1}+1, which would be between b_{1} and v_{1}, which is undesirable by the rules. Now, given the bid of b_{1}, b_{2} should clearly be b_{1}+1, as that is the minimum bid that is greater than b_{1} and less than v_{2}. So, if values were {50,100}, the return would be {50,51}. If the order were reversed, and the b_{2} bid came first, then b_{2} would be v_{1}, as anything less would allow b_{1} to be between b_{2} and v_{2}. This leaves the b_{1} 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.
RobotSquirrel
Used as: Division I  Level 3:
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.
 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.
 Only try to pick up after a move, a call to sub, or at the beginning of sub or main.
 Only turn (possibly a UTurn) 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.
By
lbackstrom
TopCoder Member