Connection Status:
Competition Arena > RadarSabotage

RadarSabotage

TCO11 Round 4 · 2011-05-07 · by vexorian

TCO11 Round 4 · 2011-05-07 · by vexorian · Geometry, Graph Theory
Class Name: RadarSabotage
Return Type: int
Method Name: minimumDifference
Arg Types: (int, int, vector<int>, vector<int>, vector<int>)
Problem Statement

Problem Statement

The final battle between Feudalia and Banania is nearing. Before Feudalian forces reach the Bananian capital, they must cross a well-watched portion of land of dimensions W x H without getting detected by any of the Bananian radars. There are two walls at the left and right sides of the portion of land which you can consider to be infinitely long. One of those walls connects points (0,0) and (0,H) and the other connects points (W,0) and (W,H).

The locations of the radars are given by int[]s radarX and radarY. Each radar i has a power level that is initially set to radarPower[i]. The power level of a radar is a non-negative integer value equal to its power consumption. If the power level of radar i is P, then its detection radius is P*P, which means that the radar can detect any movement within all points with a distance to (radarX[i], radarY[i]) less than or equal to P*P.

The Feudalian force must find a path to take between the bottom and top sides of the rectangle such that none of the points in the path are within the detection radius of any radar. Formally, the path must be a curve that connects two points (x0, 0) and (x1, H) which does not cross either of the two walls, and for every point (x,y) in the path and a radar i, the distance between (x,y) and the radar must be strictly larger than P*P where P is the power level of the radar.

You are a Feudalian spy with the ability to modify the power level of any radar to any non-negative integer value that is not larger than the radar's original power level. Set the power levels in such way that the Feudalian force can cross the rectangle without being detected. If there are multiple ways to do it, minimize the difference in total power consumption between the initial setup and the final setup so that the sabotage is more difficult to notice. Return the minimum difference in power usage that is required to make the land crossable.

Constraints

  • W and H will each be between 3 and 1000, inclusive.
  • radarX will contain between 1 and 30 elements, inclusive.
  • radarX, radarY and radarPower will contain the same number of elements.
  • Each element of radarX will be between 1 and W-1, inclusive.
  • Each element of radarY will be between 1 and H-1, inclusive.
  • Each element of radarPower will be between 1 and 200, inclusive.
  • No two radars will be located at the same point.
Examples
0)
8
20
{4}
{4}
{10}
Returns: 9

There is only one radar initially with a power level of 10. If the power level is changed to 1, the radius of the radar will become 1*1 = 1, and it will be possible to pass. If we only changed the level to 2, the radius would become 4, and it would not be possible to pass:

1)
3
5
{1,1,2}
{1,2,2}
{1,1,1}
Returns: 1

If we turn the third radar off a path for the army will be possible.

2)
6
16
{1,3,5}
{8,8,8}
{2,2,2}
Returns: 3

A possible solution is to set the first radar's power level to 0 and the second radar's level to 1.

3)
51
4
{46,8}
{2,1}
{8,8}
Returns: 8
4)
24
32
{3,6,10,18,13}
{18,23,10,13,26}
{2,2,2,3,1}
Returns: 0

The army is already able to cross without being detected. No change is necessary. Note that the path does not necessarily have to be a straight line:

Submissions are judged against all 111 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class RadarSabotage with a public method int minimumDifference(int W, int H, vector<int> radarX, vector<int> radarY, vector<int> radarPower) · 111 test cases · 2 s / 256 MB per case

Submitting as anonymous