When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

qwerty29's blog

By qwerty29, history, 3 years ago, In English

Question: https://cses.fi/problemset/task/1628/

You are given an array of n numbers. In how many ways can you choose a subset of the numbers with sum x?

Solution: Using meet in the middle approach but its timing out for few test cases, could you please help me where I can improve my code.

#include <bits/stdc++.h>
#define all(c) (c).begin(), (c).end()
#define present(c, x) ((c).find(x) != (c).end())
#define cpresent(c, x) (find(all(c),x) != (c).end())
#define fi first
#define se second
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define parr(arr) for(int num : (arr)) cout << num << ' '; cout << '\n';
using namespace std;


int main(){
    ios::sync_with_stdio(false); cin.tie(NULL);
        int n; cin >> n;
        long long int x; cin >> x;
        int mid = n/2;
        vector<int> arr(n);
        for(int i=0;i<n;++i) cin >> arr[i];
        vector<long long int> left, right;
        for(int i=0;i<(1<<mid);++i){
            long long int sum = 0;
            for(int j=0;j<32;++j){
                if(i & (1<<j)){
                    sum += arr[j];
                }
            }
            left.push_back(sum);
        }
        int rem = n-mid;
        for(int i=0;i<(1<<rem);++i){
            long long int sum =0;
            for(int j=0;j<32;++j){
                if(i & (1<< j))
                    sum += arr[mid+j];  
            }
            right.push_back(sum);
        }
        long long int count = 0;
        unordered_map<long long int,int> m;
        for(int num : right) m[num]++;
        for(int i=0;i<left.size();++i){
            if(left[i] <= x){
                long long int other = x - left[i];
                count += m[other];
            }
        }
        cout << count << '\n';
    return 0;
}
  • Vote: I like it
  • -1
  • Vote: I do not like it

| Write comment?
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

use custom hash function.

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

just use map instead of unordered

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Reserve memory. Use m.reserve(1e6).

Also, you can use custom hash. Blog: https://codeforces.com/blog/entry/62393

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it
#include<bits/stdc++.h>
using namespace std;
vector<long long> generateSub(vector<long long> &nums,long long s,long long e){
       long long l=e-s;
       vector<long long> ans;
       for(long long i=0;i<(1<<l);i++){
           long long sum=0;
           for(long long j=0;j<l;j++){
               if(i&(1<<j)){
                   sum+=nums[j+s];
               }
           }
           ans.push_back(sum);
       }
       return ans;
   }
 
void solve(){
	long long n,x;
	 cin>>n>>x;
	 vector<long long> v(n);
	 for(long long i=0;i<n;i++){
	 	cin>>v[i];
	 }
	 vector<long long> sum1,sum2;
	 sum1=generateSub(v,0,n/2);
	 sum2=generateSub(v,n/2,n);
	 long long ans=0;
	 sort(sum1.begin(), sum1.end());
     sort(sum2.begin(), sum2.end());
     for (long long s1 : sum1)
        ans += upper_bound(sum2.begin(), sum2.end(), x - s1) - lower_bound(sum2.begin(), sum2.end(), x - s1);
      cout << ans;
}
int main(){
    #ifndef ONLINE_JUDGE
       freopen("input1.txt","r",stdin);
       freopen("output1.txt","w",stdout);
    #endif
       int t=1;
       // cin>>t;
       while(t--){
       	solve();
       	cout<<endl;
       }
 
}

I also stuck in this problem for a while but, I finally find out the solution for this problem