
Match Editorial 
SRM 156Wednesday, July 23, 2003
Match summary
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 900point submission knocked him out of the running and gave tomek his second SRM win. tomek,
ranked third out of all DivisionI coders, earned another bragging right this week: his perfect winning streak now stands at 8
consecutive matches, crushing Yarin's almost oneyearold record of 7.
The race for top score in DivisionII was a bit less intense, as most coders who breezed through the easy and medium problems were
stumped by the 1000pointer. 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
DiskSpace
Used as: Division Two  Level One:
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;
}
}
BombSweeper
Used as: Division Two  Level Two:
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)

Used as: Division One  Level One:
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 errorprone 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.
WordParts
Used as: Division Two  Level Three:
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 DivisionII. 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.
SmartElevator
Used as: Division One  Level Two:
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 bruteforce 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 everuseful next_permutation() function. If your language doesn't have
next_permutation() builtin, 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
}
PathFinding
Used as: Division One  Level Three:
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
otherwiseperfect 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 breadthfirst search. The state of the board can be described as a 4tuple:
(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:
 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 forloop 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.
 Are both players in valid locations? Neither player should be inside of a wall, or off the board, or in the same location.
 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.
 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.
By
LunaticFringe
TopCoder Member