Match Editorial

At the end of the challenge phase, it seemed certain that Yarin would win tonight's SRM by over 100 points. However, a fatal oversight in his 900-point submission knocked him out of the running and gave tomek his second SRM win. tomek, ranked third out of all Division-I coders, earned another bragging right this week: his perfect winning streak now stands at 8 consecutive matches, crushing Yarin's almost one-year-old record of 7.

The race for top score in Division-II was a bit less intense, as most coders who breezed through the easy and medium problems were stumped by the 1000-pointer. It was Dumitru's high score on this problem that gave him the win in his division, followed by vavadera. imolarolla, a newcomer, came in third place tonight, bagging an initial rating of 1670.

The Problems

Value	250
Submission Rate	157 / 198 (79.29%)
Success Rate	104 / 157 (66.24%)
High Score	derelikt for 245.89 points (3 mins 41 secs)
Average Score	205.71 (for 104 correct submissions)

Your goal here is to calculate the smallest number of hard drives your scattered files can take up, given the capacity and current use of each drive.

The first step is to determine how much data there is total between your various hard drives, by adding together the amounts on each drive. You can do this because the files can be moved freely, and the drive they came from doesn't matter. This total can be considered your unallocated data. At this point, the greedy algorithm is actually a very good strategy, as the best way to minimize the number of drives used is to first fill up the largest, then the next largest, and so forth until all data is allocated. Thus, sort total, and go through from greatest to least, subtracting from your data total until it reaches or passes zero.

public class DiskSpace {
   public int minDrives(int[] used, int[] total) {
      int data = 0;
      for (int i = 0; i < used.length; i++)
         data += used[i];
      Arrays.sort(total);
      int answer = 0;
      for (int i = total.length - 1; data > 0; i--) {
         data -= total[i];
         answer++;
      }
      return answer;
   }
}

Value	600
Submission Rate	126 / 198 (63.64%)
Success Rate	99 / 126 (78.57%)
High Score	derelikt for 559.45 points (7 mins 45 secs)
Average Score	369.95 (for 99 correct submissions)

Value	300
Submission Rate	138 / 141 (97.87%)
Success Rate	127 / 138 (92.03%)
High Score	SnapDragon for 294.46 points (3 mins 54 secs)
Average Score	245.35 (for 127 correct submissions)

Here you must solve a formula to give the likelihood that you will win on a given board. To do this, you must ascertain two numbers for that board: the number of bombs, and the number of spaces which neither contain nor neighbor any bombs.

Counting the bombs is easy, but the latter sum is a bit more difficult to reach. For each space on the board, you must check each of its eight neighbors for bombs. However, you don't want to check a neighbor that doesn't actually exist, such as a square off the edge of the board. So before checking a neighbor to see if it contains a bomb, you must first check to see that it within the bounds of the board. It is undoubtedly easier and less error-prone to put this check into its own function:

bool isBomb(vector <string> board, int row, int col) {
   if (row < 0 || row >= board.size() || col < 0 || col >= board[0].length())
      return false;
   else
      return board[row][col] == 'B';
}

Once you have both numbers, executing the formula is simple arithmetic - but make sure to multiply by 100, to yield a percentage.

Value	1000
Submission Rate	24 / 198 (12.12%)
Success Rate	9 / 24 (37.50%)
High Score	Dumitru for 592.29 points (28 mins 1 secs)
Average Score	495.24 (for 9 correct submissions)

Your task in this problem is to determine if a given compound word is composed entirely of prefixes and/or suffixes of a given base word. If it is composed in this fashion, you must return the smallest number of such affixes into which the compound word can be divided.

Solving this problem requires knowledge of either dynamic programming or memoization, programming tricks which are rarely seen in Division-II. I personally have always been a fan of the latter technique; memoized recursion seems both easier to comprehend and easier to code than DP.

To make things easier, it is wise to start your solution by creating a dictionary of valid word parts. Simply create a new array and add to it every prefix and suffix of original, including the whole word itself.

   vector<string> dict;
   for (int i = 1, i < original.length() - 1; i++)
      dict.push_back(original.substr(0, i));  
      // Add every prefix
   for (int i = 1; i < original.length() - 1; i++)
      dict.push_back(original.substr(i));     
      // Add every suffix
   dict.push_back(original);                       
   // Add the entire word

With our dictionary in hand, we can now launch our recursive function. This function need take only one parameter: the current position in compound. It operates by checking each word in the dictionary against the current position in compound. If there is a match, it recurses on the remainder of the string and updates the best result found so far. For the outline of the function, including the memoization step, refer to the pseudocode below.

int minParts(int position) {
   if we have already executed this function for the current position,
      immediately return the previously found result
   if position = compound.length,
      return 0 (the empty case)
   let answer = INFINITY;
      for each word w in dictionary
   if w is a prefix of compound.substring(position),
      let temp = minParts(position + w.length)
   if (temp < answer)
      set answer = temp
   return answer
}

The memoization step is necessary for cases such as the one where both original and compound consist of 50 A's in a row. The dictionary will contain 99 elements (some duplicates of each other), and nearly all of these entries will cause the recursive function to call itself again at every position in the string, yielding an exponential number of calls and necessitating far more than the allowed 8 seconds. Memoization ensures that the function will never have to do work more than 50 times.

One last thing to note is that the greedy algorithm fails on this problem. Your recursive function needs to check every word in the dictionary as a possibility at each position; you cannot simply look for the longest prefix/suffix present in the compound word and break the word up accordingly. To understand why, consider the example given in the problem statement where original = "BAAABA" and compound = "BAAABAAA". The correct answer is 2 ("BAAA", "BAAA"), but the greedy algorithm will incorrectly return 3 ("BAAABA", "A", "A"), as it tries to use the largest dictionary word possible at the beginning.

Value	550
Submission Rate	67 / 141 (47.52%)
Success Rate	58 / 67 (86.57%)
High Score	Yarin for 512.45 points (7 mins 48 secs)
Average Score	325.63 (for 58 correct submissions)

The goal of this problem is to determine the optimal strategy for your company's elevator. Given the arrival floors, arrival times, and destination floors of the elevator's users, you must return the shortest possible time in which the elevator can complete its task.

The constraints are what make this problem possible. There are at most five employees to consider, which should be a small enough number for even the slowest of brute-force algorithms to handle in 8 seconds.

To understand how to account for each case, let us consider an example where the maximum five employees all need to use the elevator. Your code should cycle through every permutation of "0011223344", where the first instance of a number signals picking up the corresponding employee, and the second instance signals dropping that employee off. Check the time required for each permutation, and the smallest value you find will be the answer.

C++ users have an advantage here with the ever-useful next_permutation() function. If your language doesn't have next_permutation() built-in, you should strongly consider writing one yourself and additing it to your code library for future use.

Alternately, this problem can be solved by recursion. Refer to the following pseudocode:

int timeWaiting(int[] passengerState, int currentFloor, int currentTime) {
   if every passenger has been dropped off,
      return currentTime
   let answer = INFINITY
   for each passenger p
      if p has already been dropped off,
         go on to the next passenger
      otherwise, if p has not yet been picked up,
         let newFloor = p's starting floor
         let distance = abs(currentFloor - newFloor)
         let newTime = max(p's arrival time, currentTime + distance)
         let newPassengerState = passengerState with p now on elevator
         let completionTime = timeWaiting(newPassengerState, newFloor, newTime)
      otherwise, if p is currently in the elevator,
         let newFloor = p's destination floor
         let distance = abs(currentFloor - newFloor)
         let newTime = currentTime + distance;
         let newPassengerState = passengerState with p dropped off
         let completionTime = timeWaiting(newPassengerState, newFloor, newTime)
      if completionTime < answer
      set answer = completionTime
   return answer
}

Value	900
Submission Rate	34 / 141 (24.11%)
Success Rate	17 / 34 (50.00%)
High Score	ZorbaTHut for 736.40 points (14 mins 3 secs)
Average Score	546.83 (for 17 correct submissions)

This problem gives you a board consisting of empty spaces, walls, and the starting positions of two players (A and B). It then asks you to determine the least possible number of turns in which players A and B can switch positions. On any turn, either or both players may move a single space vertically, horizontally, or diagonally, but they cannot switch positions in any single turn. It is also important to note that a player may remain in the same location - it does not have to move on every turn. (This oversight ruined many otherwise-perfect submissions, including Yarin's.)

Yet again, the input restrictions on this problem allow a solution which would otherwise time out. The largest possible board is 20 by 20, meaning there are only 400 places where a single player can be, and only 160000 possible configurations for the locations of both players. So as long as the algorithm used stays within those general bounds (i.e., doesn't consider board configurations more than once), it should run well within 8 seconds.

The best and fastest way to solve this problem is to use a breadth-first search. The state of the board can be described as a 4-tuple: (playerA_row, playerA_col, playerB_row, playerB_col). The starting and ending states are easy enough to figure out, simply by scanning the input array for the location of the 'A' and 'B' characters. All that's left is to enumerate all the different ways to get from one state to another, which can be accomplished as follows:

int playerA_row, playerA_col, playerB_row, playerB_col;
    for (playerA_rowChange=-1; playerA_rowChange <= 1; ++playerA_rowChange)
      for (playerA_colChange=-1; playerA_colChange <= 1; ++playerA_colChange)
        for (playerB_rowChange=-1; playerB_rowChange <= 1; ++playerB_rowChange)
          for (playerB_colChange=-1; playerB_colChange <= 1; ++playerB_colChange) {
            playerA_newRow=playerA_row + playerA_rowChange;
            playerA_newCol=playerA_col + playerA_colChange;
            playerB_newRow=playerB_row + playerB_rowChange;
            playerB_newCol=playerB_col + playerB_colChange;
            // Validate, check, and enqueue the new state.
}

Once we have a new state, we need to validate it. Validation consists of several steps:

1. Have we seen this state before? If we've already dealt with this combination of player positions, we should skip it and go on to the next for-loop permutation (using the continue command). The easiest way to check if we've seen this state before is to create a new boolean visited[20][20][20][20], initialize each entry to false, and mark an entry as true after we've gotten past this step of the validation.
2. Are both players in valid locations? Neither player should be inside of a wall, or off the board, or in the same location.
3. Did this move cause the players to swap places? If (playerA_newRow == playerB_row && playerA_newCol == playerB_col && playerB_newRow == playerA_row && playerB_newCol == playerA_col), then the players have crossed paths, and this move was invalid.
4. Did we win? If the players have switched places, we can immediately return the number of turns we've taken so far.

After the state has been validated, we can push it (and the number of turns it took to get to it) to the back of our queue, and pop the next element. If the queue becomes empty, then it's impossible for the players to switch positions with each other, and we return -1.