|
Match Editorial |
Wednesday, 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:
Used as: Division One - Level One:
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)
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 non-empty 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 Floyd-Warshall 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 Floyd-Warshall to check a room is not the fastest solution. It runs in O(v3), and we could use a breadth first search which would run in O(v+e).
I chose Floyd-Warshall because it is easier and faster to code, and less error prone.
