akshayk0406's blog

IOI 2000 Problem POST
By akshayk0406, 13 years ago, In English
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.
Tags dp
  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
13 years ago, # |
  Vote: I like it +3 Vote: I do not like it
Try to think, why it is better to put every post on the points given, not between them. You can notice, that the best results if you put between or on points are the same;
After that do dynamic programming dp[I][J],
where - what is the best result if we assuming only first I points and last put post befoure I was on J.

If I remeber right, you should do O(n3) dynamic programming then.
→ Reply
13 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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.

→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Thanks to both of you.
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 ?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Sorry, my bad, the correction would be as follows: let's put the pairs (coordinates, cities) of in a set/map; then, calculating dx[i][j], we find the first city k so that . Then we add to dx[i][j] value sx[i] - sx[k] - k· (xi - xk). In this step we have added the distances between the i-th city and cities that have the PO in i-th city as their nearest PO, that is, cities k, k + 1, ..., i - 1. To add the distances from city j to cities j + 1, j + 2, ..., k - 1, we can go in the opposite direction add do the same thing.

    Maybe there is an easier method to get dx[i][j]...
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
To find city k , we could binary search. This would lead to O(v*v*(log(v)) solution for calculating 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 ?

→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Not quite, since s2 denotes now the sum of the distances from j, j + 1, ..., k - 1 to city k. It should be instead the sum of the distances from city j to cities j + 1, j + 2, ..., k - 1. Suggestion is such that we should calculate s2 by going in another direction and finding it in the same manner as we did with s1.

    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. :)
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Yeah , now I got the concept of finding the value of s1 and s2.
Thanks for helping me through this problem
→ Reply