
Match Editorial 
SRM 114Tuesday, September 24, 2002
The Problems
Snail
Used as: DivisionII, Level 1:
Value

250 points 
Submission Rate

235 / 256 (91.80%)

Success Rate

195 / 235 (82.98%)

Average Score

225.28 points

High Score

slowjoe for 248 points

Most people got this one pretty easily. You just had to set up a simple loop to count the number of days, and update the position of the snail within the well for each day. Once the position on any given day is outside of the well, it 's time for the function to return:
int days=0;
while (depth>0) {
days++;
depth=dayUp;
if (depth<=0) return days;
depth+=nightDown;
}
The areas where most people made mistakes on this one were starting with the wrong day (i.e. starting at 1 instead of 0) and using the wrong exit condition (i.e. depth==0 instead of depth<=0).
Reference Implementation: Penwiper, practice room
DirSort
Used as: Division II  Level 2 & Division I  Level 1:
DivII stats

Value

600 points 
Submission Rate

172 / 256 (67.19%)

Success Rate

118 / 172 (68.60%)

Average Score

372.12 points

High Score

Wombat80 for 569.90 points

DivI stats

Value

350 points 
Submission Rate

141 / 146 (96.58%)

Success Rate

128 / 141 (90.78%)

Average Score

273.11 points

High Score

ZorbaTHut for 344.15 points

As is evident from the above statistics, most people were able to submit this problem, and most ended up solving it successfully. The obvious approach for this problem was to implement a simple loop or nested loops to sort the directories in increasing order. The code that you use to compare two directories must first compare the directories on the basis of how many "forwardslashes" they have. The fewer the number of forwardslashes, the earlier the directory should be in the returned string array. If two given directories have the same number of forward slashes it becomes necessary to implement some sort of comparison function to see which one should come first.
The comparison function used to compare two directories with equal numbers of forwardslashes should lexicographically compare the text between each set of forward slashes, starting with the text between the first set of forwardslashes. The comparison function should return as soon as the text being compared differs, i.e. it could return 1 to indicate that directory1 is less than directory2, or +1 to indicate that directory1 is greater than directory2.
Virtually everyone had the right idea for this problem. The mistakes that were made were usually indexing problems or string out of bounds errors.
Tile
Used as: Division II  Level 3:
Value

900 points 
Submission Rate

49 / 146 (33.56%)

Success Rate

3 / 49 (6.12%)

Average Score

421.59 points

High Score

vorthys for 590.86 points

Only three coders (vorthys, puzzlehacker, and vesko8) managed to solve this problem correctly. Given the low submission numbers and success rate for this problem, it probably should have been worth a bit more. All three of them used dynamic programming in their solutions. If you tried to solve this problem by trying all of the tile combinations until you got beyond 100,000, then your solution would time out for situations in which there are a large number of tiles that do not add up to 64 easily. For example, take 50 3x3 tiles. No combination of 3x3 tiles adds up to 64, but there are literally hundreds of millions of combinations (approx. 50C8) that come close and would have to be tried!
Instead, set up an array of 65 values which represents the number of tile combinations that results in a given total ranging from 0 to 64 inclusive. Initialize the zero element of this array to 1, and the rest to zero. Loop over the number of tiles, and the combination totals as follows:
for (int i=0;i<numtiles;i++) {
for (int j=64;j>=tilesize[i];j) {
numcombos[j]+=numcombos[jtilesize[i]];
}
}
Your return value is simply numcombos[64], the number of tile combinations that add up to an area of 64. Of course if this number is greater than 100,000 return 0 instead.
Reference Implementation: vorthys
Highcard
Used as: Division I  Level 2:
Value

450 points 
Submission Rate

134 / 146 (91.78%)

Success Rate

117 / 134 (87.31%)

Average Score

375.71 points

High Score

radeye for 443.15 points

Remind me to never play cards with Chris. This problem required way less work than most Div I  Level 2 problems. Chris is cheating by looking at his friend's cards and optimally rearranging his own cards. The simplest way for Chris to think about optimizing his own cards is to sort both the hand that he is dealt and the hand that his friend is dealt. Chris then applies his best card to the best card his friend has which is also lower than Chris' best card. Chris then applies his second best card, to the highest card left of his friend's which is also lower than Chris' second best card, and so on. Here's a pseudocode snippet for Chris' strategy, based on my solution:
Sort(chriscards);
Sort(friendcards);
int friend_index = number of friend cards  1
int numWinners=0;
int chris_index = friend_index
while (friend_index>=0) {
if (chris[chris_index]>friend[friend_index]) {
numWinners++;
chris_index;
friend_index;
}
else {
friend_index;
}
}
return nW;
Reference Implementation: Penwiper
Pipes
Used as: Division I  Level 3:
Value

900 points 
Submission Rate

53 / 146 (36.30%)

Success Rate

37 / 53 (69.81%)

Average Score

482.34 points

High Score

radeye for 733.71 points

This problem was reasonably straightforward, so far as Div I  Level 3 problems go. You are given a map describing how pipes are buried in the ground, and need to calculate how much pressure is available in one of the lowest buried pipes. The pressure available in the first pipe on the top level is defined as 100. The pressure in each pipe below the first level is calculated based on the pipes from the previous level. If two pipes are directly on top of one another, then all of the pressure from the top pipe gets transferred to the pipe below it. If there is a horizontal separation between the two pipes however, the amount of pressure transferred to the lower pipe is inversely proportional to the horizontal distance, such that if two pipes p1 and p2 are distances x1 and x2 from the higher pipe, then the amount of pressure transferred to p1 will be (x2/x1) times the amount of pressure transferred to p2. I'm not certain if this is how pressure is really distributed between vertical pipes, but it sounds reasonable.
Given n pipes separated by the distances x1, x2, x3, ..., xn (where none of the xi are equal to zero) from a higher pipe with pressure P, you need to do the following to calculate p(i), the pressure in each of the lower n pipes:
 Find the smallest distance, and call it xmin.
 Calculate a pressure ratio for each pipe: pratio(i) = xmin / x(i)
 Sum all of the ratios.
 Calculate pressure in each pipe as: p(i) = pratio(i) / (Sum of ratios) * P and round down in all cases.
Every solution that I looked at calculated the ratios using floatingpoint arithmetic. Finding a sum of these ratios without using floatingpoint arithmetic would not be possible for some of the cases of large maps with many pipes. Some people added on things like .00000001 to each value of p(i) to avoid floating point errors, but this proved to be unnecessary, at least for all of the system test cases.
Once you have the above algorithm for calculating the pressures of pipes going from one level to the next, the problem becomes quite simple. Set up a loop to start at the first level and go down to the second last level. At each pipe location in a given level, you start with knowledge of what that pipe's pressure is. Use the above algorithm to find out how much pressure that pipe contributes to each of the pipes below it. Once the loop is completed, you then simply have to return the pressure of the pipe on the last level whose zerobased index is given as an input parameter to the problem.
By
Penwiper
TopCoder Member