Update appNew update is available. Click here to update.
sidenav-btnClose
Topic list
City Lights
HARD
50 mins
Sorting
Topics (Covered in this problem)
Problem solved
Badge
Skill meter
Sorting
-
-
Other topics
Problem solved
Badge
Skill meter
Strings
-
-
Matrices (2D Arrays)
-
-
Linked List
-
-
Binary Search
-
-
Stacks & Queues
-
-
Trees
-
-
Graph
-
-
Dynamic Programming
-
-
Greedy
-
-
Tries
-
-
Arrays
-
-
SQL
-
-
Binary Search Trees
-
-
Heap
-
-
Bit Manipulation
-
-
Solve problems & track your progress
Checkout your overall progress in every topic here
Become
userLevel
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.

City Lights

Contributed by
Jaypal Mudaliyar
Hard
yellow-spark
0/120
Avg time to solve 50 mins
Success Rate 40 %
Share
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 )
Sample Input 1 :
2
6 6 3
6 1 4
1 0 5
10 4 2
2 7
1 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 :
2
20 6 4
1 8 13 20
5 5 5 5
5 1 5
0 1 2 3 5
0 0 0 0 1
Sample Output 2 :
4
-1
Reset Code
Full screen
Auto
copy-code
Console