Nilesh_'s blog

[Problem] Find count of subsequences where sum of elements equal to target over all subsequences
By Nilesh_, 2 months ago, In English

The special value of sequence of integers is defined as the number of non empty subsequences where the sum of elements is equal to k. Given an array arr of n integers and an integer k. Find the sum of special values of all non empty subsequences of arr. Since the sum can be large. Report it modulo 1e9 + 7.

Constraints:

1 <= N <= 2000

1 <= arr[i] <= 1e9

1 <= k <= 2e12

Example: n = 4, k = 3, arr = [3, 1, 4] ans is 6.

ans = 2(contribution of sequence [1, 4]) + 4(contribution of [4]) = 6

Kindly help me with the above probelm, Thanks. I tried forming dp state based on unique values and for each possible subsequence where sum equals target, 2^(n — currentElementsCount) will be its contribution to ans. However couldn't arrive at a proper solution.

Upd1: changed title, added example

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

»
2 months ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

I don't think you can solve the problem "does there exist a subsequence of the array that equals k" in time faster than O(NK) much less the full problem with the constraints given.

Could you link to the source of the problem?

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

    This was from an online test conducted by a company.

    There was a slight mistake in the title, which has been corrected. The problem statement is exactly the same as the original problem from the test. The constraint for n is accurate, but I assumed the ranges for arr[i] and k.

    → Reply
»
2 months ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it 
//////////////////Keep calm and code on////////////////////
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
using ll= long long;
#define f(i,n) for(int i=0;i<n;i++)
#define sorted(x) sort(x.begin(),x.end());
#define rsorted(x) sort(x.rbegin(),x.rend());
#define rev(x) reverse(x.begin(),x.end());
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef pair<int, int> pii;
typedef vector<pair<int, int>> vpii;
typedef unordered_map<int, int> umap_ii;
typedef unordered_map<ll, ll> umap_ll;
typedef unordered_map<string, int> umap_si;
int dp[2002][2002];
int fun(int n,vi& arr,int count,int ind){
    if(ind==n)return 0;
    if(dp[ind][count]!=-1)return dp[ind][count];
    int sum=0;

    if(n-ind-1<count)sum+=fun(n,arr,count,ind+1);
    if(count>0)sum+=fun(n,arr,count-1,ind+1)+arr[ind];

    return dp[ind][count]=sum;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
    
    int n,k;
    cin>>n>>k;
    vector<int>arr;
    int ans=0;
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<n;i++){
        int a;
        cin>>a;
        arr.pb(a);
    }
    int sum=0;
    for(int i=1;i<=n;i++){
        int x=fun(n,arr,i,0);

        if(x==k){
            sum+=pow(2,n-i);// as other element have choice to be in the subsequence (yes:No)
        }
    }
        cout << sum << endl;
    
    // return 0;
}

will this o(n^3) or o(n^2)

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I have another problem , can we find sum of LIS in less than O(N^2)?

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

    I found this code lis in o(n*log n)

    set<int> s;
    set<int>::iterator it;
    for(int i=0;i<n;i++)
    {
         s.insert(arr[i]);
             it=s.find(arr[i]);
         it++; 
         if(it!=s.end()) 
           s.erase(it);
    }
    cout<<s.size()<<endl;.
    → Reply
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      not LIS size , sum of all elements in LIS

      → Reply
      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it 
         set<int> s;
    vector<int> lis;
    for(int i = 0; i < n; i++) {
        auto it = s.lower_bound(arr[i]);
        if(it != s.end()) s.erase(it);
        s.insert(arr[i]);
    }

    int sum_lis = 0;
    for(int x : s) sum_lis += x;

    cout << sum_lis << "\n";
        → Reply