Блог пользователя Nilesh_

[Problem] Find count of subsequences where sum of elements equal to target over all subsequences
Автор Nilesh_, 3 месяца назад, По-английски

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

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
3 месяца назад, # |
← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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?

→ Ответить
  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
»
3 месяца назад, # |
← Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится 
//////////////////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)

→ Ответить
»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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;.
    → Ответить
    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      not LIS size , sum of all elements in LIS

      → Ответить
      • »
        »
        »
        »
        3 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится 
         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";
        → Ответить