New update is available. Click here to update.

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

City Lights

Contributed by

Jaypal Mudaliyar

Hard

0/120

Avg time to solve 50 mins

Success Rate 40 %

0 upvotes

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’.

Detailed explanation ( Input/output format, Notes, Constraints, Images )

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

Sample Input 1 :

Sample Output 1 :

1
-1

Explanation Of Sample Input 1 :

For the first test case,

It is clearly visible, that it is advantageous to fix only the street light at position ‘4’.
Hence, the output will be: 1

For the second test case,

It is clearly visible, that even if we fix all the street lights of the city, we can’t have the luminance of new street lights in the whole city. Hence the output is ‘-1’
Hence, the output will be: -1

Sample Input 2 :

Sample Output 2 :

4
-1

Auto

Console