Match Editorial

The Problems

Value	250
Submission Rate	134 / 158 (84.81%)
Success Rate	95 / 134 (70.9%)
High Score	MisterZimbu for 231.24 points

Implementation

This problem could be approached either as a straight-forward 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.

Value	500
Submission Rate	66 / 158 (41.77%)
Success Rate	31 / 66 (46.97%)
High Score	AyelilTr for 406.88 points

Value	250
Submission Rate	81 / 87 (93.1%)
Success Rate	61 / 81 (75.31%)
High Score	b0b0b0b for 242.72 points

Implementation

This problem can be solved in a very straight-forward 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²). With an upper bound of 1000 imposed on radix, there is no problem using this simple method to solve this problem.

Value	1000
Submission Rate	27 / 158 (17.09%)
Success Rate	9 / 27 (33.33%)
High Score	MisterZimbu for 673.57 points

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 most-significant 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ⁿ - 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 most-significant to least-significant). 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".

Value	550
Submission Rate	29 / 87 (33.33%)
Success Rate	10 / 29 (34.48%)
High Score	kv for 387.15 points

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 Backus-Naur form (BNF). BNF basically specifies rules in the form of

  non-terminal ::= terminals and non-terminals

  There are many ways to approach this, but my favorite tends to be recursive-descent. A recursive-descent parser generally defines a function for each non-terminal in the grammar. The definition of each function follows directly from the rule for the non-terminal that it parses. The occurrence of a non-terminal in a rule corresponds to a (possibly recursive) call to the function that represents that non-terminal.

  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 64-bit 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.

Value	1000
Submission Rate	15 / 87 (17.24%)
Success Rate	6 / 15 (40%)
High Score	Yarin for 680.59 points

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 depth-first search starting at the first vertex, visiting every vertex we can reach without visiting the second vertex. After the depth-first 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 depth-first 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;
}