Updates from January, 2017 Toggle Comment Threads | Keyboard Shortcuts

  • loctv 11:38 pm on January 22, 2017 Permalink | Reply
    Tags: ,   

    Problem: Count Pairs in an Array 

    Given an array of integers arr[0..n-1], count all pairs (arr[i], arr[j]) in the such that i*arr[i] > j*arr[j], 0 =< i < j j*arr[j] are
    (10, 2) (10, 4) (10, 1) (2, 1) (4, 1)
    Input:

    The first line of input contains T denoting the no. of test cases . Then T test cases follow . The first line of each test case contains an Integer N and the next line contains N space separated values of the array A[ ] .

    Output:

    For each test case output the required result in a new line.

    Constraints:

    1<=T<=100
    1<=N<=100
    1<=A[ ] <=1000

    Example:

    Input:
    2
    7
    5 0 10 2 4 1 6
    4
    8 4 2 1
    Output:
    5
    2

    import itertools
    def count_pairs(arr):
        """
            counting all pairs in arr such that 
            i*arr[i] > j*arr[j] and j > i
            arr: a list of tuple - [(index, value),...]
        """
        # get all pairs
        all_pairs = list(itertools.combinations(arr, 2))
        # check all pairs for the condition
        count_pairs = 0
        for pair in all_pairs:
            i, j, arr_i, arr_j = pair[0][0], pair[1][0], pair[0][1], pair[1][1]
            if i*arr_i > j*arr_j and j > i:
                count_pairs += 1
        return count_pairs
    
    if __name__ == '__main__':
        t = input()
        for _ in range(t):
            n = input()
            arr = map(int, raw_input().strip().split())
            arr = [(i,arr_i) for (i, arr_i) in enumerate(arr)]
            print count_pairs(arr)
    

    **'Life is short, why haven't you learned python yet?'

    Advertisements
     
  • loctv 11:06 pm on January 22, 2017 Permalink | Reply
    Tags: ,   

    Problem: 

    Given a pattern string and a test string, Your task is to implement RegEx substring matching. If the pattern is preceded by a ^, the pattern(excluding the ^) will be matched with the starting position of the text string. Similarly, if it is preceded by a $, the pattern(excluding the ^) will be matched with the ending position of the text string. If no such markers are present, it will be checked whether pattern is a substring of test.

    Example :

    ^coal
    coaltar
    Result : 1
    tar$
    coaltar
    Result : 1
    rat
    algorate
    Result: 1
    abcd
    efgh
    Result :0
    Input: The first line of input contains an integer T denoting the no of test cases . Then T test cases follow. Each test case contains two lines. The first line of each test case contains a pattern string. The second line of each test case consists of a text string.

    Output: Corresponding to every test case, print 1 or 0 in a new line.

    Constrains:
    1<=T<=100
    1<=length of the string<=1000

    Hint: Choosing the right language will probably help.

    Implementation: Python 2.7

    #code
    def regx_matching(pattern, string):
        if pattern.startswith('^'):
            return string.startswith(pattern[1:]) 
        elif pattern.endswith('$'):
            return string.endswith(pattern[:-1])
        else:
            return pattern in string
    
    if __name__ == '__main__':
        t = input()
        for _ in range(t):
            pattern = raw_input().strip()
            string = raw_input().strip()
            print 1 if regx_matching(pattern, string) 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