I believe I have the optimal score for this problem.

I do binary search on the minimum radius that allows to cover all the cities with K shelters. Then the problem is reduced to Set Cover - can we choose K sets (shelters) that cover all the cities.

To solve Set Cover, I do several simplifications of the sets:
- if some set is empty, remove it
- if some city is covered by only one set, choose that set
- if S is a subset of T, remove S
- if the sets covering a city A are a subset of the sets covering a city B, remove the city B

Also from time to time, I try the greedy strategy:
- choose the largest sets
- if A is covered by at most 2 sets, choose the larger of these

Also I have an easy check if the solution is impossible - if the sum of sizes of the K largest sets is less than the number of cities.

Once no more simplifications are possible, I split the problem (with backtracking). Choose the city covered by fewest sets, choose the largest set covering the city and either select that set or not select that set.

My solution for Herdkeeper:

1. Put each antelope in its own group

2. For each antelope, if it single, join it with the closest group.

3. If best solution - store.

4. Find two closest groups and join them.

5. If more than 1 group: goto 3.

I repeat the whole process a few times, because there is some randomness (order of processing of antelopes and pairs of groups).

Unlike most of the rest of the solutions, my Turing machine is generated automatically. Then I compressed it into a C++ program

Every time the machine sees a new pair of sounds, it is in one of the first 191 states. Each of these corresponds to a sequence of moves that we would like to make before continuing with the rest of the music (0=empty sequence).

At this point, the machine makes a decision - what sequence of moves to make now before moving to the next cell (A) and what sequence to pass on to the right (B). There are 191 possibilities for B and 62 possibilities (sequences that move around and come back) for A.

The choices of A and B were precalculated to minimize the edit distance and penalize passing long sequences to the right.

Now, B%16 is written to the tape , A and the rest of B is in encoded as the state numer (192/16 * 62 = 744, plus some states to deal with the end of input). 806 states are used to do the appropriate "dance" around this point, come back, read B%16 and move to the right into state B.

I would like to know if you got a polynomial time solution for problem OFBEAT. I used some backtracking (but probably not enough, because I got WA).
Btw, these were the test cases I used:
6
14
+2 +2 +2 +2 -4 +2 +1 +2 -3 +2 -2 -8 +4 -2
30
+5 +1 -2 +1 +2 +2 +1 +1 -1 +1 -1 -1 -1 -2 -1 +1 -1 +2 -1 -1 -1 +1 -1 -2 +2 -2 +2 -1 -2 -1
32
+5 +1 -2 +1 +2 +2 +1 +1 -1 +1 -1 -1 -1 -2 -1 +1 -1 +2 -1 -1 -1 +1 -2 -1 +1 -1 +2 -2 +2 -1 -2 -1
12
+1 +1 +2 +2 -1 -1 -3 +1 -1 -2 +2 -1
14
+3 +2 -1 -1 -1 +2 +2 +2 -1 -1 -1 +1 -1 -5
14
+5 +6 -5 -4 +3 +2 -1 -1 -1 +2 +3 -4 -4 -1

My outputs are:
4
7
8
4
5
6

Are my outputs correct?

My solution to herdkeeper was quite simple:
Start with all points. For each point, try 5 different lines through it for separating the set of points into two halves. Select separation line which minimizes the sum of the perimeters of the convex hulls of the two sets. If this minimum value is smaller than the perimeter of the convex hull of the whole set of points, recursively try to split the two sets again.

My outputs are:
4
7
7
4
5
6

My algorithm for OFBEAT is O(n^2). It is most probably possible to implement the same ideas in O(n log n) using some kind of tree data structures.

I calculate the number of guarded vertical streets first, then rotate the polygon and do it again.

First I split the polygon into rectangles (sets of vertical streets). Each rectangle ends at the top and at the bottom with a wall. There can also be 0-width rectangles (for vertical streets touching walls to the left and to the right). To compute these rectangles, I scan left-to-right and keep a O(n) size array - for each segment between two different y's I store the number of the current rectangle.

Also, for each rectangle I store a list of rectangles it touches to the left and to the right, along with the segment along which they touch.

This way, I have a graph of rectangles. This graph is in fact a tree. There are O(n) rectangles.

Now for each rectangle I will choose whether or not to guard a vertical street in that rectangle. I will make that decision bottom-up in the tree (starting from the leaves) greedily. Each rectangle (recursively) returns an array of horizontal streets that are covered.

If some horizontal street in a given rectangle is not covered by the children AND it cannot be covered by the parent (because they do not share that street), then we must guard one vertical street in the rectangle. Otherwise, we do not guard any street - we can always postpone it to the parent.

Hmm, I can't see the solution using only 7 guarded streets for my 3rd test case. The image looks like:

I guard 4 vertical and 4 horizontal streets.

Ok, I see it now. Move the third (from left) guarded vertical street one to the left; then the 2nd (from bottom) guarded horizontal street can be removed.

Wow, pictures!

The guarded streets do not have to be connected (there was a change in the problem statement). So that horizontal street can be removed anyway.

I wonder if the author had a solution for connected sets of streets or if it was a bug in the problem statement.

The vertical and horizontal guarded streets do not depend on each other - simply every horizontal street has to cross a guarded vertical street and vice-versa.

Oops, they are not connected in your 7-solution...

Anyway, you can remove the horizontal street without moving any other streets.

for that input above i get the same answer:
4
7
8
4
5
6

i cannot see the pictures.. But i draw the case 3 myself but I really cannot find a solution with 7 street selected. Is that necessary for patrolled streets to be intersected?

My algorithm look like tomek's and i uses a line-tree(i don't know how to spell it) to make it O(nlogn).
For case 3:
I assume the first step walks towards +x and the second towards +y.
For vertical streets, using greedy algorithm i have to choose 4 of them; and for horizontal ones i choose 4, too. Could you please tell me what is the problem i have?

I just uploaded the pictures again, in case you want to take a look.

i can see..
thank you so much..

Oh!!!
I know what's the problem ... Thanks a lot..
I should deal with the points but not the lines!!

any hard datacase ?

i'm getting wrong all the time .. .