
Match Editorial 
SRM 171Wednesday, November 12, 2003
Match summary
SRM 171 had a nice variety of problems, which benetin plowed through easily to win the match by an impressive margin of 190 points.
Division 2 was also won by a large margin, 150, by first time coder Mossop. Many coders found the division 1 easy / division 2
medium more difficult that usual, with the average submission time in division 1 at about 20 minutes. It also proved easy game during the
challenge phase, with about 40 challenges total over both divisions, and coders like ambrose and cgu claiming three of those
challenges each.
The Problems
RPG
Used as: Division Two  Level One:
Value

250

Submission Rate

225 / 269 (83.64%)

Success Rate

196 / 225 (87.11%)

High Score

jaivasanth for 242.77 points (4 mins 55 secs)

Average Score

185.47 (for 196 correct submissions)

Aside from parsing, which wasn't too hard, this problem was fairly straightforward. Allocate an array of three elements for
the return value, loop through all the input values, and increment the elements in the array as necessary. The only hitch is
that you can't calculate the average value as you go because that can introduce rounding errors. One of the example cases
made this problem explicit, though, and it is easily solved by waiting until you've gone through all the values, then the average
value is given by (min+max)/2. The input is in the form "ndx", if it is parsed into arrays n and d, then the
following code will find the minimum, maximum, and average die rolls and store it in the array ret:
for (int i=0;i< n.size();i++) {
ret[0]+=n[i];
ret[1]+=n[i]*d[i];
}
ret[2]=(ret[0]+ret[1])/2;
CrossCountry
Used as: Division Two  Level Two:
Value

600

Submission Rate

125 / 269 (46.47%)

Success Rate

38 / 125 (30.40%)

High Score

Humbug75 for 430.26 points (19 mins 32 secs)

Average Score

317.36 (for 38 correct submissions)

Used as: Division One  Level One:
Value

300

Submission Rate

205 / 219 (93.61%)

Success Rate

125 / 205 (60.98%)

High Score

ZorbaTHut for 291.08 points (5 mins 0 secs)

Average Score

214.22 (for 125 correct submissions)

This problem boiled down to sorting by a specific criterion, and this, of course, can be done in many different ways.
If you are familiar with the standard sorting functions of your language, one way to do this is to make an appropriate struct
and comparator, and then the sorting is done for you. Using the standard template library for C++ the struct and
comparator could be declared like this:
struct team {
int score;
int sixth;
char name;
};
bool operator < (const team & lhs, const team & rhs) {
if (lhs.score!=rhs.score) return lhs.score< rhs.score;
if (lhs.sixth!=rhs.sixth) return lhs.sixth< rhs.sixth;
return lhs.name< rhs.name;
}
As long as you score the teams correctly, remove teams that didn't have at least five runners finish, and assign a
large value (like 1000000) to the sixth place runner if a team didn't have more than 5 finish, then this will sort
exactly how the problem specifies. The following code demonstrates this:
vector< team > teamScores;
for (int i=0;i< numTeams;i++) {
int numFinished=0;
team t;
t.score=0;
t.sixth=1000000;
t.name='A'+i;
for (int j=0;j< finishOrder.size();j++) {
if (finishOrder[j]==('A'+i)) {
if (numFinished< 5) {
numFinished++;
t.score+=j;
} else if (numFinished==5) {
t.sixth=j;
numFinished++;
}
}
}
if (numFinished> =5)
teamScores.push_back(t);
}
sort(teamScores.begin(),teamScores.end());
Now that the teams are sorted in the correct order, all that remains is to go through and put the team names into a string for the return value.
string ret;
for (int i=0;i< teamScores.size();i++)
ret+=teamScores[i].name;
return ret;
TextEditor
Used as: Division Two  Level Three:
Value

900

Submission Rate

40 / 269 (14.87%)

Success Rate

11 / 40 (27.50%)

High Score

Mossop for 765.03 points (12 mins 23 secs)

Average Score

522.84 (for 11 correct submissions)

This problem had two main parts. First, take the input text and turn it into an array of strings of the appropriate width.
Second, reorder these strings so that they correspond to two columns of text. If you note that extra whitespace in the input
can be disregarded, the first part becomes as simple as using the appropriate parsing tools of your language. In
C++ this can be done as follows using stringstreams:
string t;
for (int i=0;i< text.size();i++) {
t+=text[i];
t+=' ';
}
stringstream ss(t);
vector< string > v;
string temp;
int back=1;
while (ss >> temp) {
if (v.size()> 0 && v[back].size()+1+temp.size() < =width) v[back]+=" "+temp;
else {
v.push_back(temp);
back++;
}
};
This code first takes the input text and makes one large string out of it. Then it takes one word at a time out of the string
and makes new lines of text, always making the lines as long as possible without exceeding
width characters in length.
Now we have to reorder the text. If you are careful about how many lines there are in each column, this can be done with
minimal coding. The thing to note is that with an even number of lines, there will be an equal number of lines per column,
but with an odd number there will be one more line in the first column.
vector<string> ret(v.size());
int offset=v.size()%2;
for (int i=0;i< v.size();i++)
if (i%2==0) {
ret[i]=v[i/2];
} else {
ret[i]=v[i/2+v.size()/2+offset];
}
ResistorCombinations
Used as: Division One  Level Two:
Value

500

Submission Rate

99 / 219 (45.21%)

Success Rate

51 / 99 (51.52%)

High Score

WishingBone for 456.03 points (8 mins 59 secs)

Average Score

310.83 (for 51 correct submissions)

This problem was most easily approached with a complete search to find all possible values of resistors that can be made,
and then finding the one of those that is closest to the target value. The complete search can be done with a recursive procedure
that takes as input which resistors to be used, breaks those resistors up into two sets, calls itself recursively to find all
possible resistances from those two sets, and then makes all combinations of one resistance from the first set and one from
the second set. The base case is when there is only one resistor in a set, in which case the only resistance that can be made is
that of the one resistor itself. For a Java implementation of this, see writer's solution in the practice room. Here is
some incomplete C++ code that gives the general idea:
set < double > getAllCombos(vector < double > vr) {
if (vr.size()<=1) return set<double>(vr.begin(),vr.end());
vector < double > A,B;
set < double > comboA,comboB;
set < double > ret;
for all combinations of nonempty sets A and B such that the union of A and B is in vr
comboA=getAllCombos(A);
comboB=getAllCombos(B);
for every element EA in comboA
for every element EB in comboB
ret.insert(EA+EB); //series combination
ret.insert((EA*EB)/(EA+EB)); //parallel combination
return ret;
}
Also be sure to find all combinations, not just combinations that use all of the resistors. Once all possible combinations have
been found it is trivial to find the closest value to the target value.
UndergroundVault
Used as: Division One  Level Three:
Value

1000

Submission Rate

36 / 219 (16.44%)

Success Rate

23 / 36 (63.89%)

High Score

benetin for 859.42 points (11 mins 53 secs)

Average Score

624.81 (for 23 correct submissions)

This was definitely one of those problems where, if you could figure out how to solve it, the coding was easy.
The problem statement might have been clear, but it wasn't quite clear how to go about solving it. The problem
statement itself gave a useful clue though, "You can't do this, however, just by sealing any door you see,
because you could close off a section of the vault and be unable to seal doors in that section, or you could seal
yourself in the vault!" This is really all the information we need. Consider the problem as a graph with the
rooms as vertices and the doors between them as edges. Whenever you seal a room you remove certain edges
from that vertex. To determine whether or not a room can be sealed, temporarily remove the appropriate
edges, and then check to see whether all unsealed rooms (including the one you are currently checking) can
be reached from room 0. If so, then you aren't sealing off any part of the vault, and you aren't sealing yourself
in the vault, so that room can be sealed.
Here is my solution to this problem. First parse the input into an adjacency matrix adj[][] such that adj[i][j]=1
if there is a door from room i to room j that must be sealed from room i, and adj[i][j]=Inf
otherwise (where Inf is some arbitrary large number). Make sure to set the diagonal values of adj to 1 as well.
Now make an array unsealed[] which has one element for each room such that unsealed[i]=1 if
room i is unsealed, and 0 otherwise. Now use the FloydWarshall algorithm with a small modification to
find what rooms can be reached if we don't use doors from one specific room.
bool canBeSealed(vector < vector < int > > adj,vector < int > unsealed,int room) {
for (int k=0;k < adj.size();k++)
for (int i=0;i < adj.size();i++)
for (int j=0;j < adj.size();j++) {
if (i==room  k==room) continue;
adj[i][j] < =adj[i][k]+adj[k][j];
}
for (int i=0;i < unsealed.size();i++)
if (unsealed[i] && adj[0][i]==1000000) return false;
return true;
}
The small modification is that we can't use edges that begin in room
room. Now that we have this, all we have to do is check rooms one at a time to see what we can seal.
vector < int > ret;
for (int i=0;i < adj.size();i++) {
int j=0;
while (j < adj.size()) {
if (! unsealed[j]) {
j++;
continue;
}
vector < vector < int > > temp=adj;
for (int k=0;k < adj.size();k++)
temp[j][k]=1000000;
if (canBeSealed(temp,unsealed,j)) {
unsealed[j]=0;
adj=temp;
ret.push_back(j);
break;
}
j++;
}
}
ret.push_back(0);
return ret;
Admittedly, using FloydWarshall to check a room is not the fastest solution. It runs in O(v
^{3}), and we could use a breadth first search which would run in O(v+e).
I chose FloydWarshall because it is easier and faster to code, and less error prone.
By
Running Wild
TopCoder Member