Updates from March, 2017 Toggle Comment Threads | Keyboard Shortcuts

  • loctv 6:41 pm on March 19, 2017 Permalink | Reply
    Tags: ,   

    Problem: Manasa and Stones 

    Manasa is out on a hike with friends. She finds a trail of stones with numbers on them. She starts following the trail and notices that two consecutive stones have a difference of either a or b. Legend has it that there is a treasure trove at the end of the trail and if Manasa can guess the value of the last stone, the treasure would be hers. Given that the number on the first stone was 0, find all the possible values for the number on the last stone.

    Note: The numbers on the stones are in increasing order.

    Input Format

    The first line contains an integer T, i.e. the number of test cases. T test cases follow; each has 3 lines. The first line contains n (the number of stones). The second line contains a, and the third line contains b.

    Constraints

    1 <= T <= 10
    1 <= n, a, b <= 10^3

    Output Format

    Space-separated list of numbers which are the possible values of the last stone in increasing order.

    Sample Input

    2
    3 
    1
    2
    4
    10
    100
    

    Sample Output

    2 3 4 
    30 120 210 300 
    

    Explanation

    All possible series for the first test case are given below:

    1. 0,1,2
    2. 0,1,3
    3. 0,2,3
    4. 0,2,4

    Hence the answer 2 3 4.

    Series with different number of final steps for second test case are the following:

    1. 0, 10, 20, 30
    2. 0, 10, 20, 120
    3. 0, 10, 110, 120
    4. 0, 10, 110, 210
    5. 0, 100, 110, 120
    6. 0, 100, 110, 210
    7. 0, 100, 200, 210
    8. 0, 100, 200, 300

    Hence the answer 30 120 210 300.

    Approach:

    1. Using backtracking. Generate all possible sequences, get all last values, and put them into a set. This is acceptable with n small (less than 15), since the complexity is O(2^n). Here is the code for backtracking
    2. Analyze. Let’s take 2 examples above and find out the pattern. In the first example, n = 3 and there are 3 different ending values, max value is 4 and the difference from the largest to the smallest is 1 (4 -> 3 -> 2) . In the second example, n = 4 and there are 4 different ending values, max value is 300 and difference between pairs is 90. Have you seen the pattern yet? With n, there are n different values, the largest value is max(a,b)*(n-1), the difference is max(a,b) – min(a,b), or a – b, if a is bigger, otherwise b-a. How can we know that this pattern is the one that we’re looking for. First, since there are only two values a,b, assume a is bigger than b (it works the same way if b is bigger than a). Then the biggest possible value you can get is b*(n-1). since the first one is 0. The second biggest is b*(n-1) – (a-b), since this is the second biggest, the last value is b, instead of a. We c0ntinue this as long as the value return after calculate the difference is positive. And this is actually n-1 times, since we already manually calculate the largest.

    Source code. The chain function is how you print out all possible stones chain, with complexity O(2^n). Inside main is the code to solve this problem.

    def chain(n, arr, options):
        for i in options:
            arr[n] = arr[n-1] + i
            if n == len(arr) - 1:
                print(arr)
            else:
                chain(n+1, arr, options)
    
    def test():
        chain(1, [0]*4, (10, 100))
    
    if __name__ == '__main__':
        t = int(input().strip())
        for _ in range(t):
            n = int(input().strip())
            a = int(input().strip())
            b = int(input().strip())
            if b > a:
                a, b = b, a
            pos_values = [0]*n
            pos_values[0] = a*(n-1)
            for i in range(1, len(pos_values)):
                pos_values[i] = pos_values[i-1] - (a-b)
            pos_values = list(set(pos_values))
            print(*sorted(pos_values))
    
    Advertisements
     
  • loctv 10:50 pm on March 7, 2017 Permalink | Reply
    Tags: ,   

    Problem: Check Mirror in N-ary tree 

    *Difficulty: Medium

    Given two n-ary tree’s the task is to check if they are mirror of each other or not.

    Example

    1                      1
    /    \                 /   \
    2      3             3     2

    Output: 1

    1                        1
    /  \                    /  \
    2    3                2     3

    Output: 0

    Note: you may assume that root of both the given tree as 1.

    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 space separated values n and e denoting the no of nodes and edges respectively. Then in the next line two lines are 2*e space separated values u,v denoting an edge from u to v for the both trees .

    Output:
    For each test case in a new line print 1 if both the trees are mirrors of each other else print 0.

    Constraints:
    1<=T<=20
    1<=n<=15
    1<=e<=20

    Example:
    Input:

    2
    3 2
    1 2 1 3
    1 3 1 2
    3 2
    1 2 1 3
    1 2 1 3
    Output:
    1
    0

    Approach: Since this is a N-arr tree, that means one node can have multiple child. So the easiest way is to consider it as a graph. Each graph has a list of adjacent nodes. The way to to check  if two threes (or graphs if you will) are mirror of each other or not is:

    1. They have the same number of nodes
    2. All node have the same number of adjacent nodes
    3. The child list of each node in the first tree when reversed will be exactly like the one in the node of second tree and vice versa.

    Implementation: Python 3

    def is_mirror(tree_1, tree_2):
        if len(tree_1) != len(tree_2):
            return False
        for node in tree_1:
            if len(tree_1[node]) != len(tree_2[node]):
                return False 
            if tree_1[node] != list(reversed(tree_2[node])):
                return False 
        return True 
    
    def create_tree():
        tree = {}
        arr = list(map(int, input().strip().split()))
        for i in range(0,len(arr),2):
            if arr[i] in tree:
                tree[arr[i]].append(arr[i+1])
            else:
                tree[arr[i]] = [arr[i+1]]
        return tree
    
    if __name__ == '__main__':
        t = int(input().strip())
        for _ in range(t):
            n, e = list(map(int, input().strip().split()))
            tree_1 = create_tree()
            tree_2 = create_tree()
            # print(tree_1)
            # print(tree_2)
            print(1 if is_mirror(tree_1, tree_2) else 0)
    
     
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