JOIN
 Match Editorial
SRM 116
Tuesday, October 15, 2002

# The Problems

Used as: Division-II, 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 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.

BossFight
Used as: Division II - Level 2 & Division I - Level 1:
 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.

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++){
}
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 v1 and v2, with v2>v1, and let bi be what the person valuing the item at vi bids for the item. If the b2 bid comes after b1, then b1 should equal v1, and b2 should be v1+1. If b1 were anything less than v1 (b1 can't be greater than v1), then the person bidding b2 could bid b1+1, which would be between b1 and v1, which is undesirable by the rules. Now, given the bid of b1, b2 should clearly be b1+1, as that is the minimum bid that is greater than b1 and less than v2. So, if values were {50,100}, the return would be {50,51}. If the order were reversed, and the b2 bid came first, then b2 would be v1, as anything less would allow b1 to be between b2 and v2. This leaves the b1 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.

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.

By lbackstrom
TopCoder Member