HackerRank Wet Shark and Two Subsequences problem solution

YASH PAL,

In this HackerRank Wet Shark and Two Subsequences problem solution we have given an array X and we need to find all pairs of subsequences (A, B) and we need to determine how many possible subsequences A and B can exist.

Note:

  • Two segments are different if there’s exists at least one index i such that element xi is present in exactly one of them.
  • Both subsequences can overlap each other.
  • Subsequences do not necessarily have to be distinct
hackerrank wet shark and two subsequences problem solution

HackerRank Wet Shark and Two Subsequences problem solution in Python.

#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'twoSubsequences' function below.
#
# The function is expected to return an INTEGER.
# The function accepts following parameters:
#  1. INTEGER_ARRAY x
#  2. INTEGER r
#  3. INTEGER s
#
mod = 10**9+7
def twoSubsequences(x, r, s):
    # Write your code here
    if r<s or (r+s)%2==1 or r==0:
        return 0
    h,l = (r+s)//2, (r-s)//2
    m = len(x)
    dp = [[0 for i in range(m+1)] for j in range(h+1)]
    dp[0][0] = 1
    if x[0]<=h:
        dp[x[0]][1] = 1
    for i in range(1, m):
        for j in range(h,0,-1):
            for k in range(1,m+1):
                if j>=x[i]:
                    dp[j][k] = (dp[j][k]+dp[j-x[i]][k-1]) % mod
    res = 0
    for k in range(1,m+1):
        res  = (res+dp[h][k]*dp[l][k]) % mod
    return res
        
            

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    first_multiple_input = input().rstrip().split()

    m = int(first_multiple_input[0])

    r = int(first_multiple_input[1])

    s = int(first_multiple_input[2])

    x = list(map(int, input().rstrip().split()))

    result = twoSubsequences(x, r, s)

    fptr.write(str(result) + 'n')

    fptr.close()

Wet Shark and Two Subsequences problem solution in Java.

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Solution {

    /*
     * Complete the twoSubsequences function below.
     */
    static int twoSubsequences(int[] X, int r, int s) {
        /*
         * Write your code here.
         */
        final long MOD=1000000007;
        int n = (r + s) / 2, l = (r - s) / 2,m=X.length;
        long result=0;
        long[][] dp=new long[n + 1][m + 1];
        dp[0][0] = 1;
    if(X[0] <= n) {
        dp[X[0]][1] = 1;
    }
    for(int i = 1; i < m; i++) {
        dp[0][0] = 1;
        for(int k = 1; k <= m; k++) {
            dp[0][k] = 0;
        }
        for(int j = n; j >= 1; j--) {
            dp[j][0] = 0;
            for(int k = 1; k <= m; k++) {
                if(j < X[i]) {
                    dp[j][k] = dp[j][k];
                } else {
                    dp[j][k] = (dp[j - X[i]][k - 1] + dp[j][k]) % MOD;
                }
            }
        }
    }
    if(l >= 0 && (r + s) % 2 != 1 && (r - s) % 2 != 1 && r != 0) {
        for(int i = 0; i <= m; i++) {
            result = (result + dp[n][i] * dp[l][i]) % MOD;
        }
    }
    return (int)result;
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        String[] mrs = scanner.nextLine().split(" ");

        int m = Integer.parseInt(mrs[0].trim());

        int r = Integer.parseInt(mrs[1].trim());

        int s = Integer.parseInt(mrs[2].trim());

        int[] x = new int[m];

        String[] xItems = scanner.nextLine().split(" ");

        for (int xItr = 0; xItr < m; xItr++) {
            int xItem = Integer.parseInt(xItems[xItr].trim());
            x[xItr] = xItem;
        }

        int result = twoSubsequences(x, r, s);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedWriter.close();
    }
}

Problem solution in C++.

#include <bits/stdc++.h>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define VAR(v, i) __typeof(i) v=(i)
#define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define all(v) (v).begin(),(v).end()

#define VI vector<int>
#define PII pair<int,int>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define lint long long int

#define debug(x) {cerr <<#x <<" = " <<x <<endl; }
#define debug2(x,y) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y <<endl; } 
#define debug3(x,y,z) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y << ", " << #z << " = " << z <<endl; } 
#define debugv(x) {{cerr <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<endl; }}
#define debugt(t,n) {{cerr <<#t <<" = "; FOR(it,0,(n)) cerr <<t[it] <<", "; cerr <<endl; }}

#define make( x) int (x); scanf("%d",&(x));
#define make2( x, y) int (x), (y); scanf("%d%d",&(x),&(y));
#define make3(x, y, z) int (x), (y), (z); scanf("%d%d%d",&(x),&(y),&(z));
#define make4(x, y, z, t) int (x), (y), (z), (t); scanf("%d%d%d%d",&(x),&(y),&(z),&(t));
#define makev(v,n) VI (v); FOR(i,0,(n)) { make(a); (v).pb(a);} 
#define IOS ios_base::sync_with_stdio(0)
#define HEAP priority_queue

#define read( x) scanf("%d",&(x));
#define read2( x, y) scanf("%d%d",&(x),&(y));
#define read3(x, y, z) scanf("%d%d%d",&(x),&(y),&(z));
#define read4(x, y, z, t) scanf("%d%d%d%d",&(x),&(y),&(z),&(t));
#define readv(v,n) FOR(i,0,(n)) { make(a); (v).pb(a);}

using namespace std;
#define max_n 100005

int mod = 1e9+7;
int dp[2005][105];
int dp2[2005][105];

int main(){
	make3(m,r,s);
	if((r+s)%2!=0){
		makev(v,m);
		printf("0n");
	}
	else{
		makev(v,m);
		int sum = (r+s)/2, diff = (r-s)/2;
		if(diff < 0){
			printf("0n");
			return 0;
		}
		FOR(i,0,sum+1) FOR(j,0,m+1) dp[i][j] = 0;
		dp[0][0] = 1;

		FOR(i,0,m){
			FOR(j,0,sum+1){
				FOR(k,0,m+1){
					dp2[j][k] = dp[j][k] + ((j>=v[i] && k > 0) ? dp[j-v[i]][k-1] : 0);
					dp2[j][k] %= mod;
				}
			}
			FOR(q,0,sum+1) FOR(j,0,m+1)  dp[q][j] = dp2[q][j];
		}
		int ans = 0;
		FOR(i,1,m+1){
			ans += (dp[sum][i]*1LL*dp[diff][i])%mod;
			ans %= mod;
		}
		printf("%dn",ans);
	}
}

Problem solution in C.

#include "stdio.h"
#include "string.h"

int dp[4010][102];
int a[102];
const int MOD = (1e9) + 7;

int main() {
    int m, r, s;
    while (scanf("%d%d%d",&m,&r,&s) != EOF) {
        for (int i = 0 ; i < m ; ++i)
            scanf("%d", &a[i]);
        if (r == 0 && s == 0) {
            printf("0n");
            continue;
        }
        if ((r + s) % 2 == 1 || r < s) {
            printf("0n");
            continue;
        }

        int maxS = (r + s + 1) / 2;
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        for (int i = 0 ; i < m ; ++i) {
            for (int sum = maxS ; sum >= 0 ; --sum) {
                if (sum + a[i] > maxS) continue;
                for (int cnt = 0 ; cnt <= i ; ++cnt) {
                    dp[sum+a[i]][cnt+1] += dp[sum][cnt];
                    dp[sum+a[i]][cnt+1] %= MOD;
                }
            }
        }
        int total = 0;
        for (int cnt = 0 ; cnt <= m ; ++cnt) {
            total += (int)((long long)dp[(r+s)/2][cnt] * dp[(r-s)/2][cnt] % MOD);
            total %= MOD;
        }
        printf("%dn",total);
    }
    return 0;
}

Algorithms coding problems solutions