acash's blog

Google | HARD OA(Campus Placement) | Subsequence Supremacy
By acash, history, 3 days ago, In English

You are given an array arr of size n and an integer k. Score of an array is defined as number of its non-empty subarrays with sum = k. Your task is to find sum of scores of all the subsequences of arr. Since the answer can be very large print its modulo 1e9+7.

Input format :

First line contains T , the number of testcases. Each testcase has two lines. First line contains two integers n and k. Second line contains n integers describing arr.

Output Format :

For each testcase, print a single integer denoting sum of scores of all the subsequences of arr modulo 1e9+7

Constraints :

1<=T<=1000 1<=n<=1000 1<=k<=1000 1<=arr[i]<=1e5 Sum of n over all the testcases will not exceed 1000 Sum of k over all the testcases will not exceed 1000.

First Test Case

2

10 1

5 1 4 5 4 5 3 3 2 2

10 2

2 2 5 1 2 3 2 1 2 4

Output:

512

2592

Dry run:

For 1st tc, for subarray [1] there are 9-left out elements, possibility of taking-not-taking = 2^9 = 512 no other subarray possible, hence ans = 512

For 2nd tc, for subarray [2], there are 5 such subarrays, possibility of other 9 elements = 2 ^ 9 = 512 (for each) there are 5 such, hence ans for subarray [2] = 5 x 512 = 2560 now there is one more possible subarray [1,1], to make this as a subarray we need to exclude all the elements in between, hence new array = [2,2,5,1,1,2,4], now keeping [1,1] aside, we are left with 5 other element, possibility = 2 ^ 5 = 32 no other subarray possible

hence ans = 2560 + 32 = 2592

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
3 days ago, # |
← Rev. 5   Vote: I like it +3 Vote: I do not like it

:)

→ Reply
  • »
    »
    3 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Isn't Time complexity should be n * k * n because we have 3 nested loops. Can you Please explain on it ?

    → Reply
    • »
      »
      »
      3 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for pointing the mistake out. I had miscalculated the third loop to be of O(n) on summation over all k, but on closer inspection it looks like it will be O(n^2) over all k. This does indeed make the complexity O(n^2 * k). A better approach might be storing only the current indices and backtracking when k is achieved, which'd probably increase the complexity of the code a bit.

      → Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

This is what I came up with can't guarantee it's credibility of the code because I have not tested on many cases, but the idea is that we find a subsequence with the given sum and we treat it like an subarray and the total subsequence we can form will be extra elements we can take on left and right (all of there combinations i.e. 2 ^ (left + right))

Do in the code dp[ i ][ j ][ k ] represents the ith element, j is 1 when we haven't taken any previous element, otherwise 0 and k is the sum left.

Please correct me if I'm wrong. 

ll n, k;
ll a[N], dp[1005][2][1005];

ll solve(ll i, ll j, ll k) {
	if (i > n) return 0;
	if (dp[i][j][k] != -1) return dp[i][j][k];
	ll ans = 0;
	// first
	if (j) {
		// pick
		if (k > a[i]) ans += two[i - 1] * solve(i + 1, 0, k - a[i]);
		if (k == a[i]) ans += two[n - 1];
		// notpick
		ans += solve(i + 1, 1, k);
	} else {
		// pick
		if (k > a[i]) ans += solve(i + 1, 0, k - a[i]);
		if (k == a[i]) ans += two[n - i];
		// notpick
		ans += solve(i + 1, 0, k);
	}
	return dp[i][j][k] = ans;
}

void solution() {
	cin >> n >> k;
	FOR (i, 1, n) cin >> a[i];
	FOR(i, 0, n) FOR (j, 0, 1) FOR (K, 0, k) dp[i][j][K] = -1;
	cout(solve(1, 1, k));
}
→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Note that values above 1000 are useless

Also see that we can deal with count of values instead of values

So maximum number of values we have to deal with is 1+2+3...t=1000

t=50

So for any subsequence we can fix its end points and count its contribution by 2^(i-1)*2^(n-j)*x

Where x is number of subsequences having sum k-a[i]-a[j] from i+1 to j-1

→ Reply
»
3 days ago, # |
  Vote: I like it +8 Vote: I do not like it

we can take dp(i,k) as number of subseq which make up a sum of k as a some prefix and once we fill this table we can simply multiply with the ways to chose the remaining elements from the start which is 2^i for each dp[i][k]

void solve(){
  ll int n,z;
  cin>>n>>z;
  vll a(n);
  for(int i = 0;i<n;i++)cin>>a[i];
  function<ll(ll)> twopow = [&](ll int b){
    if(b==0) return 1LL;
    ll ans = (twopow(b/2) * twopow(b/2))%MOD;
    if(b&1) ans = (2*ans)%MOD;
    return ans;
  };
  ll cache[1001][1001];
  memset(cache,-1,sizeof(cache));
  function<ll(ll,ll)> dp = [&](ll int i , ll int k) {
    if(i==n){
      if(k!=0) return 0LL;
      return 1LL;
    }
    if(k<0) return 0LL;
    if(k==0) return twopow(n-i);
    if(cache[i][k]!=-1) return cache[i][k];
    ll ans = dp(i+1,k-a[i]);//take
    ans = (ans + dp(i+1,k))%MOD; // don't take
    return cache[i][k] = ans;
  };
  ll ans = 0;
  for(int i = 0;i<n;i++){
    ll del = (twopow(i)*dp(i+1,z-a[i]))%MOD;
    ans = (ans + del)%MOD;
  }
  cout<<ans<<'\n';
  
}
→ Reply
  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    1 10 3 1 2 1 3 2 2 1 1 1 4

    what is the answer you are getting for this testcase?

    → Reply
»
3 days ago, # |
  Vote: I like it +1 Vote: I do not like it

int f(int ind, int sum, vector &v, int k) {

int n =  v.size();
if(sum == k) {
    return (1ll<<(ind+1));
}
if(ind == -1 || sum > k) return INT_MIN;
int pick = 1, nopick = 0;
if(sum == 0ll) pick = (1ll<<(n-1ll-ind));
pick *= f(ind - 1, sum + v[ind], v, k);
nopick = f(ind - 1, sum, v, k);
int ans = 0;
if(pick > 0) ans += pick;
if(nopick > 0) ans += nopick;
return ans;

}

signed main() { init_code(); int t; cin>>t; while(t--) { int n, k; cin>>n>>k; vector v(n); for(auto &it : v) cin>>it; cout<<f(n-1, 0, v, k)<<endl; } }

How is this solution only utilising sum and index as a 2d dp not sure it will work, still have to memoise it this is just the recursive code, please guide me regarding the above.

→ Reply
»
43 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Is this a "MEET-IN-THE-MIDDLE" problem, since the constraints are large so is it possible to solve it through DP?

→ Reply
  • »
    »
    36 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    no it is dp the constraints are only 10^3 * 10^3 so u can use dp to solve it.

    → Reply
»
34 hours ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it
Main idea
Initial Approach
Optimized idea

My implementation (it is passing the samples)

→ Reply
  • »
    »
    25 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can't we just bruteforce all $$$[l, r]$$$ pairs and add $$$2^{l-1} \times 2^{n-r}$$$ to the answer if a[l:r] sums to k?

    → Reply
    • »
      »
      »
      20 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The problem statement says

      "Your task is to find sum of scores of all the subsequences of arr."

      So the entire subarray $$$a[l..r]$$$ need not be considered.

      In the second test case, $$$[1,2,3,2,1]$$$ is a valid case, because we can choose $$$[1,1]$$$ which has the sum of $$$2$$$.

      → Reply
    • »
      »
      »
      20 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah I was wondering the same thing.

      → Reply
»
26 hours ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

consider 0 as the numbers we do not take and 1 as the numbers we take

assume that for achieving sum = k: our take not take looks something like this

0 0 1 0 1 1 0 1 0 0 0

now this subsequence has sum=k, and this subsequence will be the subarray for all combinations of take — not take of 0s before first occurrence of 1 and after that last occurrence of 1

so this subsequence will act as subarray for 2^5=(32) subsequence

we can easily handle this using dp[1001][1001][2]

the last state determines whether we have selected our first 1 or not

dp states->

f(0,0,0)->we are at index 0 and until now our sum=0 and we have not selected our first 1

dp transition ->

f(i,s,0)=2*f(i+1,s+a[i],1)+f(i+1,s,0)

f(i,s,1)=f(i+1,s+a[i],1)+f(i+1,s,1)

base case ->

if before all the elements are exhausted we achieve sum=k, return 2^(rem elements)

otherwise return 0

i really think this should work

→ Reply
»
8 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it 
M = 1000000007

def solve(arr, k):
    n = len(arr)
    pw = [1] * n
    for i in range(1, n):
        pw[i] = 2 * pw[i - 1]
        pw[i] %= M
    res = 0
    s = [0] * (k + 1)
    for i in range(n):
        for j in range(k, arr[i] - 1, -1):
            curr = s[j - arr[i]] + pw[i] if arr[i] == j else s[j - arr[i]]
            res += curr * pw[n - i - 1] if j == k else 0
            s[j] += curr
            s[j] %= M
            res %= M
    return res

print(solve([5, 1, 4, 5, 4, 5, 3, 3, 2, 2], 1))
print(solve([2, 2, 5, 1, 2, 3, 2, 1, 2, 4], 2))
→ Reply
»
8 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I feel like the below solution is an optimized solution for this. It uses O(n) space for dp.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll binpow(ll a, ll b, ll M = 1000000007)
{
    a %= M;
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = (ans * a) % M;
        b /= 2;
        a = (a * a) % M;
    }
    return ans;
}

void solve()
{
    ll n, k, ans = 0;
    cin >> n >> k;
    vector<ll> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    vector<ll> s(k + 1);
    s[0] = 1;
    for (int i = 0; i < n; i++, s[0] = s[0] * 2 % M)
    {
        if (a[i] > k)
            continue;
        auto c = s;
        for (int j = 0; j + a[i] <= k; j++)
        {
            if (j + a[i] == k)
                ans = (ans + binpow(2, n - i - 1) * s[j] % M) % M;
            c[j + a[i]] = (c[j + a[i]] + s[j]) % M;
        }
        s = c;
    }
    cout << ans << endl;
}

int32_t main()
{
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}
→ Reply
»
7 hours ago, # |
  Vote: I like it 0 Vote: I do not like it 
from collections import Counter

M = 1000000007

def solve(arr, k):
    n = len(arr)
    res = 0
    sf = Counter()
    for i, el in enumerate(arr):
        sf[0] = pow(2, i, M)
        res += sf.get(k - el, 0) * pow(2, n - i - 1, M)
        sf += Counter({x + el: sf[x] for x in sf if x + el <= k})
        res %= M
    return res
→ Reply