Attack On Titans

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
5 upvotes
Asked in company
IBM

Problem statement

Levi Ackerman implements a new strategy for the protection of his kingdom. For this, he assigns a few beast titans, on each level, a titan defends the Kingdom that is represented by a rectangular grid of cells. If a titan takes a position in some cells of the grid, then this titan defends all the cells in the same row and the same column. No two titans share a row or a column. The penalty of the position is the number of cells in the largest undefended rectangle.

For example 
The given figure has titans at coordinates at (3,8) and (8,6) and (11,2). We can see that the maximum undefended rectangle is of area 12 units, therefore, the position shown in the picture has a penalty of 12.

Help Levi to find out how much the penalty will cost the given positions of titans.

Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains three space-separated integers L, B, and N that are the length of the grid, breadth of the grid, and a number of beast titans, respectively. 

The next N lines of each test case contain two space-separated integer numbers X and Y  that represent the coordinates of the cell occupied by a titan.
Output format : 
For each test case, in a separate line, print a single integer which is the penalty of the given configuration.
Note: 
You don’t have to print anything; it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 5
1 <= L, B <= 3000
0 <= N <= MIN(L,B)
1 <= X <= L
1 <= Y <= B

Time Limit : 1 sec
Sample Input 1 :
2
6 6 2
2 5
5 2
4 4 1
1 1
Sample Output 1 :
4
9
Explanation For Sample Input 1:
For the first test case:
The given configuration according to the test case is - 


We can see that the maximum undefended rectangle is 4 units therefore the penalty for this case will be 4.

For the second test case:
The given configuration according to the test case is - 


Clearly, the maximum undefended rectangle is 9 units therefore the penalty for this case will be 9.

Sample Input 2 :

2
15 8 3 
3 8
8 6
11 2
3 3 0

Sample Output 2 :

12
9
Hint

 Can you check all the possible rectangles?

Approaches (2)
Brute Force

The idea is to find the area of all possible rectangles formed by the configuration that is every rectangle formed between any four belts of titan reign(that titan can protect) and tore the maximum area out of all the rectangles.

 

  • First, we will put all the x coordinates of the titans in an array and also add 1 and the L in the array for the boundary points.
  • Similarly, we will store the y coordinates of the titans in an array and here also add 1 and B in the array for boundary points.
  • Now sort both the arrays.
  • To calculate the area we will pairwise calculate the area, for every consecutive pair in x coordinates we will iterate for every pair in y coordinates array. For example, if x coordinate array is {1,2,3} and y coordinate array is {4,7,8} then we will calculate the area between 1, 2 and 4, 7 and then 1, 2 and 7, 8 and in this fashion for all other numbers.
  • The area will be (X[i] - X[i-1] -1) * (Y[j] - Y[j-1] -1).
  • And in each iteration, we will update the maximum area.
  • Finally, return the maximum area.
Time Complexity

O(N ^ 2), where N denotes the number of titans in the grid.

 

We are sorting the arrays of x coordinate and y coordinate and then we are iterating y coordinate array for every consecutive pair of x. Therefore, net time complexity will be O(N * log(N)) + O(N * N) = O(N * N).

Space Complexity

O(N), where N denotes the number of titans in the grid.

 

Since we are creating arrays to store x and y coordinates.

Code Solution
(100% EXP penalty)
Attack On Titans
Full screen
Console