Match Editorial

The Problems

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

Div-II 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

Div-I 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 "forward-slashes" they have. The fewer the number of forward-slashes, 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 forward-slashes should lexicographically compare the text between each set of forward slashes, starting with the text between the first set of forward-slashes. 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.

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[j-tilesize[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

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 re-arranging 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 pseudo-code 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

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:

1. Find the smallest distance, and call it xmin.
2. Calculate a pressure ratio for each pipe: pratio(i) = xmin / x(i)
3. Sum all of the ratios.
4. 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 floating-point arithmetic. Finding a sum of these ratios without using floating-point 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 zero-based index is given as an input parameter to the problem.