Google | HARD OA(Campus Placement) | Subsequence Supremacy

#	User	Rating
1	tourist	3985
2	jiangly	3741
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3489
7	Radewoosh	3483
8	Kevin114514	3442
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
2	atcoder_official	162
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	nor	150

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

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

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)); }

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'; }

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;

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))

#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; }

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

Comments (29)

Write comment?

SomeYoGuy

6 months ago, # |

← Rev. 5 →

→ Reply

akashtomar19

6 months ago, # ^ |

Isn't Time complexity should be n * k * n because we have 3 nested loops. Can you Please explain on 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.

bhavyatyagi

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.

illum1nadi

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

what is the answer you are getting for this testcase?

first three are t, n, k rest are numbers

2146

Amit9

please explain your solution, what is the two array?

indresh_hErd

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

kruelcratos

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]

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

}

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.

shivamp_07

Orz

mayushiii

t=1 n=5 k=3 [3,3,3,3,3] Answer for this testcase??

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

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

WORTH

← Rev. 2 →

Main idea

Initial Approach

Optimized idea

My implementation (it is passing the samples)

weirdflexbutok

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?

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$$$.

Thanks

Isaac_Newton__

Yeah I was wondering the same thing.

lemnisKate

← Rev. 3 →

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)=f(i+1,s+a[i],1)+2*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

uday51

It won't work ... due wrong transitions, check my comment below on why it's wrong.

bihariforces

SIGTERM

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

I have a dp solution to it, i saw many dp solutions but some of them seemed wrong, actually this question can be done in O(n*n*k) time complexity and can be optimised further using prefix sum to O(n*k) :-

DP States-> i X j X flag ---> till index i, sum of score of all subsequences with k=j, flag= 0/1

dp[i][j][1] means that ending at index i, sum of score of all subsequences with k=j such that element at ith index is included in the sum .

so it's transition can be :- dp[i][j][1] += dp[h][j-a[i]][1] , such that 0 <= h < i ( Now optimise that using prefix sum )

dp[i][j][0] means that ending at index i, sum of score of all subsequences with k=j such that element at ith index is not included in the sum. But it can or can not be included in the subsequence. In both the cases whether it's included or not included in subsequence it's value is going to be the same dp[i-1][j][0] + dp[i-1][j][1].

Add that 2 times because of the dual possibilities of including or not including the subsequence

Here is my C++ implementation

Code

void solve(){
 
    int n,k; cin>>n>>k;
    vector<int> a(n);
    for(int i=0 ;i<n ;i++) cin>>a[i];

    vector<vector<vector<int>>> dp( n+1 , vector<vector<int>> ( k+1 , vector<int> (2,0)));

    // i X j X flag  ---> till index i , sum of score of all subsequence with k = j , flag = 0 / 1
    // if flag is 0 , this means the sum of j in that subarray includes the ith index element ans 0 means it doesn't

    if( k >= a[0] ) dp[0][a[0]][1] = 1;
    
    // Maintaining prefix sum of all 0 < j <= k for all indices 0 -> i-1 to reduce the TC from O(n) to O(1) inside the loop

    vector<int> psum(k+1,0);
    if( k >= a[0] ) psum[a[0]] = 1;

    for(int i=1 ;i<n ;i++){
        for(int j=0 ;j<=k ;j++){

            dp[i][j][0] +=  2 * ( dp[i-1][j][0] + dp[i-1][j][1] );

            if( j > a[i] ) dp[i][j][1] +=  psum[j-a[i]];     

            // Unique case         
            else if( j == a[i] ) dp[i][j][1] +=  (1<<(i));
        }
        // Managing prefix sum

        for(int j=0 ;j<=k ;j++){
            psum[j] += dp[i][j][1];
        }
    }

    cout<< (dp[n-1][k][0] + dp[n-1][k][1]) <<endl;

}

acash's blog