plane bombing problems- help

Question

I'm training code problems, and on this one I am having problems to solve it, can you give me some tips how to solve it please.

The problem is taken from here:

https://www.ieee.org/documents/IEEEXtreme2008_Competitition_book_2.pdf

Problem 12: Cynical Times.

The problem is something like this (but do refer to above link of the source problem, it has a diagram!):

Your task is to find the sequence of points on the map that the bomber is expected to travel such that it hits all vital links. A link from A to B is vital when its absence isolates completely A from B. In other words, the only way to go from A to B (or vice versa) is via that link.

Due to enemy counter-attack, the plane may have to retreat at any moment, so the plane should follow, at each moment, to the closest vital link possible, even if in the end the total distance grows larger.

Given all coordinates (the initial position of the plane and the nodes in the map) and the range R, you have to determine the sequence of positions in which the plane has to drop bombs.

This sequence should start (takeoff) and finish (landing) at the initial position. Except for the start and finish, all the other positions have to fall exactly in a segment of the map (i.e. it should correspond to a point in a non-hit vital link segment).

The coordinate system used will be UTM (Universal Transverse Mercator) northing and easting, which basically corresponds to a Euclidian perspective of the world (X=Easting; Y=Northing).

Input Each input file will start with three floating point numbers indicating the X0 and Y0 coordinates of the airport and the range R. The second line contains an integer, N, indicating the number of nodes in the road network graph. Then, the next N (<10000) lines will each contain a pair of floating point numbers indicating the Xi and Yi coordinates (1 < i<=N). Notice that the index i becomes the identifier of each node. Finally, the last block starts with an integer M, indicating the number of links. Then the next M (<10000) lines will each have two integers, Ak and Bk (1 < Ak,Bk <=N; 0 < k < M) that correspond to the identifiers of the points that are linked together.

No two links will ever cross with each other.

Output The program will print the sequence of coordinates (pairs of floating point numbers with exactly one decimal place), each one at a line, in the order that the plane should visit (starting and ending in the airport).

Sample input 1

102.3 553.9 0.2 
14 
342.2 832.5 
596.2 638.5 
479.7 991.3 
720.4 874.8 
744.3 1284.1 
1294.6 924.2 
1467.5 659.6 
1802.6 659.6 
1686.2 860.7 
1548.6 1111.2 
1834.4 1054.8 
564.4 1442.8 
850.1 1460.5 
1294.6 1485.1 
17 
1 2 
1 3 
2 4 
3 4 
4 5 
4 6 
6 7 
7 8 
8 9 
8 10 
9 10 
10 11 
6 11 
5 12 
5 13 
12 13 
13 14 

Sample output 1
102.3 553.9 
720.4 874.8 
850.1 1460.5 
102.3 553.9 

Answer 1

1. Pre-process the input first, so you identify the choke points. Algorithms like Floyd-Warshall would help you.
2. Model the problem as a Heuristic Search problem, you can compute a MST which covers all choke-points and take the sum of the costs of the edges as a heuristic.
3. As the commenters said, try to make concrete questions, either here or to the TA supervising your class.
4. Don't forget to mention where you got these hints.

Answer 2

The problem can be broken down into two parts.

1) Find the vital links.

These are nothing but the Bridges in the graph described. See the wiki page (linked to in the previous sentence), it mentions an algorithm by Tarjan to find the bridges.

2) Once you have the vital links, you need to find the smallest number of points which given the radius of the bomb, will cover the links. For this, for each link, you create a region around it, where dropping the bomb will destroy it. Now you form a graph of these regions (two regions are adjacent if they intersect). You probably need to find a minimum clique partition in this graph.

Haven't thought it through (especially part 2), but hope it helps.

And good luck in the contest!

Answer 3

I think Moron' is right about the first part, but on the second part... The problem description does not tell anything about "smallest number of points". It tells that the plane flies to the closest vital link. So, I think the part 2 will be much simpler:

• Find the closest non-hit segment to the current location.
• Travel to the closest point on the closest segment.
• Bomb the current location (remove all segments intersecting a circle)
• Repeat until there are no non-hit vital links left.

This straight-forward algorithm has a complexity of O(N*N), but this should be sufficient considering input constraints.