Google Kickstart Round A 2021: L-shaped Plots

This is one of those problems which may look particularly very complex at first glance but ain’t that difficult in fact. Let’s see how we can approach that ‘not-so-difficult’ solution to the this problem.

Problem Statement: L-shaped Plots

Given a grid of R rows and C columns each cell in the grid is either 0 or 1.

A segment is a nonempty sequence of consecutive cells such that all cells are in the same row or the same column. We define the length of a segment as number of cells in the sequence.

A segment is called “good” if all the cells in the segment contain only 1s.

An “L-shape” is defined as an unordered pair of segments, which has all the following properties:

• Each of the segments must be a “good” segment.
• The two segments must be perpendicular to each other.
• The segments must share one cell that is an endpoint of both segments.
• Segments must have length at least 2.
• The length of the longer segment is twice the length of the shorter segment.

We need to count the number of L-shapes in the grid.

Input

The first line of the input contains the number of test cases, T. T test cases follow.

The first line of each testcase contains two integers R and C.

Then, R lines follow, each line with C integers representing the cells of the grid.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the number of L-shapes.

For all the limits and test cases you can check the official problem page for L-shaped Plots here.

Solution

The simplest logic involves calculating all the L-shaped plots made by each cell in the given matrix. The way in which we find these plots will be the difficult part.

Suppose we have a cell Aij from the given grid A. Consider this cell to be the meeting point of the two segments of some L-shaped plot. There are at most four such type of L-shaped plots, one in each of the four directions. Have a look at the figure below.

The only tricky part here is to calculate the number of L shaped plots for a particular cell Aij as the meeting point of the segments of the plot in the given grid A. But first we need to find segments in all the four directions top, down, bottom and left. “Segment” here means all cells with continuous 1s in a line. By prefix sum we can easily find the lengths of longest segments for each cell in the grid extending in all the directions.

To calculate the number of L-shaped plots having Aij cell as the meeting point of both of its segments, we need to apply some algebra here. Let a represent the length of the segment X from Aij and continuing towards the top of the grid. Similarly consider b represent the length of the segment Y from Aij and continuing towards left.

Intuitively, the number of plots with segment X as the largest segment will be min( a//2, b ) - 1. Here we are substracting 1 as we don’t want to consider plots having segment lengths shorter than 2.

In the same manner, the number of plots with segment Y as the largest segment will be min( a, b//2 ) - 1. Thus for L-shaped plot with with one segment to the top and one to the left, we can have below number of plots:-

min( a//2, b ) + min( a, b//2 ) - 2

Have a look at the complete code below :-

rr = input
rri = lambda: int(rr())
rra = lambda: list(map(int, rr().split()))
def solve(arr,m,n):
    res=0

    #Initialze the prefix sum arrays for all 4 directions
    top=[[0]*n for _ in range(m)]
    left=[[0]*n for _ in range(m)]
    bottom=[[0]*n for _ in range(m)]
    right=[[0]*n for _ in range(m)]

    # first calculate the sum from bottom and right.
    for i in range(m-1,-1,-1):
        for j in range(n-1,-1,-1):
            if arr[i][j]:
                bottom[i][j]=bottom[i][j+1] +1 if j+10 else 1
                left[i][j]= left[i-1][j]+1 if i>0 else 1

                a,b,c,d = top[i][j],left[i][j], bottom[i][j],right[i][j]
                #Finally we calculate the number of plots in all 4 directions using the prefix sums
                res+= min(a//2,b) + min(b//2,a) - 2 if a>1 and b>1 else 0
                res+= min(c//2,d) + min(d//2,c) - 2 if c>1 and d>1 else 0
                res+= min(a//2,d) + min(d//2,a) - 2 if a>1 and d>1 else 0
                res+= min(b//2,c) + min(c//2,b) - 2 if b>1 and c>1 else 0
            
    return res

T = rri()
for t in range(1, T + 1):
    m,n = rra() #multiple input - 1 D
    arr = []
    for i in range(m): #2D
        arr.append(rra())
    print('Case #{}: {}'.format(t, solve(arr,m,n)))

Time Complexity: O(R*C)

It will cost us O(R*C) time in total as we are traversing the grid twice.

Space Complexity: O(R*C)

O(R*C) space will be consumed for storing all the 4 prefix sum arrays.