Updates from January, 2017 Toggle Comment Threads | Keyboard Shortcuts

  • loctv 8:59 pm on January 26, 2017 Permalink | Reply
    Tags: ,   

    Problem: Flood Fill Algorithm 

    *Difficulty: Easy

    Given a 2D screen, location of a pixel in the screen ie(x,y) and a color(K), your task is to replace color of the given pixel and all adjacent same colored pixels with the given color K.

    Input:
    The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. The first line of each test case contains Two integers N and M denoting the size of the matrix. Then in the next line are N*M space separated values of the matrix. Then in the next line are three values x, y and K.

    Output:
    For each test case print the space separated values of the new matrix.

    Constraints:
    1<=T<=10
    1<=M[][]<=100

    Example:
    Input:

    2
    3 4
    0 1 1 0 1 1 1 1 0 1 2 3
    0 1 5
    2 2
    1 1 1 1
    0 1 8

    Output:
    0 5 5 0 5 5 5 5 0 5 2 3
    8 8 8 8

    Implementation: Python 2.7

    def floodFill(rootColor, visited, screen, replaceColor, x, y):
        # set color of x,y on the screen
        screen[x][y] = replaceColor
        # mark them as visited
        visited.append((x, y))
        # get all 4 directions 
        # first I make a mistake, I get all 8 directions
        # but in the end, it's wrong
        all_directions = [(x-1, y), (x, y+1),
                            (x+1, y), (x, y-1)]
        # filter those 4 directions
        # only get which one is in screen, not yet visited and has rootColor
        all_directions = filter(lambda coor: isInScreen(coor[0], coor[1], screen) and not (coor[0], coor[1]) in visited and screen[coor[0]][coor[1]] == rootColor , all_directions)
        # recursive call for those all directions
        for (next_x,next_y) in all_directions:
            floodFill(rootColor, visited, screen, replaceColor, next_x, next_y)
        
    
    # check if (x, y) is in screen (not out of bound)
    def isInScreen(x, y, screen):
        return x >= 0 and x < len(screen) and y >= 0 and y < len(screen[0])
    
    def printScreen(screen):
        for row in screen:
            for col in row:
                print col,
        print
    
    def main():
        t = input()
        for _ in range(t):
            n, m = map(int, raw_input().strip().split())
            arr = map(int, raw_input().strip().split())
            x, y, replaceColor = map(int, raw_input().strip().split())
            screen, visited = [], []
            # convert list-like array to matrix (actually is a list of list)
            for i in range(0, len(arr), m):
                screen.append(arr[i:i+m])
            rootColor = screen[x][y]
            floodFill(rootColor, visited, screen, replaceColor, x, y)
            printScreen(screen)
            
    if __name__ == '__main__':
        main()
    
    Advertisements
     
  • loctv 1:43 am on January 26, 2017 Permalink | Reply  

    Problem: Sum of All Subarrays 

    *Difficulty: Medium

    Given an array A with N elements , you need to find the sum all sub arrays of array A. Since the sum could be very large print the sum modulo (10^9+7).

    Input :
    The first line contains integer T, denoting number of test cases. The first line of each test case contains an integer N, denoting the number of elements.The second line of each test case contains N space separated integers denoting values of the array A.
    Output :
    Print the answer of each test case in a new line.

    Constraints :
    1<=T<=10
    1<=N<=10^5

    Example
    Input :

    2
    3
    1 2 3
    2
    1 3

    Output :
    20
    8

    *Approach 1:

    Generate all sub arrays
    This is O(n^3) complexity solution

    Code: Python 2.7

    def sum_all_sub_arrs(arr):
        if len(arr) == 1:
            return arr[0]
        elif len(arr) == 2:
            return arr[0] + arr[1] + sum(arr)
        elif len(arr) == 3:
            return sum(arr)*2 + arr[0] + arr[1] + arr[1] + arr[2]
        else:
            sum_all = 0
            for i in range(2, len(arr)):
                for j in range(len(arr)):
                    #print arr[j:j+i]
                    sum_all += sum(arr[j:j+i])
                    if j+i == len(arr):
                        break
            return sum_all + sum(arr)*2
    
    if __name__ == '__main__':
        t = input()
        for _ in range(t):
            n = input()
            arr = map(int, raw_input().strip().split())
            print sum_all_sub_arrs(arr) % (10**9+7)
    

    It cant be applied to solve this problem, since if using C++, I can barely pass this problem with runtime nearly reach 5 seconds. (This is Python, so it’s impossible)

    After 30 minutes working on papers, I figured out something’s interesting.
    Example with input array’s length is odd
    Array: 1 2 3 4 5
    Sum of all sub-arrays:
    1 + 2 + 3 + 4 + 5 + 1 + 2 + 2 + 3 + 3 + 4 + 4 + 5 + 1 + 2 + 3 + 2 + 3 + 4+ 3 + 4 + 5 + 1 + 2 + 3 + 4 + 2 + 3 + 4 + 5 + 1 + 2 + 3 +4 + 5 = 105
    Here’s is the array and the number of times of each element in the equation above:
    Array:              1 – 2 – 3 – 4 – 5
    Frequency:     5 – 8 – 9 – 8 – 5
    Example with input array’s length is even
    Array: 1 2 3 4
    Sum of all sub-arrays:
    1 + 2 + 3 + 4 + 1 + 2 + 2 + 3 + 3 +4 + 1 +2 +3 + 2 + 3 + 4 + 1 +2 + 3 + 4 = 50
    Array:           1 – 2 – 3 – 4
    Frequency: 4 – 6 – 6 – 4
    In general:
    + if length of input array is odd, and n is the length
    Frequency: n –  prev+(n-2)  – prev+(n-4) – … – prev+1  – … – prev+(n-4)  – prev+(n-2) – n
    + if length of input array is even, and n is the length
    Frequency: n – prev+(n-2) – prev+(n-4) – ….. – prev+(n-4) – prev+(n-2) – n

    Code: Python 2.7

    def sum_all_sub_arrs(arr):
        # input array contains only one element
        if len(arr) == 1:
            return arr[0]
        # init steps
        frequency = [0]*len(arr)
        dif = len(arr)-2
        # because frequency values are symmetric
        # example: 4 6 6 4
        #          3 4 3
        #          etc
        # we need to traverse only half first of the input array
        # and work out the frequency of each value
        for i in range(0, len(arr)//2 + 1 if len(arr) % 2 != 0 else len(arr)//2):
            # first frequency = len(arr)
            if i == 0:
                frequency[i] = len(arr)
            # then, each of next element is its previous cell plus difference
            # and decrease the difference by 2
            else:
                frequency[i] += (frequency[i-1] + dif)
                dif -= 2
        # half left of frequency
        for i in range(len(arr)//2+1 if len(arr) % 2 != 0 else len(arr)//2, len(arr)):
            offset = len(arr) - i - 1 
            frequency[i] = frequency[offset]
        return sum(x*y for (x,y) in zip(arr, frequency))
    
    if __name__ == '__main__':
        t = input()
        mod = 10**9 + 7
        for _ in range(t):
            n = input()
            arr = map(int, raw_input().strip().split())
            print sum_all_sub_arrs(arr) % mod
    

    Solution took: 94ms

     
c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel