Flipping the Matrix

Sean invented a game involving a  matrix where each cell of the matrix contains an integer. He can reverse any of its rows or columns any number of times, and the goal of the game is to maximize the sum of the elements in the  submatrix located in the upper-left corner of the  matrix (i.e., its upper-left quadrant).

Given the initial configurations for  matrices, help Sean reverse the rows and columns of each matrix in the best possible way so that the sum of the elements in the matrix's upper-left quadrant is maximal. For each matrix, print the maximized sum on a new line.

Input Format

The first line contains an integer, , denoting the number of queries. The subsequent lines describe each of the  queries in the following format:

1. The first line of each query contains an integer, .
2. Each line  the  subsequent lines contains  space-separated integers describing the respective values of row  in the matrix.

Output Format

You must print  lines of output. For each query (i.e., matrix), print the maximum possible sum of the elements in the matrix's upper-left quadrant.

Sample Input

1
2
112 42 83 119
56 125 56 49
15 78 101 43
62 98 114 108

Sample Output

414

Explanation

We start out with the following  matrix:

We can perform the following operations to maximize the sum of the  submatrix in the upper-left corner:

1. Reverse column  (), resulting in the matrix: 
   
2. Reverse row  (), resulting in the matrix: 
   

When we sum the values in the  submatrix in the upper-left quadrant, we get . Thus, we print  on a new line.

Solution:

for _ in range(int(input())):

    n = int(input()) 

    n2 = 2 * n

    maxSum = 0

    

    matrix = [0] * n2

    

    for i in range(n2):

        matrix[i] = [int(x) for x in input().strip().split()]

    for i in range(n):

        for j in range(n):

            maxSum += max([matrix[i][j],matrix[i][n2-1-j], matrix[n2-1-i][j],matrix[n2-1-i][n2-1-j]])

                   

    print (maxSum)

Read More

Smallest Substring - All Distinct Letters

A string value S containing only alphabets (both lower and uppercase) is passed as input to the program. The program must print the size of the smallest sub-string which contains all the distinct alphabets in the string S. (lowercase and uppercase characters are treated as two different unique characters)

Input Format:

First line contains S.

Output Format:

First line contains the size of the smallest substring which contains all the distinct characters in the string S.

Example Input/Output 1:

Input:

abcdfffccbbfeaad

Output:

8

Explanation:

The smallest sub string that contains all the distinct letters is cbbfeaad whose length is 8. 

Solution:

s = input()

st = set(s)

a = [0]*len(s)

for i in range(len(s)):

    for j in range (1,len(s)+1):

        x = s[i:j]

        xt = set(x)

        if len(st) == len(xt):

            if len(x)<len(a):

                a = x

print(a)                

print(len(a))

Read More

Add Numbers - Base N

Two numbers X and Y are provided with reference to base N. Add the numbers and print their sum with reference to base 10. 

Input Format: 

First line will contain the value of N. Second line will contain X and Y separated by one or more spaces. 

Output Format: 

First line will contain the sum of X and Y to the base 10. 

Example Input/Output 1: 

Input: 2 1010 11 

Output: 13 

Explanation: 1010 to the base 2 is 10. 11 to the base 2 is 3. Hence the sum is 10+3 = 13.

Solution:

b = int(input())
x = input().split()
print(int(x[0],b)+(int(x[1],b)))

Read More

Next & Previous Immediate Prime Difference

A number N is passed as the input. The program must print the difference between the next immediate prime number and the previous immediate prime number. If the given number N itself is a prime number then print 0 (zero). 

Input Format: 

The first line will contain the value of the number N. 

Output Format: 

The difference between the next immediate prime number and the previous immediate prime number for N. 

Example Input/Output 1: 

Input: 14 

Output: 4 

Explanation: The next immediate prime number is 17. The previous immediate prime number is 13. Hence their difference = 17-13 = 4 is printed as output. 

Solution:

def prim3(n,a):

    x = n

    for i in range(2,int((n/2) + 5)):

        if n%i == 0 and a:

            n -= 1

        elif n%i == 0:

            n += 1

    return 0 if n == x else n

n = int(input())

print(prim3(n,0)-prim3(n,1))

Read More

Longest sub-string with N unique characters

The program must find the length L of the longest sub-string with N unique characters in a given string value S 

Input Format:

The first line will contain the string value S.

The second line will contain the number of unique characters N.

Output Format:

Length L of the sub-string longest sub-string with N unique characters.

Example Input/Output 1: 

Input:

abcdcdabcdef

2

Output:

4

Explanation:

The longest possible substring with 2 unique characters in abcdcdabcdef is cdcd whose length is 4.

Solution:

s = input()

n = int(input())

a = []

for i in range(len(s)):

    for j in range(1,len(s)+1):

        st = s[i:j]

        y = set(st)

        if len(y) == n:

            if len(a) < len(st):

                a = st

print(len(a))

Read More