KingdomXCitiesandVillages
Link to problem statement
It becomes a habit, in expected value problems, it is sometimes possible to separate the calculations and then add them up, because of the expected value's linearity property. This was not an exception. Let us call the length of each road a cost. When building a road, the cost of building it is the length of the road. The order of villages is random, but eventually each of the villages will be picked exactly once. And for each of the villages, exactly one road will be built. Expected_Length( all roads) can be rephrased to Expected_Length( road1 + road2 + ...) and since each road is added for each village, then it can become : Expected( cost_to_connect(village1) + cost_to_connect(village2) + ...). Because of the aforementioned linearity property, we have that the result can be seen as:
Expected(Cost to connect village1) + Expected(Cost to connect village2) + ... Expected(Cost to connect villageN)
Then if it is possible to find the expected cost for each village, we can just add them up to find the wanted result.
Expected cost to connect each village
Since we can treat each village independently, assume we are working with a village i. The road that will be built will have the minimum length among all the roads that can connect the village to cities or to villages that are already connected. Then the cost depends greatly on which villages have been picked before village i. The definition of the expected value tells us that it is equal to: Sum( x * prob_x ) for each x. This means that for each possible road cost X, we need to find the probability that road cost is picked and multiply them. The sum of all those products is the expected cost.
For a given cost X, what is the probability we will pick that value? X would have to be the minimum road length possible between village i and any city or village that is already connected. The minimum distance between village i and the cities will never change, let us call this constant dcity. It is always possible to build a road between the village and a city such that the cost is dcity, regarding X vs. dcity, there are three possibilities:
- X > dcity: Since it is always possible to build a road from the village to a city, then the minimum cost will never be greater than dcity. The probability to have minimum = X is 0.
- dcity = X : If we want the minimum cost to be dcity, then no village with a distance to i smaller than dcity should be picked before village i. If such a city was picked, the minimum distance would be smaller than X = dcity
- X < dcity : For the minimum would have to be equal to X, then no village with a distance to village i smaller than X should be picked. However, it is also necessary to pick at least one village such that the distance between it and village i is X, so that the minimum can be X.
We just need to calculate two probabilities:
- Probability no village with a distance to village i smaller than dcity is picked before village j is picked.
- Probability only villages with a distance to village j that are greater than or equal to X are picked before i and at least one the villages with a distance equal to X is picked before i.
It is possible to calculate those probabilities in many ways. I will use a dynamic programming-like approach. Let us begin with the first case, there are n villages. Among them, we have village i, a set of good villages that can be picked before j and the remaining villages are bad = (n - good) villages that may not be picked before picking village i. We will find a recurrence that simulates the process. This process can be represented by variables good and bad, because we can tell that n = good + bad + 1 (the 1 is village i). At any moment, there is a (1/n) probability to pick each of the villages. So, there is a (1/n) probability to pick village i. If village i is picked, then the event is one of those we want to include in the probability. For each of the good village, there is a probability of (1/n) that it will be picked, so there is a probability of (good/n) that a good village is picked. If a good village is picked, then there will be (good-1) remaining good villages, and village i and the bad villages will stay, so the simulation can continue and in fact, becomes a sub-instance of the problem we are solving, with a different value of good. If a bad village is picked, the event is not one to consider in the probability we want, so we should not include it. In total, the recurrence works as follows:
f(good, bad) {
n = good + bad + 1
result = (1/n) + (good/n) * f(good-1, bad)
}
The other case contains some villages such that at least one of them must be picked before the ball. Let us call the number of those villages need. Those villages
are also valid to be picked before i, so they will be a subset of the good villages. Therefore n is still = good+bad+1. In this case, if village i was picked (with 1/n probability) before the needed villages, it is not a valid event. If one of the needed villages is picked (with probability need/n), then we no longer need to pick any more of them, so good=good-1 and need becomes 0, and then the case becomes one with a group of good and bad villages that is the same as the basic recurrence we solved above. If one of the good villages that is not one of the needed ones is picked (probability (good-need)/n), then good = good-1 , need stays the same and the situation becomes a sub-case with different values of good,need,bad. As usual, picking a bad village would make the event not a valid one to consider in the calculation of this probability. The recurrence becomes something like:
g(good, need, bad) {
n = good + bad + 1
return (need/n) * f(good-1, bad) + ((good-need)/n) * g(good-1,need,bad)
}
Both recurrences can be joined in a single one. Just make it so when need=0, the case we are dealing with is one in which it is not needed to get any specific village of the good ones.
The recurrences are acyclic. Which means we can just use memoization (Cache the result for each group of arguments, so that the result for each group of arguments is evaluated exactly once). good , need and bad can be at most equal to the number of villages vn , so the total complexity of getting all the calls to the recurrences is O(vn * vn * vn). With vn <=50, that is very fast.
In reality, many people could find it easier or cleaner to just spend some time analyzing the problem (good, need,bad) and calculate the probabilities without a recursion but by other means. In my specific case it is easier to think of recursions, for some reason.
Thanks to the recurrences, we can get the probabilities for each X by first counting the amount of villages that are good, bad and needed for the specific value of X. We can of course not just iterate through all possible values of X from 0 to infinite, so instead we will only focus on those that are possible distances. dcity is a possible value of X. Then we can tell that for every distance between a village j and village i, we can consider it a possible distance. Then there are at most O(vn*vn) such distances. Special care should be put so that we don't evaluate each distance more than once.
In order to get the probabilities, you need to count the number of distances that are greater than or equal to a value, the distances are doubles and that may add some risk to greater than or equal checks. A way to avoid this issue is to notice that Euclidean distances are :
squareRoot((x1-x2)2 + (y1-y2)2)
The values of x and y are always integer in this problem. When comparing:
squareRoot(A) < squareRoot(b).
It is equivalent to (A<B) . Assuming they are both non-negative integers. This means that you can just use (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) in comparisons instead of its square root. This way you will always use integers in comparisons. This was not really necessary in this problem. But it is just a habit I made to avoid doubles when possible.
Another thing is, that the coordinates in the input can be as large as 1000000, and that makes the Euclidean distance overflow 32 bits integers. Simply use 64 bits integers to avoid overflow. The final implementation follows:
using namespace std;
#define for_each(q, v) for(typeof(v.begin()) q = v.begin(); q!=v.end(); q++)
struct KingdomXCitiesandVillages
{
bool seen[51][51][51];
double mem[61][51][51];
//memoized recursion that finds the probability to pick
//a village i given some conditions:
// good: Amount of villages that can be picked
// before the village i.
// bad: Amount of villages that cannot be picked before i.
// need: If need!=0, then at least one of these villages
// must be picked before i. They are a subset of good
//
double probDo(int good, int need, int bad) {
double &res = mem[good][need][bad];
if (! seen[good][need][bad] ) {
seen[good][need][bad] = true;
//total amount of vilalges available to pick:
double n = good + bad + 1;
if ( need == 0) {
// pick the wanted village
res = 1 / n;
// pick a good village
if ( good ) {
res += (good / n) * probDo(good-1,0,bad);
}
} else {
// pick a needed village:
res = (need / n) * probDo(good-1, 0, bad);
// pick a good village that is not needed:
if ( good > need ) {
res += ( (good-need) / n) * probDo(good-1, need, bad);
}
}
}
return res;
}
double determineLength(vector <int> cityX, vector <int> cityY,
vector <int> villageX, vector <int> villageY)
{
//initialize memoization.
memset(seen,0,sizeof(seen));
int vn = villageX.size(), cn = cityX.size();
double sum = 0;
for (int i=vn; i--;) {
long long d2city = numeric_limits<long long>::max();
for (int j=cn; j--;) {
long long dx,dy;
dx = cityX[j] - villageX[i];
dy = cityY[j] - villageY[i];
d2city = std::min(d2city, dx*dx + dy*dy);
}
set<long long> pick;
pick.insert(d2city);
long long d2[vn];
for (int j=vn; j--;) {
long long dx,dy;
dx = villageX[j] - villageX[i];
dy = villageY[j] - villageY[i];
d2[j] = dx*dx + dy*dy;
if ( j != i) {
pick.insert(d2[j]);
}
}
double villageExpected = 0.0;
// = sum( X * prob_X )
for_each(p, pick) { //iterate through all possible X
//We are using a std::set in this case to
//avoid checking a X twice. You can use whatever is
//most comfortable for you.
long long x = *p;
double prob;
//Find the probability x was the minimum distance:
if ( *p > d2city ) {
prob = 0;
} else if (*p == d2city ) {
// number of villages with
// a distance greater than or equal to d2city
int c = 0;
for (int j=vn; j--;) {
if ( i!= j ) {
if (d2[j] >= d2city ) {
c++;
}
}
}
// probability only a subset of the c
// villages are picked before j
prob = probDo(c,0,vn-1-c);
} else {
// number of villages with
// a distance greater than x
int cg = 0;
// number of villages with
// a distance equal to x
int ce = 0;
for (int j=vn; j--;) {
if ( i!= j ) {
if (d2[j] == x ) {
ce++;
} else if (d2[j] > x) {
cg++;
}
}
}
// probability at least one of the
// ce villages is picked and only
// villages of cg and ce are picked
prob = probDo(cg+ce, ce, vn-1-cg-ce);
}
villageExpected += (prob * sqrt(x) );
}
sum += villageExpected;
}
return sum;
}
};
2 comments :
There is a typo in your editorial. You use "X>dcity" and "dcity<X" as two different cases.
Right, it has been fixed.
Post a Comment