Last post I mentioned that I had not been able to come up with a decent algorithm to problem H from the Waterloo practice. Well, yesterday, while running, I figured it out. There’s an N^2 algorithm that’s pretty straight-forward.
The problem involves a bunch of planets and each planet has a certain political situation, 0 or 1. A planet is considered unstable if given some value R, there are more planets within R parsecs of the given planet with the opposite political stance than the with the same political stance. Your job is to find the minimum R such that the number of unstable planets is maximized.
The obvious bruteforce solution is to consider all distances between planets, and for each planet, compute whether it is unstable or not. However, this obvious solution is N^4 where N can be up to 1000. That’s a big big number.
There’s a slightly better algorithm than this, where you can compute and store all distances. Also, for every planet, store in one list the distance of all planets with the same political situation as you in sorted order and in another list the distance of all planets with the opposite political situation as you in sorted order. Then, when you loop over all possible distances and all planets, you can use binary search on the sorted lists to figure out how many planets are for and against you at the given distance. You can also do early outs when you can’t possibly improve on the best score. If you only store unique distances, then there will be less than N^2 of these, but could be as many as N^2/2. Regardless of the optimizations, this algorithm is still way too slow, and has a big-Oh of O(N^3 log N).
The N^2 algorithm that I came up with involves computing all distances between planets and storing these in sorted order along with the indices of the planets used to make that given distance. Then, you can loop over all distances and use your previously calculated stabilization results to help solve for the current distance. Since the distances are sorted, results computed for smaller distances can be combined to help compute values for the current distance.
In C++, this could look something like this:
int destab = 0;
// m is a multimap where the key is the distance
// from planets with indices stored in the pair values
multimap<double, pair<int, int> >::iterator iter = m.begin();
// loop over all distances
while(iter != m.end()) {
double d = iter->first;
// go over all distances for all planets <= to this one
while(iter != m.end() && iter->first <= d) {
int i1 = iter->second.first;
int i2 = iter->second.second;
Planet * p1 = &planets[i1];
Planet * p2 = &planets[i2];
// if the political situation is the same,
// increase the stabilization factor
if(p1->p == p2->p) {
p1->c++;
// planet became stable so decrease destab
if(p1->c == 0) destab--;
// make sure the second planet is
// different from the first
if(i1 != i2) {
p2->c++;
// planet became stable so decrease destab
if(p2->c == 0) destab--;
}
}
else {
// political situation is different
// so decrease factor
p1->c--;
p2->c--;
// we switched to unstable, increase destab
if(p1->c == -1) destab++;
if(p2->c == -1) destab++;
}
iter++;
}
// keep track of best solution
if(destab > best) {
best = destab;
bestR = d;
}
}
I also think problem D. Data Mining is pretty easy. It looks a bit intimidating because it has a bunch of math formulas. Your job is to find the minimum amount of memory that needs to be allocated based on a particular formula they give you. The formula has an A and B parameter, which is not given and you have to find. Everything else for the formula is given.
The key is to realize that since A and B are used as bit shift operators in the formula there is a limited number of valid A and B values. This is because you can only shift an integer to the left and right so much before you just end up with a bunch of zero bits. Thus, you can try all A and B combinations, plugging them into the memory formula and keeping track of the smallest number you can generate. That number is your answer.
