Codeforces 427E – Police Patrol

Imagine that your city is an infinite 2D plane with Cartesian coordinate system. The only crime-affected road of your city is the x-axis. Currently, there are n criminals along the road. No police station has been built on this road yet, so the mayor wants to build one. [read on codeforces]

Let’s define a function cost(x) which gives the total value for the station put in x. One can make several algebraic observations.

First, we can limit ourselves to putting the station on spots with criminals. One can prove that between two subsequent criminals x and y values of cost(z) for x < z < y are greater or equal to min(cost(x),cost(y)).

Second, we can also remark that the cost is decreasing to a certain point and than increasing. In fact cost can be proven to be convex on a set of criminals.

Third, the strategy for computing the cost(x) can go like that:

  • take the leftmost criminal compute his distance from x and multiply by two,
  • remove m leftmost criminals (we take them together with the furthest one),
  • repeat as long as there are still criminals on left of x.

Then, do the same for the right side from x.

This gives already a neat solution O(n log n) if we implement cost like above and apply ternary search for finding the optimal value. And for C++ it is enough. For my python implementation it was not. So let’s tune it further.

The forth and the most important observation is that we will always have to reach the leftmost criminal and the rightmost and it will always take us the same amount of time no matter where we start. Therefore we can compute this cost and remove those guys together with m others beside them. Then we have the same problem but without 2*m guys.

We keep reducing the problem linearly and get an insanely simple solution of an E problem. Voila:

n, m = map(int,raw_input().split())
a = map(int,raw_input().split())

res, le = 0, 0

while le &lt; n:
    res = res + a[n - 1] - a[le]
    le, n = le + m, n - m

print 2 * res

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>