Discussion on Ema's Supercomputer Challenge

4 weeks ago+ 0 comments

Finally done in 3 submission. Like others, always struggling on finding a smarter way but brute force at the end.

Here's something I would like to share that I think it's a smarter way to find max possible pluses on each block. This is NOT to find 2 pluses with max product. It's only an idea of how to determine the largest plus if current cell is the center.

An easier way to find a plus is iterating on each cell and trying to count the connecting good cells on 4 directions. I saw many dissuasions were doing this. But form my understanding, this could lead to an O(n*m*(n+m)) runtime because each cell needs to look up the entire rows (n) and column (m), as well as there are n*m cells.

My idea is counting the maximum length while iterating on each cell. During the iteration, it would marks a count number on each cell continuously. If it is good, count + 1. When a bad cell is hit or the row/column is end, count = 0 and update previous 1/2 count of good cells. For example, if we have 6 good cells in a row, it would be marked as 1 2 3 4 5 6 after the iteration. When the iteration hit the 7th cell (a bad cell), it would update this row to 1 2 3 3 2 1. In this case, each number on the cell represents the max number of good cells on the right and left (including the current cell) if current cell is a center. By doing same thing horizontally, we can have numbers that represents max number of good cells on the top and bottom if current cell is center. Combining these two table together, we can have the possible max size of plus on each cell. In this method, the worst case runtime should be O(n*m).

def twoPluses(grid):
    # Write your code here
    n_rows = len(grid)
    n_columns = len(grid[0])
    
    lr_grid = [[0] * n_columns for i in range(n_rows)]
    max_jv = 0
    for i in range(n_rows):
        last_bad_j = -1
        for j in range(n_columns+1):
            if j == n_columns or grid[i][j] == "B":
                for x in range(j-1, last_bad_j, -1):
                    new_v = j - x
                    if (new_v < lr_grid[i][x]):
                        lr_grid[i][x] = new_v
                    else:
                        max_jv = max(max_jv, lr_grid[i][x])
                        break
                last_bad_j = j
            else:
                # if grid[i][j] == "G":
                lr_grid[i][j] = j - last_bad_j
            
    ud_grid = [[0] * n_columns for i in range(n_rows)]
    max_iv = 0
    for j in range(n_columns):
        last_bad_i = -1
        for i in range(n_rows+1):
            if i == n_rows or grid[i][j] == "B":
                for y in range(i-1, last_bad_i, -1):
                    new_v = i - y
                    if (new_v < ud_grid[y][j]):
                        ud_grid[y][j] = new_v
                    else:
                        max_iv = max(max_iv, ud_grid[y][j])
                        break
                last_bad_i = i
            else:
                # if grid[i][j] == "G":
                ud_grid[i][j] = i - last_bad_i
            
    max_grid = [[0] * n_columns for i in range(n_rows)]
    cross_list = [[] for i in range(min(max_jv, max_iv) + 1)]
    for i in range(n_rows):
        for j in range(n_columns):
            valid_cross = min(lr_grid[i][j], ud_grid[i][j])
            max_grid[i][j] = valid_cross
            if valid_cross > 0:
                cross_list[valid_cross].append((i, j))
    print(grid)
    print(lr_grid)
    print(ud_grid)
    print(max_grid)
    print(cross_list)
  ... rest of the code - brute forcing the solution

Cookie support is required to access HackerRank