Tagged: Problem Solving Toggle Comment Threads | Keyboard Shortcuts

  • loctv 3:28 pm on February 20, 2017 Permalink | Reply
    Tags: Problem Solving,   

    Problem: Making Anagrams 

    *Difficulty: Easy

    Problem:

    ctci-making-anagrams-english

    Approach: To be able to make anagrams from two string, we have to find their common characters first. For example, if we have abccd and cdcc, then their common characters is c and d. Then we build two string contains only character that is in both string a and string b. In the previous example, string a = ccd and string b = cdcc. The last thing we need to do is make them anagrams. We do that by iterating through either string a or string b, with each character d, if there are more d in string a than string b, we remove d from a to make the number of d equal in both a and b. In our example, string b will remove 1 ‘c’, then a = ccd and b = dcc. Notice that we don’t have to do this on string, we rather do this on dictionary of string. Since the input only contains lower English alphabet, the maximum size of the dictionary will contain only 26 keys and 26 corresponding values. If key ‘c’ in a has higher value than key ‘c’ in b, then set its value to ‘c’ in b.

    Implementation: Python 2.7

    from collections import Counter
    
    def make_anagrams(a, b):
        a_set = set(list(a))
        b_set = set(list(b))
        a_counter = Counter()
        b_counter = Counter()
        # get char in common 
        for c in a:
            if c in b_set:
                a_counter[c] += 1
        for c in b:
            if c in a_set:
                b_counter[c] += 1
        # make anagrams 
        for key in a_counter.keys():
            a_val = a_counter.get(key)
            b_val = b_counter.get(key)
            if a_val > b_val:
                a_counter[key] = b_val
            else:
                b_counter[key] = a_val
        # calculate removed char
        a_lost = len(a) - sum([a_counter.get(x) for x in a_counter.keys()])
        b_lost = len(b) - sum([b_counter.get(x) for x in b_counter.keys()])
        return a_lost + b_lost
    
    if __name__ == '__main__':
        a = input().strip()
        b = input().strip()
        print(make_anagrams(a, b))
    
     
  • loctv 10:25 pm on February 19, 2017 Permalink | Reply
    Tags: Problem Solving,   

    Problem: Arrays Left Rotation 

    • Difficulty: Easy

    Problem description:
    Array Left Rotation pdf

    All approaching ideas is inspired by Python.
    Approach: The first thing come in my mind is using a for loop, using Python list slice notation. But it’s too expensive both in computing muscle and memory usage. With the constraints, it will get TLE. Another approach is using modular arithmetic. Basically, rotate array d times means that we start iterating at index d. We have to use modular arithmetic to wrap around the array in case of reaching the end of array but still haven’t iterated through all elements yet.

    Implementation: Python 3

    def rotate(arr, d):
        count = 0
        start = d % len(arr)
        while count < len(arr):
            print(arr[start], end=' ')
            count += 1
            start = (start + 1) % len(arr)
        print()
    
    if __name__ == '__main__':
        n, d = list(map(int, input().strip().split()))
        arr = list(map(int, input().strip().split()))
        rotate(arr, d)
    
     
  • loctv 8:54 am on February 13, 2017 Permalink | Reply
    Tags: Problem Solving,   

    Problem: Word Boggle 

    *Difficulty: Medium

    Given a dictionary, a method to do lookup in dictionary and a M x N board where every cell has one character. Find all possible words that can be formed by a sequence of adjacent characters. Note that we can move to any of 8 adjacent characters, but a word should not have multiple instances of same cell.

    Example:

    Input: dictionary[] = {"GEEKS", "FOR", "QUIZ", "GO"};
           boggle[][]   = {{'G','I','Z'},
                           {'U','E','K'},
                           {'Q','S','E'}};
    
    Output:  Following words of dictionary are present
             GEEKS, QUIZ
    
    

    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 an integer x denoting the no of words in the dictionary. Then in the next line are x space separated strings denoting the contents of the dictinory. In the next line are two integers N and M denoting the size of the boggle. The last line of each test case contains NxM space separated values of the boggle.

    Output:
    For each test case in a new line print the space separated sorted distinct words of the dictionary which could be formed from the boggle. If no word can be formed print -1.

    Constraints:
    1<=T<=10
    1<=x<=10
    1<=n,m<=7

    Example:
    Input:

    1
    4
    GEEKS FOR QUIZ GO
    3 3
    G I Z U E K Q S E

    Output:
    GEEKS QUIZ

    *Approach: This problem is almost the same with this.
    The mechanism gonna be used here is back tracking. There are only two main parts in the algorithm:

    • With each cell in boggle matrix (two for loops)
      • Check all possible words that can be generated with that cell
      • While generating, if a generated word can be found in dictionary, add to result
      • if the length of generated word equal the length of longest word in dictionary, return (base case)
    • After getting all words, put them into a set to eliminate duplicate words, then sorted them alphabetically before output

    Suppose max_level is the length of longest word in dictionary, as soon as the length of a generated word exceeds max_level, we return. Why? Because if we still continue generating, there is no word will match anything in dictionary.

    Implementation: Python 2.7

    from __future__ import print_function
    
    def generate_words(x, y, dictionary, boggle, visited_cells, level, max_level, result, word):
    	visited_cells.append((x, y))
    	word += boggle[x][y]
    	#print word
    	if word in dictionary:
    		result.append(word)
    	eight_directions = ((x+1, y), (x-1, y), (x, y+1), (x, y-1),
    						(x+1, y+1), (x+1, y-1), (x-1, y+1), (x-1, y-1))
    	eight_directions = [(new_x,new_y) for new_x,new_y in eight_directions 
    		if in_bound(new_x, new_y, boggle) and (new_x, new_y) not in visited_cells]
    	if level > max_level:
    		return
    	for new_x, new_y in eight_directions:
    		generate_words(new_x, new_y, dictionary, boggle, 
    			visited_cells, level+1, max_level, result, word)
    		visited_cells.pop()
    
    def find_all_possible_words(dictionary, boggle):
    	max_level = get_max_level(dictionary)
    	overall_result = []
    	for x in xrange(len(boggle)):
    		for y in xrange(len(boggle[x])):		
    			result = []
    			visited_cells = []
    			level = 0
    			word = ""
    			generate_words(x, y, dictionary, boggle, visited_cells, level, max_level, result, word)
    			if result:
    				overall_result.extend(result)
    	overall_result = set(overall_result)
    	overall_result = list(sorted(overall_result))
    	if overall_result:
    	    print(*overall_result, sep=" ")
    	else:
    	    print(-1)
    
    def get_max_level(dictionary):
    	return max(len(x) for x in dictionary)
    
    def in_bound(x, y, boggle):
    	return (x >= 0 and x < len(boggle)) and (y >= 0 and y < (len(boggle[0])))
    
    if __name__ == '__main__':
    	t = input()
    	for _ in range(t):
    		n = input()
    		dictionary = raw_input().strip().split()
    		n, m = map(int, raw_input().strip().split())
    		boggle = []
    		temp = raw_input().strip().split()
    		for i in range(0, len(temp), m):
    			boggle.append(temp[i:i+m])
    		#print(dictionary)
    		#print(boggle)
    		find_all_possible_words(dictionary, boggle)
    

     

     

     
  • loctv 9:56 pm on February 6, 2017 Permalink | Reply
    Tags: Problem Solving,   

    Problem: Longest K unique characters substring 

    *Difficulty: easy

    Given a string you need to print the size of the longest possible substring that has exactly k unique characters. If there is no possible substring print -1.
    Example
    For the string aabacbebebe and k = 3 the substring will be cbebebe with length 7.
    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 string s and the next line conatains an integer k.

    Output:
    For each test case in a new line print the required output.

    Constraints:
    1<=T<=100
    1<=k<=10

    Example:
    Input:

    2
    aabacbebebe
    3
    aaaa
    1
    Output:
    7
    4

    Implementation: Python 2.7

    #code
    def all_sub_string(k, string, all_substr):
        if k > len(string):
            return 
        elif k == len(string):
            all_substr.append(string)
            return
        else:
            for i in range(len(string)):
                if i + k > len(string):
                    break
                all_substr.append(string[i:i+k])
            all_sub_string(k+1, string, all_substr)
    
    def longest_k_unique_char_substr(all_substr, k):
        if k > len(all_substr[-1]):
            return -1
        max_length = -1
        for substr in all_substr:
            if len(substr) >= k and len(set(substr)) == k:
                if len(substr) > max_length:
                    max_length = len(substr)
        return max_length
                
    
    def main():
        t = input()
        for _ in xrange(t):
            string = raw_input().strip()
            k = input()
            all_substr = []
            all_sub_string(1, string, all_substr)
            print longest_k_unique_char_substr(all_substr, k)
    
    if __name__ == '__main__':
        main()
    
     
  • loctv 9:33 pm on February 4, 2017 Permalink | Reply
    Tags: Problem Solving,   

    Problem: Kth Prime factor of a Number 

    • Difficulty: Easy

    Given two numbers n and k, print Kth prime factor among all prime factors of n.

    Note: if k > all the count of prime factor of n, then print -1

    Input:

    The first line of input contains an integer denoting the no of test cases. Then T test cases follow. Each test case contains two space seperated integers n and k respectively.
    Output:

    For each test case ouput a simple line containing a single integer denoting kth prime factor of n.
    Constraints:

    1<=T<=100
    0<=N<=104
    1<=K<=50
    Example:

    Input:

    2
    225 2
    81 5

    Ouput:

    3
    -1

    Explanation:

    Test Case 1:  n=225 and k=2

    Prime factor of 225 are: 3,3,5,5

    Kth prime factor is 3

    Test Case 2: n=81 and k=5

    Prime factor of 81 is 3,3,3,3

    since k is greater than all the count of prime factor, hence we print -1

    Approach: This is not the fastest solution, but it’s fairly fast. Enough to paste the biggest test case in less than 100 ms. Using sieve of Eratosthenes to generate first 10000 primes, then use it as a dictionary to find all prime factors of a number. There are multiple ways to solve this problem, since the constraints is not big, so this solution is not only simple but fast.

    Implementation: Python 2.7

    #code
    import math
    def sieveOfEratosthenes(n):
        sieve = [True]*(n+1)
        sieve[0] = sieve[1] = False
        for i in range(2, int(math.sqrt(n))):
            if sieve[i]:
                for j in range(i+i, len(sieve), i):
                    sieve[j] = False
        return [i for i in range(len(sieve)) if sieve[i]]
    
    def primeFactors(number, primes):
        factors, i = [], 0
        while number > 1:
            if number % primes[i] == 0:
                factors.append(primes[i])
                number /= primes[i]
            else:
                i += 1
        return factors
    
    def main():
        t = input()
        primes = sieveOfEratosthenes(10000)
        for _ in range(t):
            number, k = map(int, raw_input().strip().split())
            factors = primeFactors(number, primes)
            print -1 if k > len(factors) else factors[k-1]
            
    if __name__ == '__main__':
        main()
    
     
  • loctv 9:04 pm on February 3, 2017 Permalink | Reply
    Tags: Problem Solving,   

    Problem: A or B 

    *Difficulty: Medium
    Consider four numbers: A, B, C, and K. You must change at most K bits in A and B to form the numbers A’ and B’ satisfying the equation A’ | B’ = C. Here, the | symbol denotes the bitwise OR operation.

    Given Q sets of the numbers defined above, find and print the respective values of A’ and B’ on new lines; if no such value exists, print -1 instead. If there are multiple solutions, make A’ as small as possible; if there are still multiple solutions, make B’ as small as possible.

    Notes:

    • A, B and C are given in Hexadecimal (base 16), and K is given in decimal (base 10).
    • If the number of bits changed in A is kA and the number of bits changed in B is kB , then kA + kB must be <= K.

    Input Format

    The first line contains an integer, Q , denoting the number of queries. The subsequent lines describe each respective query as follows:

    • The first line contains a single integer denoting the value of K.
    • Each of the next 3 lines contains a Hexadecimal (base 16) number describing the respective values of A, B, and C.

    Constraints

     screenshot-from-2017-02-03-20-49-42

    Output Format

    Print two lines of output for each query:

    1. The first line should contain a Hexadecimal (base 16) number denoting the value of A’ .
    2. The second line must contain a Hexadecimal (base 16) number denoting the value of B’.

    If no valid answer exists, you must instead print one line of output with the integer -1.

    Note: The letters in Hexadecimal numbers must be in uppercase.

    Sample Input

    3
    8
    2B
    9F
    58
    5
    B9
    40
    5A
    2
    91
    BE
    A8
    

    Sample Output

    8
    58
    18
    42
    -1
    

    Explanation

    Query 0:
    In this query, K = 8.
    Change to A = 2B(16) to A’ = 8(16). 3 bits are changed.

    Change B = 9F(16) to B’= 58(16) . 5 bits are changed.

    Query 1:
    In this query, K = 5.
    Change A = B9(16) to A’ = 18(16). 3 bits are changed.
    Change B = 40(16) to B’ = 42(16). Only 1 bit is changed.

    Query 2:
    There is no valid answer, so we print -1.

    Approach:

    There are two parts of the solution. The first is the one that I figured out, but I sucked at the second part.
    Let’s me explain. The solution complexity is O(n).
    Part 1: Convert A,B,C to binary, and equalize their length (calculate max length, then append 0 before the ones that are shorter). Traverse through each bit in C.
    If C[i] == 0:
    + if A[i] = 1 => A[i] = 0, reduce K by 1
    + if B[i] = 1 => B[i] = 0, reduce K by 1
    If C[i] == 1:
    + if A[i] == 0 and B[i] == 0 => B[i] = 1, reduce K by 1
    While iterating through C, if K == 0 but still not A’ | B’ = C, then return -1
    Note: in case C[i] == 1, we let B[i] = 1 since we want to minimize A first.

    Part 2: Since not fully understood the description of the problem (my bad English), I had to see the tutorial, which then made me surprised. The second part when we minimize even further A. If K still bigger than 0.
    i -> 0
    while K > 0:
    if C == [1]: # since if C[i] == 0 we cant change anything
    + if A[i] == 1 and B[i] == 1 => A[i] = 0 #minimize A, reduce K by 1
    + if A[i] == 1 and B[i] == 0 => A[i] = 0 and B[i] = 1, reduce K by 2

    That’s it. How silly I am 😦

    Implementation: Python 2.7

    def figureOut(A, B, C, K):
        # convert from base 16 to base 10
        # in binary format
        A = bin(int(A, 16))[2:]
        B = bin(int(B, 16))[2:]
        C = bin(int(C, 16))[2:]
        maxLength = max(len(A), len(B), len(C))
    
        #equalize A,B,C length
        if len(A) < maxLength:
            A = '0'*(maxLength-len(A)) + A
        if len(B) < maxLength:
            B = '0'*(maxLength-len(B)) + B
        if len(C) < maxLength:
            C = '0'*(maxLength-len(C)) + C
        A, B, C = list(A), list(B), list(C)
    
        # 1. found result
        result = []
        for i in range(len(C)):
            if C[i] == '0':
                if A[i] == '1':
                    A[i] = '0'
                    K -= 1
                if B[i] == '1':
                    B[i] = '0'
                    K -=1
            elif C[i] == '1':
                if A[i] == '0' and B[i] == '0':
                    B[i] = '1'
                    K -= 1
            # not found, return -1
            if K < 0:
                return -1
        
        # found result,
        # minimize A
        i = 0
        while K > 0:
            if C[i] == '1':
                if A[i] == '1' and B[i] == '1':
                    A[i] = '0'
                    K -= 1
                elif A[i] == '1' and B[i] == '0':
                    if K > 1:
                        A[i] = '0'
                        B[i] = '1'
                        K -= 2
                    
            i += 1
            if i == len(C):
                break
    
        return '{:X}'.format(int(''.join(A), 2)), '{:X}'.format(int(''.join(B), 2))
        
    
    def main():
        t = input()
        for _ in range(t):
            K = input()
            A = raw_input().strip()
            B = raw_input().strip()
            C = raw_input().strip()
            
            result = figureOut(A, B, C, K)
            if result != -1:
                print result[0]
                print result[1]
            else:
                print -1
    
    if __name__ == '__main__':
        main()
    
     
  • loctv 10:09 pm on February 2, 2017 Permalink | Reply
    Tags: Problem Solving,   

    Problem: Find all four sum numbers 

    *Difficulty: Medium

    Given an array A of size N, find all combination of four elements in the array whose sum is equal to a given value K. For example, if the given array is {10, 2, 3, 4, 5, 9, 7, 8} and K = 23, one of the quadruple is “3 5 7 8” (3 + 5 + 7 + 8 = 23).

    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 input contains two integers N and K. Then in the next line are N space separated values of the array.

    Output:
    For each test case in a new line print all the quadruples present in the array separated by space which sums up to value of K. Each quadruple is unique which are separated by a delimeter “$” and are in increasing order.

    Constraints:
    1<=T<=100
    1<=N<=100
    -1000<=K<=1000
    -100<=A[]<=100

    Example:
    Input:

    2
    5 3
    0 0 2 1 1
    7 23
    10 2 3 4 5 7 8
    Output:
    0 0 1 2 $
    2 3 8 10 $2 4 7 10 $3 5 7 8 $

    Approach:
    Using itertools in Python, I can easily quickly generate all combination-length-four of an arr.

    #code
    from __future__ import print_function
    import itertools
    
    def allFourSumNumber(arr, K):
        result = []
        for four in itertools.combinations(arr, 4):
            if sum(four) == K:
                if four not in result:
                    result.append(four)
        return result
    
    def main():
        t = input()
        for _ in range(t):
            n, K = map(int, raw_input().strip().split())
            arr = map(int, raw_input().strip().split())
            found = False
            for four in allFourSumNumber(sorted(arr), K):
                found = True
                print(four[0], four[1], four[2], four[3], '$', end='')
            print(-1 if not found else '')
    
    if __name__ == '__main__':
        main()
    

    “Life is short, why haven’t you learned Python yet?”

     
  • loctv 11:43 pm on January 31, 2017 Permalink | Reply
    Tags: Problem Solving,   

    Problem: Partition a number into two divisible parts 

    *Difficulty: Easy
    Given a number (as string) and two integers a and b, divide the string in two non-empty parts such that the first part is divisible by a and second part is divisible by b. If string can not be divided into two non-empty parts, output “-1”, else print the two parts.

    Input:

    The first line of input contains a single integer T denoting the number of test cases. Then T test cases follow. Each test case consists of single line containing 3 space seperated number denoting the respective values of  n, a and b.
    Output:

    For each test case output a single line containing the two space seperated non-empty parts else print -1.
    Constraints:

    1<=T<=100

    1<=N<=106

    1<=a,b<=N
    Example:

    Input:

    3
    1200 4 3
    123 12 3
    125 12 5

    Ouput:

    12 00
    12 3
    -1

    Approach:
    With Python in my pocket, I don’t think this problem deserves a medium-hard rank. The constraints is not hard, 10^6 means the length of the longest input number is just 6. The only thing to keep in mind is alway think of exceptions. Exceptions here are two case, number with length 1 and 2.

    Implementation: Python2.7

    #code
    def partitionToTwoPart(number, a, b):
        number = str(number)
        if len(number) < 2:
            return -1
        elif len(number) == 2:
            first, second = number[0], number[1]
            if int(first) % a == 0 and int(second) % b == 0:
                return first, second
            else:
                return -1
        else:
            for i in range(1, len(number)):
                first, second = number[:i], number[i:]
                if int(first) % a == 0 and int(second) % b == 0:
                    return first, second
            else:
                return -1
    
    def main():
        t = input()
        for _ in range(t):
            n, a, b = map(int, raw_input().strip().split())
            result = partitionToTwoPart(n, a, b)
            if result != -1:
                print result[0], result[1]
            else:
                print -1
    if __name__ == '__main__':
        main()
    
     
  • loctv 5:49 pm on January 30, 2017 Permalink | Reply
    Tags: Problem Solving,   

    Problem: Replace O’s with X’s 

    *Difficulty: Medium
    Given a matrix of size NxM where every element is either ‘O’ or ‘X’, replace ‘O’ with ‘X’ if surrounded by ‘X’. A ‘O’ (or a set of ‘O’) is considered to be by surrounded by ‘X’ if there are ‘X’ at locations just below, just above, just left and just right of it.

    Examples:

    Input: mat[N][M] =  {{'X', 'O', 'X', 'X', 'X', 'X'},
                         {'X', 'O', 'X', 'X', 'O', 'X'},
                         {'X', 'X', 'X', 'O', 'O', 'X'},
                         {'O', 'X', 'X', 'X', 'X', 'X'},
                         {'X', 'X', 'X', 'O', 'X', 'O'},
                         {'O', 'O', 'X', 'O', 'O', 'O'},
                        };
    Output: mat[N][M] =  {{'X', 'O', 'X', 'X', 'X', 'X'},
                          {'X', 'O', 'X', 'X', 'X', 'X'},
                          {'X', 'X', 'X', 'X', 'X', 'X'},
                          {'O', 'X', 'X', 'X', 'X', 'X'},
                          {'X', 'X', 'X', 'O', 'X', 'O'},
                          {'O', 'O', 'X', 'O', 'O', 'O'},
                        };
    
    
    Input: mat[N][M] =  {{'X', 'X', 'X', 'X'}
                         {'X', 'O', 'X', 'X'}
                         {'X', 'O', 'O', 'X'}
                         {'X', 'O', 'X', 'X'}
                         {'X', 'X', 'O', 'O'}
                        };
    Input: mat[N][M] =  {{'X', 'X', 'X', 'X'}
                         {'X', 'X', 'X', 'X'}
                         {'X', 'X', 'X', 'X'}
                         {'X', 'X', 'X', 'X'}
                         {'X', 'X', 'O', 'O'}
                        };

    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.

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

    Constraints:
    1<=T<=10
    1<=mat[][]<=100
    1<=n,m<=20

    Example:
    Input:

    2
    1 5
    X O X O X
    3 3
    X X X X O X X X X
    Output:
    X O X O X
    X X X X X X X X X

    Approach:
    The problem’s description is not clear enough. Just imagine that you’re playing Go, O is black and X is white, if a territory of black is surrounded by white, then all cells in that territory are replaced by white.
    Problem’s difficulty is medium because the code is pretty long (I suppose)

    Algorithm:
    1. Get all O groups
    2. From those groups, get groups that are surrounded by X
    3. Replace O groups by X
    Simple, isn’t it?

    Implementation: Python 2.7

    def getAllOGroups(matrix):
        markedO, groups = [], []
        for i in range(len(matrix)):
            for j in range(len(matrix[i])):
                if not (i, j) in markedO and matrix[i][j] == 'O':
                    tempGroup = []
                    #get all adjacent O
                    getAllAdjacentOFrom(i, j, matrix, tempGroup, markedO)
                    groups.append(tempGroup)
        return groups
    
    def getAllAdjacentOFrom(i, j, matrix, tempGroup, markedO):
        tempGroup.append((i, j))
        markedO.append((i, j))
        #up
        i_up, j_up = i-1, j
        if isInBound(i_up, j_up, matrix) and (i_up, j_up) not in markedO and matrix[i_up][j_up] == 'O':
            getAllAdjacentOFrom(i_up, j_up, matrix, tempGroup, markedO)
        #down
        i_down, j_down = i+1, j
        if isInBound(i_down, j_down, matrix) and (i_down, j_down) not in markedO and matrix[i_down][j_down] == 'O':
            getAllAdjacentOFrom(i_down, j_down, matrix, tempGroup, markedO)
        #left
        i_left, j_left = i, j-1
        if isInBound(i_left, j_left, matrix) and (i_left, j_left) not in markedO and matrix[i_left][j_left] == 'O':
            getAllAdjacentOFrom(i_left, j_left, matrix, tempGroup, markedO)
        #right
        i_right, j_right = i, j+1
        if isInBound(i_right, j_right, matrix) and (i_right, j_right) not in markedO and matrix[i_right][j_right] == 'O':
            getAllAdjacentOFrom(i_right, j_right, matrix, tempGroup, markedO)
    
    def getGroupsSurroundedByX(groups, matrix):
        surroundedGroups = []
        for groupO in groups:
            if len([(i, j) for (i,j) in groupO if isSurroundedByX(i, j, matrix)]) == len(groupO):
                surroundedGroups.append(groupO)
        return surroundedGroups
    
    def isSurroundedByX(i, j, matrix):
        xUp = False
        for _ in range(i-1, -1, -1):
            if matrix[_][j] == 'X':
                xUp = True
                break
        xDown = False
        for _ in range(i+1, len(matrix)):
            if matrix[_][j] == 'X':
                xDown = True
                break
        xLeft = False
        for _ in range(j-1, -1, -1):
            if matrix[i][_] == 'X':
                xLeft = True
                break
        xRight = False
        for _ in range(j+1, len(matrix[0])):
            if matrix[i][_] == 'X':
                xRight = True
                break
        return xUp == xDown == xLeft == xRight == True
    
    def isInBound(i, j, matrix):
        return i >= 0 and i < len(matrix) and j >= 0 and j < len(matrix[0])
    
    def replaceOByX(surroundedGroups, matrix):
        for group in surroundedGroups:
            for (i, j) in group:
                matrix[i][j] = 'X'
    
    def printFormated(matrix):
        for row in matrix:
            for cell in row:
                print cell,
        print
    
    def main():
        t = input()
        for _ in range(t):
            n, m = map(int, raw_input().strip().split())
            arr = raw_input().strip().split()
            matrix = [arr[i:i+m] for i in range(0, len(arr), m)]
            #get all O-groups
            groups = getAllOGroups(matrix)
            #get groups that are surrounded by X
            surroundedGroups = getGroupsSurroundedByX(groups, matrix)
            #replace O with X
            replaceOByX(surroundedGroups, matrix)
            printFormated(matrix)
            
            
    if __name__ == '__main__':
        main()
    
    
     
  • loctv 8:14 pm on January 29, 2017 Permalink | Reply
    Tags: Problem Solving,   

    Problem: Help a Thief!!! 

    *Difficulty: Basic

    You have to help a thief to steal as many as GoldCoins as possible from a GoldMine. There he saw N Gold Boxes an each Gold Boxes consists of Ai Plates each plates consists of Aj Gold Coins, Each Box consist of plates with exactly same number of GoldCoins per plate. Your task is to print the maximum gold coins theif can steal.

    Input:
    First line consists of T test cases. Each test case consists of three lines.
    First line of each test case consistss of an Integer nT denoting the number of plates theif can steal.
    Second line of each test case consists of an Integer N denoting the number of Gold Boxes available in the gold mine.
    Third line of each test case consists of 2*N spaced Integers Ai,Aj dentoning number of plates in each box and number of gold coins in each plates respectively.

    Output:
    Print the respective result in each line.

    Constraints:
    1<=T<=20
    1<=nT,Ai<=20
    1<=N<=20
    1<=Aj<=100

    Example:
    Input:

    1
    3
    3
    1 3 2 2 3 1
    Output:
    7

    Implementation: Python 2.7

    #code
    def sortByGoldCoins(goldBoxes):
        return sorted(goldBoxes, key=lambda goldBox: goldBox[1], reverse=True)
    
    def helpThief(goldBoxes, platesCanSteal):
        maxGoldCoins, i = 0, 0
        while platesCanSteal > 0:
            if platesCanSteal >= goldBoxes[i][0]:
                maxGoldCoins += goldBoxes[i][1] * goldBoxes[i][0]
                platesCanSteal -= goldBoxes[i][0]
                i += 1
            else:
                maxGoldCoins += platesCanSteal * goldBoxes[i][0]
                platesCanSteal = 0
        return maxGoldCoins
    
    def main():
        t = input()
        for _ in range(t):
            nT = input()
            N = input()
            goldBoxes = map(int, raw_input().strip().split())
            plates = [goldBoxes[i] for i in range(len(goldBoxes)) if i % 2 == 0]
            goldCoins = [goldBoxes[i] for i in range(len(goldBoxes)) if i % 2 != 0]
            goldBoxes = zip(plates, goldCoins)
            goldBoxes = sortByGoldCoins(goldBoxes)
            #print goldBoxes
            print helpThief(goldBoxes, nT)
    
    if __name__ == '__main__':
        main()
    

     

     
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