
Match Editorial 
SRM 126Monday, December 23, 2002
The Problems
Battle
Used as: DivisionII, Level 1:
Value 
250 
Submission Rate 
134
/
158
(84.81%)

Success Rate 
95
/
134
(70.9%)

High Score 
MisterZimbu for
231.24 points

Reference implementation:
see below
Implementation
This problem could be approached either as a straightforward simulation or analytically.
I will describe the analytical approach. Simply by looking at each warrior's stats, we can
compute how much time it will take for one to defeat the other. First, we compute how much
damage each warrior can inflict upon the other each round (which will remain constant throughout
the fight). This is the maximum of either the warrior's offense minus the opponent's defense or zero.
If the damage inflicted is zero, then that warrior will never be able to defeat the opponent.
Since we're given an upper bound on time of 1000, simply choose some greater value (e.g.
1001) to represent infinity.
If the damage inflicted is not zero, then the number of rounds it will take to defeat the opponent
will be: (health + damage  1) / damage (using integral division).
Once we know the number of rounds it will take for each warrior to defeat its opponent, we can compare
to determine what the output should be. If the number of rounds is the same for each warrior, then
we will output "NONE". The number we output with it will depend upon whether the number of
rounds is equal to our value representing infinity or not. If so, we output "NONE 1000", otherwise
we output "NONE " with the number of rounds appended to it.
If the number of rounds is not the same for each warrior, then we output the name of the warrior with the
greater number of rounds followed by the number of rounds for its opponent.
RandomNumberGenerator
Used as: DivisionII, Level 2:
Value 
500 
Submission Rate 
66
/
158
(41.77%)

Success Rate 
31
/
66
(46.97%)

High Score 
AyelilTr for
406.88 points

Used as: DivisionI, Level 1:
Value 
250 
Submission Rate 
81
/
87
(93.1%)

Success Rate 
61
/
81
(75.31%)

High Score 
b0b0b0b for
242.72 points

Reference implementation:
see below
Implementation
This problem can be solved in a very straightforward manner. Iterate through every possible seed
(there will be radix  1 of these). For each seed, generate random numbers until you repeat
one. If the number of unique random numbers generated is equal to radix  1, increment a counter.
After doing this for every seed, return this counter.
For each seed there can be at most radix  1 unique random numbers generated. Therefore the
upper bound on runtime for this method is O(radix^{2}). With an upper bound of 1000
imposed on radix, there is no problem using this simple method to solve this problem.
Antidote
Used as: DivisionII, Level 3:
Value 
1000 
Submission Rate 
27
/
158
(17.09%)

Success Rate 
9
/
27
(33.33%)

High Score 
MisterZimbu for
673.57 points

Reference implementation:
see below
Implementation
To solve this problem, we will iterate through every combination of choices we can make for all of
the drinks. As usual, we will represent a combination as an integer, where its bits specify the
value for each element in the set. In this case, a 1 bit indicates a DRINK action,
while a 0 bit indicates a PASS action.
If we order the bits so that the mostsignificant bit represents the action to take for the first drink
in the list, then the natural ordering of integers yields the ordering we desire for combinations.
Thus all we have to do is iterate through the values from 2^{n}  1 down to 0,
inclusive, and return the first combination we find that yields no sickness.
To determine whether a combination yields sickness is easy. Before we begin, we process the rules
parameter. This consists of some simple string parsing. Each rule gives us either one drink or an ordered
pair of drinks. If the former, we add this drink to a set of bad drinks. If the latter, we add this
ordered pair to a set of bad sequences of drinks.
For each combination, we iterate through the bits (from mostsignificant to leastsignificant). Whenever
we encounter a bit of value 1, we check to see if it causes sickness. If the drink it represents
is in the list of bad drinks, it causes sickness. If the previous bit was also 1, and the ordered
pair formed by the drink represented by the previous bit and the drink represented by the current bit
is in the set of bad sequences of drinks, it causes sickness. Otherwise we continue. If we iterate through
all of the bits in this fashion without causing sickness, then we have found the combination our answer is
based on.
Once we find this combination, we simply iterate through the combination's bits again in the same order as before.
For bits of value 1 we add "DRINK" to the output list, otherwise we add "PASS".
UnitConverter
Used as: DivisionI, Level 2:
Value 
550 
Submission Rate 
29
/
87
(33.33%)

Success Rate 
10
/
29
(34.48%)

High Score 
kv for
387.15 points

Reference implementation:
see below
Implementation
This problem can be broken down into three separate, relatively easy problems:
 Parsing (conversion specifiers and amounts)
 Rational arithmetic
 Transitive closure
I'll address these one at a time.

The parsing problem is rather easy as far as parsing problems go. You are given a grammar
in BackusNaur form (BNF). BNF basically specifies rules in the form of
nonterminal ::=
terminals and nonterminals
There are many ways to approach this, but my favorite tends
to be recursivedescent. A recursivedescent parser generally defines a function
for each nonterminal in the grammar. The definition of each function follows directly
from the rule for the nonterminal that it parses. The occurrence of a nonterminal
in a rule corresponds to a (possibly recursive) call to the function that represents
that nonterminal.
Fortunately the grammar for this problem is very simple. See my solution for how I parsed it.

Rational arithmetic is a problem that comes up again and again on TopCoder. For this reason you
should probably already have it coded, archived, and ready for quick reuse. For this problem you
only need to be able to support the multiplication and division operations on rationals. Divison
is just multiplication by a reciprocal of a rational, and multiplication is quite simple:
product of the numerators divided by the product of the denominators. Thanks to the problem specification
we don't have to deal with special values like 0 or negative values. Since we may get very
large values for either the numerator or denominator, each should be represented by a 64bit integer data
type.
You will also need to be able to convert any rational value into simplified form. This simply consists
of computing the greatest common divisor of the numerator and denominator, and then dividing each by
that value. It is generally good practice to simplify any intermediate value, to help avoid overflow.

The conversion rules that you are given specify the edges of a directed graph. In this graph,
vertices represent units and edges between vertices represent conversions from one unit to another.
Each edge has a weight associated with it. This weight gives the conversion factor; if there exists
an edge between units X and Y, then to convert a value expressed in X to Y
you would multiply that value by the weight of the edge from X to Y. Furthermore, if
there is a path from X to Y (consisting of one or more edges), then the conversion
factor from X to Y is simply the product of the weights of all the edges in this path.
Each rule corresponds to two edges, each between the same pair of vertices. One edge is from the unit
on the left side of the = to that on the right side, and its weight is the value on the
left side divided by the value on the right side. The second edge is in the opposite direction, and its
weight is the reciprocal of the first edge's weight.
The transitive closure of this graph can then give us direct access to the conversion factors between
any pair of units for which a conversion is defined. The transitive closure basically represents
the set of all acyclic paths in a directed graph. When generating the transitive closure it is easy
to compute the product of the weights of the edges for each path. See my solution for the implementation.
Once these three problems are solved, the solution is trivial. We parse the input to build our graph, then
compute the transitive closure of that graph to build a map representing all the defined conversion factors.
We then parse the input value, find the conversion factor to convert it from its unit to the input unit, multiply
the input value by that factor, and output the result.
WeatherCommunications
Used as: DivisionI, Level 3:
Value 
1000 
Submission Rate 
15
/
87
(17.24%)

Success Rate 
6
/
15
(40%)

High Score 
Yarin for
680.59 points

Reference implementation:
see below
Implementation
There is no clever trick that is needed to solve this problem. The input is small enough that it is possible
to iterate through every combination of edges, determine if each combination yields security, and measure the
cost of each combination. This one sentence basically summarizes the entire solution.
If there are n points, then there are n * (n  1) / 2 unique edges (remember that edges
are not directed). Let t = n * (n  1) / 2. Then there are 2^{t} edge combinations.
We can iterate through these combinations in the same manner as usual (see Antidote).
We can skip the empty combination (no edges), as it will always be invalid.
For each combination, we must determine if it is secure. It is secure if, for each vertex that we remove, there
exists at least one path between any pair of remaining vertices. So, we iterate through all unique pairs of
vertices. For each such pair, we perform a depthfirst search starting at the first vertex, visiting every
vertex we can reach without visiting the second vertex. After the depthfirst search, if we have visited
every vertex but one, we know that this combination is secure.
If we determine that a combination is secure, we simply iterate through the edges that are in that combination
to measure the cost of that combination. For each edge, we check to see if it is in the defined set of edges
that already exist. If not, we add the distance between the two vertices that the edge connects to the running
sum of the total cost.
As we iterate through all the edge combinations as described above, we keep track of the minimum cost over all
secure combinations. We can initialize this minimum to be the sum of the cost of all edges, as that represents
a combination that will always be valid.
Reference Implementations
Battle
#include <string>
#include <sstream>
using namespace std;
class Battle
{
public:
string firstDefeated(string warrior1, string warrior2);
};
void parse_warrior(string warrior, string &name, int &health, int &def, int &off)
{
stringstream ss(warrior);
ss >> name >> health >> def >> off;
}
string Battle::firstDefeated(string warrior1, string warrior2)
{
string n1, n2;
int h1, h2;
int d1, d2;
int o1, o2;
int dmg1, dmg2;
int t1, t2;
parse_warrior(warrior1, n1, h1, d1, o1);
parse_warrior(warrior2, n2, h2, d2, o2);
dmg1 = (o1  d2) >? 0;
dmg2 = (o2  d1) >? 0;
t1 = dmg1 ? (h2 + dmg1  1) / dmg1 : 1001;
t2 = dmg2 ? (h1 + dmg2  1) / dmg2 : 1001;
t1 <?= 1001;
t2 <?= 1001;
stringstream out;
if(t1 == t2) {
t1 <?= 1000;
out << "NONE " << t1;
} else if(t1 < t2) {
out << n2 << ' ' << t1;
} else {
out << n1 << ' ' << t2;
}
return out.str();
}
RandomNumberGenerator
#include <set>
using namespace std;
class RandomNumberGenerator
{
public:
int howManyGoodSeeds(int Base, int radix);
};
int modpow(int base, int pow, int mod)
{
return pow ? (base * modpow(base, pow  1, mod)) % mod : 1;
}
int RandomNumberGenerator::howManyGoodSeeds(int base, int radix)
{
int result = 0;
for(int i = 1; i < radix; i++) {
int gen = modpow(base, i, radix);
int prev = gen;
set<int> history;
while(history.find(prev) == history.end()) {
history.insert(prev);
prev = (gen * prev) % radix;
}
if((int) history.size() == radix  1) {
result++;
}
}
return result;
}
Antidote
#include <string>
#include <vector>
#include <sstream>
#include <set>
#include <map>
using namespace std;
class Antidote
{
public:
vector<string> safeDrinks(vector<string> a, vector<string> b);
};
vector<string> Antidote::safeDrinks(vector<string> rules, vector<string> drinks)
{
set<pair<string, string> > bad_seqs;
set<string> bad_drinks;
for(vector<string>::const_iterator i = rules.begin(); i != rules.end(); i++) {
string s = i>substr(4);
unsigned x = s.find('+');
if(x == s.npos) {
bad_drinks.insert(s);
} else {
string a = s.substr(0, x);
string b = s.substr(x + 1);
bad_seqs.insert(pair<string, string>(a, b));
}
}
vector<string> result;
unsigned c = 1 << drinks.size();
while(c > 0) {
string prev;
unsigned i;
for(i = 0; i < drinks.size(); i++) {
if(c & (1 << (drinks.size()  i  1))) {
if(prev.size() > 0 && bad_seqs.find(pair<string, string>(prev, drinks[i]))
!= bad_seqs.end()) {
break;
}
if(bad_drinks.find(drinks[i]) != bad_drinks.end()) {
break;
}
prev = drinks[i];
} else {
prev = "";
}
}
if(i == drinks.size()) {
break;
}
}
for(unsigned i = 0; i < drinks.size(); i++) {
result.push_back((c & (1 << (drinks.size()  i  1))) ? "DRINK" : "PASS");
}
return result;
}
UnitConverter
#include <string>
#include <vector>
#include <sstream>
#include <set>
#include <map>
using namespace std;
class UnitConverter
{
public:
string convertQuantity(vector<string> a, string b, string c);
};
long long gcd(long long m, long long n)
{
return n ? gcd(n, m % n) : m;
}
// Represents a rational number
struct R : public pair<long long, long long>
{
R(long long n = 0, long long d = 1) : pair<long long, long long>(n, n ? d : 1)
{
simplify();
}
R(const R &r) : pair<long long, long long>(r.first, r.second)
{
simplify();
}
bool operator!(void) const
{
return !first;
}
void operator*=(const R &r)
{
first *= r.first;
second *= r.second;
simplify();
}
R operator~(void) const
{
return R(second, first);
}
R operator*(const R &r) const
{
return R(first * r.first, second * r.second);
}
R operator/(const R &r) const
{
return *this * ~r;
}
void simplify(void)
{
long long g = gcd(first, second);
first /= g;
second /= g;
}
};
ostream &operator<<(ostream &o, const R &r)
{
if(r.second == 1) {
o << r.first;
} else if(r.first > r.second) {
o << r.first / r.second;
if(r.first % r.second) {
o << ' ' << r.first % r.second << '/' << r.second;
}
} else {
o << r.first << '/' << r.second;
}
return o;
}
// Represents an amount (rational + unit)
struct A : public pair<R, string>
{
A(const R &r, const string &s) : pair<R, string>(r, s) { }
A(const A &a) : pair<R, string>(a.first, a.second) { }
};
ostream &operator<<(ostream &o, const A &a)
{
o << a.first << ' ' << a.second;
return o;
}
// Represents a conversion (A <> A)
struct C : public pair<A, A>
{
C(const A &a, const A &b) : pair<A, A>(a, b) { }
C(const C &c) : pair<A, A>(c.first, c.second) { }
};
ostream &operator<<(ostream &o, const C &c)
{
o << c.first << '=' << c.second;
return o;
}
R parse_rational(const string &s)
{
unsigned x = s.find('/');
unsigned y = s.find(' ');
if(x == s.npos) {
stringstream ss(s);
long long a;
ss >> a;
return R(a);
}
if(y != s.npos) {
stringstream ss(s.substr(0, x));
long long a, b, c;
ss >> a >> b;
stringstream ss2(s.substr(x + 1));
ss2 >> c;
return R(a * c + b, c);
} else {
stringstream ss(s.substr(0, x));
long long a, b;
ss >> a;
stringstream ss2(s.substr(x + 1));
ss2 >> b;
return R(a, b);
}
}
A parse_amount(const string &s)
{
unsigned x = s.find_last_of(' ');
return A(parse_rational(s.substr(0, x)), s.substr(x + 1));
}
C parse_conversion(const string &s)
{
unsigned x = s.find('=');
return C(parse_amount(s.substr(0, x)), parse_amount(s.substr(x + 1)));
}
string UnitConverter::convertQuantity(vector<string> conversions, string quantity, string unit)
{
set<string> units;
map<string, map<string, R> > graph;
// Populate conversion graph
for(vector<string>::const_iterator i = conversions.begin(); i
!= conversions.end(); i++) {
C c = parse_conversion(*i);
graph[c.first.second][c.second.second] = c.second.first / c.first.first;
graph[c.second.second][c.first.second] = c.first.first / c.second.first;
units.insert(c.first.second);
units.insert(c.second.second);
}
// Transitive closure
for(set<string>::const_iterator k = units.begin(); k != units.end(); k++) {
for(set<string>::const_iterator i = units.begin(); i != units.end(); i++) {
for(set<string>::const_iterator j = units.begin(); j != units.end(); j++) {
if(!graph[*i][*j]) {
graph[*i][*j] = graph[*i][*k] * graph[*k][*j];
}
}
}
}
// graph[x][y] now gives the conversion factor from x to y
A a = parse_amount(quantity);
R scalar = graph[a.second][unit];
A b(a.first * scalar, unit);
stringstream result;
result << b;
return result.str();
}
WeatherCommunications
#include <math.h>
#include <string>
#include <vector>
#include <sstream>
#include <set>
#include <map>
using namespace std;
class WeatherCommunications
{
public:
int lowestCostToSecure(vector <int> a, vector <int> b, vector <string> c);
};
typedef pair<int, int> Pt;
struct Edge : public pair<int, int>
{
Edge(int a, int b) : pair<int, int>(a <? b, a >? b) { }
Edge(const Edge &e) : pair<int, int>(e.first, e.second) { }
};
vector<Pt> pts; // the list of input points
vector<Edge> edges; // the list of all possible edges
set<Edge> existing; // the set of edges that already exist
map<int, map<int, double> > costs; // a mapping of location > location > distance
unsigned
n, ne; // number of points, number of possible edges
// Measures the cost of a particular combination of edges
double measure(unsigned combo)
{
double cost = 0;
for(unsigned i = 0; i < ne; i++) {
if(combo & (1 << i)) {
if(existing.find(edges[i]) == existing.end()) {
cost += costs[edges[i].first][edges[i].second];
}
}
}
return cost;
}
// Perform a depthfirst search, starting from x, avoiding y,
// using edges in eset, storing visited vertices in vis
void dfs(unsigned x, unsigned y, set<Edge> &eset, set<int> &vis)
{
vis.insert(x);
for(unsigned i = 0; i < n; i++) {
if(i != y && vis.find(i) == vis.end() && eset.find(Edge(x, i)) != eset.end()) {
dfs(i, y, eset, vis);
}
}
}
// Determine if a particular combination is secure
bool valid(unsigned combo)
{
set<Edge> eset;
// Build the set of edges defined by this combination
for(unsigned i = 0; i < ne; i++) {
if(combo & (1 << i)) {
eset.insert(edges[i]);
}
}
for(unsigned i = 0; i < n; i++) { // i is starting vertex
for(unsigned j = 0; j < n; j++) { // j is removed vertex
if(j != i) {
set<int> vis;
dfs(i, j, eset, vis);
if(vis.size() != n  1) {
return false;
}
}
}
}
return true;
}
double dist(const Pt &a, const Pt &b)
{
double dx = a.first  b.first;
double dy = a.second  b.second;
return sqrt(dx * dx + dy * dy);
}
int WeatherCommunications::lowestCostToSecure(vector<int> xs, vector<int> ys, vector<string> already)
{
n = xs.size();
ne = n * (n  1) / 2;
for(unsigned i = 0; i < n; i++) {
Pt pt(xs[i], ys[i]);
pts.push_back(pt);
}
double best = 0;
for(unsigned i = 0; i < n; i++) {
for(unsigned j = i + 1; j < n; j++) {
edges.push_back(Edge(i, j));
costs[i][j] = dist(pts[i], pts[j]);
best += costs[i][j];
}
}
for(vector<string>::const_iterator i = already.begin(); i != already.end(); i++) {
stringstream ss(*i);
int a, b;
ss >> a >> b;
existing.insert(Edge(a, b));
}
for(int i = 1; i < (1 << ne); i++) {
if(valid(i)) {
best <?= measure(i);
}
}
return (int) best;
}