PROBLEM LINK:
Setter: Praveen Dhinwa
Tester: Misha Chorniy
Editorialist: Taranpreet Singh
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Inclusion-Exclusion, Union of Rectangles, and Observation to use Brute force.
PROBLEM:
Given a set of position of K lights in a N*N grid having bottom left corner at (0,0) and top right corner at (N-1,N-1). Each street light can be oriented to one of the four ways bottom left, bottom right, top left, and top right. When the street light is oriented toward a corner, it lights the whole rectangle formed between the position of the light and the corner point.
Determine whether it is possible to light the whole grid or not.
QUICK EXPLANATION
- If K \geq 4, It is always possible to light the whole grid.
- Otherwise, we can try all combinations of directions assigned to lights and check if any combination leads to lighting whole grid or not. If any combination lights the whole grid, the answer is YES, otherwise answer is NO.
EXPLANATION
Brace yourself for the shock, because the answer is always YES whenever the number of street lights is \geq 4.
Reason
Let us take two points. We direct two lights towards diagonally corners as in the image. The white circles represent the position of chosen points.
Now, the only regions left to be covered are the two white regions at corners. We can divide the covered regions into four type of regions, represented by each color in the image.
Any point in the purple region can be used to light any of the two uncovered regions. Any point in red regions can cover the top left uncovered region while points in the blue region can cover bottom right uncovered region. Points in the black region cannot cover either region alone.
Now, Points in the black region are useless, so ignore them.
If we have all the points in either red region or in the blue region, we are unable to cover both uncovered regions simultaneously.
But, it can be seen that when we have K \geq 4 and we try all combinations of a pair of points and assign them directions like shown in the image, we will have at least one case where all points are not inside the red region or in the blue region only.
Hence, we can simply print YES when we have K \geq 4.
Case when K < 4
So, Now for K < 4 we shall try all combinations of directions.
When assigned a particular direction, it shall be covering a rectangle area formed by the light source and one of the corner. We want the whole grid to be covered. This way, if we have direction assigned to all lights, the problem becomes to check if the union of K rectangles cover the whole grid or not. But checking union is not really a simple thing.
But Since we know, that all our rectangles lie inside the grid, then if the union of K rectangles covers the whole grid, union of rectangles actually coincide with grid and thus, have the same area. We can also prove, that if the area of the union of rectangles differs from the area of the grid, the union of rectangles doesn’t cover the grid.
So, all we need is to find the area of the union of rectangles. It can be done in the same way we do in set theory, Union and Intersection of sets.
If we have two rectangles, Area of the union is given by Area of first rectangle plus area of second rectangle less area of intersection of both rectangles.
If we have three rectangles, Area of the union becomes the sum of areas of rectangles less sum of areas of intersections of all pairs of rectangles plus the area of intersection of all three rectangles.
We may generalize this to the larger number of rectangles if we want to.
This way, we try all combinations, calculate the area of the union of rectangles. If the area of the union for any combination is same as the area of the grid, we can cover the grid. Otherwise, we cannot.
For reference, Area of Union of N rectangles can also be calculated much faster than O(2^N) as discussed in this blog, though it suffices to calculate it by inclusion-exclusion since K is small.
Time Complexity
Time complexity is O(T*4^3*2^3) in the worst case when we have K = 3 in all test cases. The number of ways to assign directions is 4^K while calculating union of K rectangles takes 2^K time.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution
Tester’s solution
Editorialist’s solution
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 