qwerty29's blog

By qwerty29, history, 4 weeks 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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I changed your code a little bit and it got AC.

Code
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    hey, thanks! looks like binary search is faster than the hash map in c++, theoretically, hashmap should have performed better right?