Hi,
I was trying to solve problem POST from IOI 2000(Day 2) but i was not able to come up with solution. Even though editorial mentions a DP solution i am not able to figure the recurrence.Can anyone provide me with little more insights to solve this problem.
Thanks.
I was trying to solve problem POST from IOI 2000(Day 2) but i was not able to come up with solution. Even though editorial mentions a DP solution i am not able to figure the recurrence.Can anyone provide me with little more insights to solve this problem.
Thanks.
If I remeber right, you should do O(n3) dynamic programming then.
My approach would be: suppose we have an array d[cityi][postcnt] which has an answer for first i cities and postcnt post offices placed within them, but with a condition that there is a post office in city i. Then for city k we can obtain d[k][c] as min(d[k - 1][c - 1] + dx[k][k - 1], d[k - 2][c - 1] + dx[k][k - 2], ...), where dx[i][j] is defined as the sum of the minimal distances to the PO from cities i + 1, i + 2, ..., j - 1, provided that there are PO in cities i and j. Then the answer to the problem would be d[V + 1][P + 1], where city V + 1 is a dummy far far away to the right. The complexity of this is O(V2P).
Now how do we calculate dx? Let's make an array sx, where sx[i] is the sum of the distances from cities [1, i - 1] to i-th city. It's clear sx[1] = 0. Then sx[i] = sx[i - 1] + (i - 1)· (xi - xi - 1), where x are the coordinates of the cities. Now that we have sx, dx[i][j] = sx[i] - sx[j] - j· (xi - xj), where i > j (draw this on paper, then it's easier to see). It's clear we obtain dx in O(V2), so it doesn't slow down the main algorithm.
Finally, to reconstruct the sequence of PO, it is enough to save the previous city in each of the d[i][c] states.
But still I am not able to able to understand how does relation for calculating dx[i][j] is derived.How does we ensure that for each city between i we take it disatance to nearest post-office ?
Maybe there is an easier method to get dx[i][j]...
s1 = sx[i]-sx[k]-k*(x(i)-x(k));
s2 = sx[k]-sx[j]-j*(x(k)-x(j));
then dx[i][j]=s1+s2
Is this correct ?
Anyway, since V ≤ 300, I think it is enough for each dx[i][j] to check all the cities between j and i, find which PO (in i or j) is nearest to it, and add the corresponding distance. That gives O(V3), which should also be fine.
P.S. Ok, villages, not cities, but hope you don't mind. :)
Thanks for helping me through this problem