PBT CODING JULY 8

PROBLEM 1: 

Problem statement

There are n people and two identical voting machines. You are also given an array a[] of size n such that

ai stores time required by i-th person to go to any machine, mark his vote and come back. At one time

instant, only one person can be there on each of the machines. Given a value x, defining the maximum

allowable time for which machines are operational, check whether all persons can cast their vote or

not.

Input Format

First line of input contains n- the number of people. Next line of input contains x- the maximum

allowable time for which machines are operational.Next line contains n integers where ith integer

represents time required by i-th person to go to any machine, mark his vote and come back.

Constraints

1<=n<=100

1<=x<=100

1<=ai<=100

Output Format

Print 'True' (without quotes) if all persons can cast their vote else print 'False'(without quotes).

For example, in first sample test case,

There are n = 3 persons say and maximum allowed time is x = 4 units. Let the persons be P0, P1, and P2

and two machines be M0 and M1. At t0: P0 goes to M0 At t0: P2 goes to M1 At t2: M0 is free, p3 goes to

M0 At t4: both M0 and M1 are free and all 3 have given their vote

Python Solution:

def canVote(a, n, x):

    dp = [[0] * (x + 1) for _ in range(n + 1)]

    a = a[:]

    a.append(0)

    sm = 0

    for i in range(n + 1):

        sm += a[i]

    for i in range(1, n + 1):

        for j in range(1, x + 1):

            if a[i] <= j:

                dp[i][j] = max(dp[i - 1][j], a[i] + 

                               dp[i - 1][j - a[i]])

            else:

                dp[i][j] = dp[i - 1][j]

    return (sm - dp[n][x]) <= x

if __name__ == "__main__":

    n = int(input())

    x = int(input())

    a = list(map(int,input().split()))

    print("True" if canVote(a, n, x) else "False")

PROBLEM 2:

Problem statement

Given a string str of length N, you have to find number of palindromic subsequence (need not

necessarily be distinct) which could be formed from the string str. Note: You have to return the answer

module (10^9)+7;

Input Format

A single line of input contains string 's'.

Constraints

1<=|s|<=1000

Output format

Print the number of palindromic subsequence.

For second sample test case, palindromic subsequence are :"a", "a", "b", "aa"

Python Solution:

def countPs(string):

        n = len(string)

        dp = [[0]*(n) for _ in range(n)]

        mod = 10**9 + 7

        for i in range(n):

            r = 0

            c = i

            while(r < n and c < n):

                if r == c:

                    dp[r][c] = 1

                elif r+1 == c:

                    dp[r][c] = 2

                    if string[r] == string[c]:

                        dp[r][c] += 1

                elif string[r] != string[c]:

                    dp[r][c] = dp[r][c-1] + dp[r+1][c] - dp[r+1][c-1]

                else:

                    dp[r][c] = dp[r][c-1] + dp[r+1][c] + 1

                dp[r][c] = dp[r][c] % mod

                r += 1

                c += 1

        return dp[0][n-1]

print(countPs(input().strip()))

Problem 3:

Problem statement

Given a set of numbers, check whether it can be partitioned into two subsets such that the sum of

elements in both subsets is same or not.

Input Format

First line of input contains 'n'-the size of input. Second libe of input contains n integers elements of

array.

Constraints

1 <= N <= 100

0 <= arri <= 1000

Output Format

Print "YES" if the given set can be partitioned into two subsets such that the sum of elements in both

subsets is equal, else return "NO"

Python Solution:

def isSubsetSum(arr, n, sum):

    if sum == 0:

        return True

    if n == 0 and sum != 0:

        return False

    if arr[n-1] > sum:

        return isSubsetSum(arr, n-1, sum)

    return isSubsetSum(arr, n-1, sum) or isSubsetSum(arr, n-1, sum-arr[n-1])

def findPartion(arr, n):

    sum = 0

    for i in range(0, n):

        sum += arr[i]

    if sum % 2 != 0:

        return False

    return isSubsetSum(arr, n, sum // 2)

n=int(input())

arr = list(map(int,input().split()))

if (findPartion(arr, n) == True):

    print("YES")

else:

    print("NO")