Last Updated: 9 Jul, 2022

City Lights

Hard

Solve now

Problem statement

Your friend Aayush is a successful businessman and earned a lot of profit this year and thought of helping out the residents of his city by renovating the old street lights of his city.

The city is a rectangle having ‘L’ as its length and ‘B’ as its breadth. The city can be imagined as a rectangular area on an X-Y plane having its left uppermost point at ‘(0, B/2)’ and right lowermost point at ‘(L, -B/2)’ (Check the image below for a better understanding).

Now in the current blueprint of the city there are ‘N’ street lights. They lie on the OX Axis if imagined in the X-Y plane whose position is given by the ‘POS’ array, all the street lights are at a distinct position. And each street light has a radius of ‘R[i]’ up to which it can illuminate the city from ‘POS[i]’.

Being a businessman Aayush decided to complete this work by replacing old street lights with new ones which will have the same position and radius as the previous street lights but with better efficiency.

But to save money and use it for other work he wanted to reduce the number of street lights to be replaced such that by replacing that many street lights the whole rectangular area of the city has the luminance of new street lights or conclude that even if he fixes all street lights there is no way the whole city can experience the luminance of new street lights.

Being his friend and a city planner Aayush asked you to help him out. Can you help him find the minimum number of street lights to be replaced such that the whole city can experience the luminance of the new street lights or print ‘-1’ if there is no way to fix the street light so that the whole area of the city can experience the luminance of new street lights?.

NOTE: The replaced street lights should cover each and every part of the city.

EXAMPLE :

Input: ‘L’ = 8, ‘B’ = 10, ‘N’ = 1, ‘POS’ = {4}, ‘R’ = {5}

Output: -1
In this case,

As shown in the figure above, even if we fix the only street light of the city, the whole city area can’t be covered. Hence the output is ‘-1’.

Input Format :

The first line will contain the integer ‘T’, the number of test cases.

Each test case consists of three lines.

The first line of input contains three integers, ‘L’, ‘B’, and ‘N’ separated by spaces.

The next line contains space-separated ‘N’ non-negative distinct integers, denoting the positions of the street lights in the city.

And the last line contains space-separated ‘N’ non-negative integers, denoting the radius of luminance of street lights in the city.

Output format :

For each test case, print the minimum number of street lights required to illuminate the whole city with new street lights or print ‘-1’ if it is impossible to do so.

Note :

You don't need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= ‘T’ <= 10
1 <= ‘N’ <= 10^5
‘N’ <= ‘L’ <= 10^5
1 <= ‘B’ <= 10^4
0 <= ‘POS[i]’ <= ‘L’
All ‘POS[i]’ are distinct, i.e. ‘POS[i] != POS[j]’ holds true for all ‘i != j’ such that ‘1’ <= ‘i’ <= ‘N’ and ‘1’ <= ‘j’ <= ‘N’
0 <= ‘R[i]’ <= 10^4
It is guaranteed that sum of ‘N’ over all test cases is <= 10^5
Time Limit: 1 sec

Solve now

Approaches

01 Approach

The idea for this approach is based on the properties of a circle.

From the above image, it is clear that if we select some street lights and the points of intersection of the circle formed by its radius and the line ‘Y = B/2’ i.e. points ‘(X1, B/2)’ and ‘(X2, B/2)’ covers the whole line segment ‘(0, B/2)’ to ‘(L, B/2)’, then each part of the city can experience the luminance of the new street lights.

Now to find ‘X1’ and ‘X2’ we can use the equation of the circle, shown in the figure.

Now for ‘Y = B/2’, the equation of the circle will be:

‘(X-P)*(X-P) + (B/2)*(B/2) = R*R’ — (1)

Now here, ‘X2 = P + D/2’

Now if we substitute the value of ‘X’ as ‘X2’ in the equation - 1, and use the above relation we get:

=> ‘(D/2)*(D/2) + (B/2)*(B/2) = R*R’, multiplying by ‘4’ both side.

=> ‘D*D + B*B = 4*R*R’

=> ‘D = SquareRoot(4*R*R - B*B)’. Let’s call ‘D/2’ as ‘V’ then,

=> ‘V = SquareRoot(4*R*R - B*B) / 2’.

=> ‘X1 = P - V’ and ‘X2 = P + V’.

And as we only have our line segment from ‘X=0’ to ‘X=L’, we can do the following modifications to values of ‘X1’ and ‘X2’.

=> ‘X1 = max(0, P - V)’ and ‘X2 = min(L, P + V)’.

Thus we can get points of intersection in this way, now after this, we have to select some subset of street lights to be fixed and check if it covers the whole line segment ‘(0, B/2)’ to ‘(L, B/2)’, if it doesn’t the answer is ‘-1’, else it’s the minimum of all possibilities.

This can be checked using a recursive algorithm in ‘O((2^N)*N)’ time complexity.

Algorithm:

// This function will check if the selected street lights cover the whole city area.

Bool isCovering(L, SELECTED, N)

If ‘N == 0’
- Return ‘FALSE’.
Sort the array ‘SELECTED’ in non-decreasing order of first of pair.
Initialize a variable named ‘LEFT’ with the value of ‘0’.
Initialize a variable named ‘RIGHT’ with the value of ‘0’.
Run a for loop from ‘0’ to ‘N-1’ with a variable named ‘i’.
- Initialize a variable named ‘LOW’ with the value of first of ‘SELECTED[i]’.
- Initialize a variable named ‘HIGH’ with the value of second of ‘SELECTED[i]’.
- If ‘RIGHT < LOW’
  - Return ‘FALSE’.
- Else
  - Assign ‘RIGHT’ the value of ‘max(RIGHT, HIGH)’.
If ‘LEFT == 0 and RIGHT == L’
- Return ‘TRUE’.
Return ‘FALSE’.

// This function will try out every subset of street lights and find the minimum required fixing of street lights.

Void getMinimum(i, L, N, RANGE, SELECTED, &ANS)

If ‘i == N’
- Initialize a variable named ‘SIZE’ with the value of the length of ‘SELECTED’.
- if ‘isCovering(L, SELECTED, SIZE) == TRUE’
  - Assign ‘ANS’ the value of ‘min(ANS, SIZE)’.
- Return.
Insert ‘RANGE[i]’ at the end of ‘SELECTED’.
Call ‘getMinimum(i+1, L, N, RANGE, SELECTED, &ANS)’.
Remove the last element of ‘SELECTED’.
Call ‘getMinimum(i+1, L, N, RANGE, SELECTED, &ANS)’.
Return.

// The function will return the minimum number of street lights required to be fixed.

Int cityLights(L, B, N, POS, R)

Create an array with the name ‘RANGE’ of length ‘N’ of the type which can store real-value pairs.
Run a for loop from ‘0’ to ‘N-1’ with a variable named ‘i’.
- Initialize a variable named ‘A1’ with the value of ‘4*R[i]*R[i]’.
- Initialize a variable named ‘A2’ with the value of ‘B*B’.
- Initialize a variable named ‘V’ with the value of ‘0’.
- If ‘A1>=A2’
  - Assign ‘V’ the value of ‘squareRoot(A1 - A2) / 2’.
- Assign the first of pair ‘RANGE[i]’ the value of ‘max(0, POS[i] - V)’.
- Assign the second of pair ‘RANGE[i]’ the value of ‘min(L, POS[i] + V)’.
Initialize a variable named ‘ANS’ with the value of ‘N+1’.
Create an empty list ‘SELECTED’.
Call ‘getMinimum(0, L, N, RANGE, SELECTED, ANS)’.
If ‘ANS == N+1’
- Assign ‘ANS’ the value of ‘-1’.
Return ‘ANS’.

Solve now

02 Approach

The idea of the above approach is similar to the brute force approach, but instead of trying out every possibility to fix the street lights, we sort the array formed by intersection range and pick greedily the street lights which have a larger range.

The sorted array will be in such a way that the range with the lowest left value comes first. Thus we can iterate on the array from left to right and keep track of the maximum high value up to which we can go with the current left value, initially its value will be ‘0’. Then we replace the current left value with a maximum high and increment the answer by one, and keep iterating until we reach the end of the array.

If at any point we stay on the same point after one iteration, it means there is an empty space in between street lights range i.e. no intersection, and thus we can return ‘-1’ from there.

Algorithm:

// The function will return the minimum number of street lights required to be fixed.

Int cityLights(L, B, N, POS, R)

Create an array with the name ‘RANGE’ of length ‘N’ of the type which can store real-value pairs.
Run a for loop from ‘0’ to ‘N-1’ with a variable named ‘i’.
- Initialize a variable named ‘A1’ with the value of ‘4*R[i]*R[i]’.
- Initialize a variable named ‘A2’ with the value of ‘B*B’.
- Initialize a variable named ‘V’ with the value of ‘0’.
- If ‘A1>=A2’
  - Assign ‘V’ the value of ‘squareRoot(A1 - A2) / 2’.
- Assign the first of pair ‘RANGE[i]’ the value of ‘max(0, POS[i] - V)’.
- Assign the second of pair ‘RANGE[i]’ the value of ‘min(L, POS[i] + V)’.
Initialize a variable named ‘ANS’ with the value of ‘0’.
Sort the array ‘RANGE’ in non-decreasing order of first of pair.
Initialize a variable named ‘LEFT’ with the value of ‘0’.
Initialize a variable named ‘maxRight’ with the value of ‘0’.
Initialize a variable named ‘i’ with the value of ‘0’.
Run a while loop until ‘i<N’.
- Initialize a variable named ‘LOW’ with the value of first of ‘RANGE[i]’.
- Initialize a variable named ‘HIGH’ with the value of second of ‘RANGE[i]’.
- If ‘LOW <= LEFT’
  - Assign ‘maxRight’ the value of ‘max(maxRight, HIGH)’.
  - Increment ‘i’ by ‘1’.
- Else
  - If ‘maxRight == LEFT’
    - Return ‘-1’.
  - Increment ‘ANS’ by ‘1’.
  - Assign ‘LEFT’ the value of ‘maxRight’.
If ‘maxRight != L’
- Return ‘-1’.
If ‘maxRight != LEFT’
- Increment ‘ANS’ by ‘1’.
Return ‘ANS’.

Solve now