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.
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()
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("0\n");
}
else{
makev(v,m);
int sum = (r+s)/2, diff = (r-s)/2;
if(diff < 0){
printf("0\n");
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("%d\n",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("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;
}
0 Comments