Nilesh_'s blog

[Problem] Find count of subsequences where sum of elements equal to target over all subsequences
By Nilesh_, 4 weeks 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

»
4 weeks 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
  • »
    »
    4 weeks 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
»
4 weeks 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
»
4 weeks 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
  • »
    »
    4 weeks 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
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      not LIS size , sum of all elements in LIS

      → Reply
      • »
        »
        »
        »
        4 weeks 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