HackerRank Wet Shark and Two Subsequences

In this post, we will solve HackerRank Wet Shark and Two Subsequences Problem Solution.

Note:

Two segments are different if there’s exists at least one index such that element is present in exactly one of them.
Both subsequences can overlap each other.
Subsequences do not necessarily have to be distinct

Input Format
The first line consists of 3 space-separated integers m. r. s. where m denotes the length of the original array, X, and r and s are as defined above.
The next line contains m space-separated integers. 1, 2,…, m. representing the elements of X.

Output Format
Output total number of pairs of subsequences, (A, B), satisfying the above conditions. As the number can be large, output it’s modulo 109+7= 1000000007

Sample Input 0

4 5 3
1 1 1 4

Sample Output 0

HackerRank Wet Shark and Two Subsequences Problem Solution

Wet Shark and Two Subsequences C Solution

#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("0\n");
            continue;
        }
        if ((r + s) % 2 == 1 || r < s) {
            printf("0\n");
            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("%d\n",total);
    }
    return 0;
}

Wet Shark and Two Subsequences C++ Solution

#include <cstdio>
#include <cstring>

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("0\n");
			continue;
		}
		if ((r + s) % 2 == 1 || r < s) {
			printf("0\n");
			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("%d\n", total);
	}
	return 0;
}

Wet Shark and Two Subsequences C Sharp Solution

using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;

class Result
{

    /*
     * 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
     */

    public static int twoSubsequences(List<int> x, int r, int s)
    {        
        long MOD=1000000007;     
        int n = (r + s)/2;
        int l = (r - s) / 2; 
        
        long total = 0;    
        long[,] dp = new long[n + 1 , x.Count + 1];
        dp[0,0] = 1;
        
        if (x[0] <= n){
            dp[x[0], 1] = 1;            
        }
        
        for (int i = 1; i < x.Count; i++){
            dp[0,0] = 1; 
            
            for (int k = 1; k <= x.Count; k++){
                dp[0,k] = 0;
            }
            
            for(int j = n; j >= 1; j--) {
                dp[j,0] = 0;
                
                for(int k = 1; k <= x.Count; 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 <= x.Count; i++) {
                total = (total + dp[n,i] * dp[l,i]) % MOD;
            }
        }

        return Convert.ToInt32(total);
    }

}

class Solution
{
    public static void Main(string[] args)
    {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        string[] firstMultipleInput = Console.ReadLine().TrimEnd().Split(' ');

        int m = Convert.ToInt32(firstMultipleInput[0]);

        int r = Convert.ToInt32(firstMultipleInput[1]);

        int s = Convert.ToInt32(firstMultipleInput[2]);

        List<int> x = Console.ReadLine().TrimEnd().Split(' ').ToList().Select(xTemp => Convert.ToInt32(xTemp)).ToList();

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

        textWriter.WriteLine(result);

        textWriter.Flush();
        textWriter.Close();
    }
}

Wet Shark and Two Subsequences Java Solution

import java.io.*;
import java.util.*;

public class Solution {
  private static InputReader in;
  private static PrintWriter out;
  public static int mod = 1000000007;

  public static void main(String[] args) throws IOException {
    in = new InputReader(System.in);
    out = new PrintWriter(System.out, true);
    
    int M = in.nextInt();
    int R = in.nextInt();
    int S = in.nextInt();
    if ((R+S) % 2 != 0 || S >= R) {
      out.println("0");
      out.close();
      System.exit(0);
    }
    
    int P = (R+S)/2, Q = (R-S)/2;
    
    long[][] nways = new long[M+1][P+1];
    nways[0][0] = 1;
    for (int i = 1; i <= M; i++) {
      int x = in.nextInt();
      for (int j = M; j >= 1; j--) {
        for (int k = P; k >= x; k--) {
          nways[j][k] += nways[j-1][k-x];
          if (nways[j][k] >= mod) nways[j][k] -= mod;
        }
      }
    }
    
    long total = 0;
    for (int i = 0; i <= M; i++) {
      total = (total + nways[i][P] * nways[i][Q]) % mod;
    }
    out.println(total);
    out.close();
    System.exit(0);
    
  }

  static class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
      reader = new BufferedReader(new InputStreamReader(stream), 32768);
      tokenizer = null;
    }

    public String next() {
      while (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          tokenizer = new StringTokenizer(reader.readLine());
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }
      return tokenizer.nextToken();
    }

    public int nextInt() {
      return Integer.parseInt(next());
    }
  }


}

Wet Shark and Two Subsequences JavaScript Solution

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.trim().split('\n').map(str => str.trim());

    main();
});

function readLine() {
    return inputString[currentLine++];
}

// Based on [the idea and sample code] from Discussion
function twoSubsequences(x, r, s) {
  const ARRAY_LEN = x.length, MODULO = 1000000007n, HALF_R_PLUS_S = Math.floor((r + s) / 2), HALF_R_MINUS_S = Math.floor((r - s) / 2);
    const m = ARRAY_LEN;
    /* dp is 3-dimensional array [i][j][k], the value represents [count of ways] that by using
    i: first i elements of array; 
    j: the size of subset; pciking up j elements from [ first i elements of array]
    k: sum value of elements from j subset
    */
    if (r < s)
        return 0;

    let dp = [];
    for (let i = 0; i <= m; i++) {
        dp[i] = [];
        for (let j = 0; j <= m; j++) {
            dp[i][j] = [];
            for (let k = 0; k <= HALF_R_PLUS_S; k++) {
                dp[i][j][k] = 0n;
            }
        }
    }
    dp[0][0][0] = 1n;

    for (let i = 1; i <= m; i++) {
        for (let j = 0; j <= m; j++) {
            for (let k = 0; k <= HALF_R_PLUS_S; k++) {
                dp[i][j][k] = dp[i - 1][j][k];
                let iValue = x[i - 1];
                if (k >= iValue && j >= 1)
                    dp[i][j][k] += dp[i - 1][j - 1][k - iValue];
                dp[i][j][k] %= MODULO;
            }
        }
    }

    let sum = 0n;
    for (let j = 1; j <= m; j++) {
        sum += (dp[m][j][HALF_R_PLUS_S] * dp[m][j][HALF_R_MINUS_S]) % MODULO;
    }

    return sum;
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const mrs = readLine().split(' ');

    const m = parseInt(mrs[0], 10);

    const r = parseInt(mrs[1], 10);

    const s = parseInt(mrs[2], 10);

    const x = readLine().split(' ').map(xTemp => parseInt(xTemp, 10));

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

    ws.write(result + "\n");

    ws.end();
}

Wet Shark and Two Subsequences Python Solution

from collections import Counter
MOD = 10 ** 9 + 7
n, r, s = map(int, input().split())
if (r ^ s) & 1:
    print(0)
    quit()
x = (r + s) // 2
y = (r - s) // 2

a = list(map(int, input().split()))
s = [Counter() for _ in range(n + 1)]
s[0][0] = 1
for i, v in enumerate(a):
    for j in range(i, -1, -1):
        s[j + 1] += Counter({k + v: e % MOD for k, e in s[j].items() if k + v <= x})
print(sum((c[x] * c[y]) % MOD for c in s[1:]) % MOD)

c C# C++ HackerRank Solutions java javascript python