CSES Task 1628, Meet in the Middle

Problems and Contests
#1

Here is the problem. Below is my code.

/*
Author: atharvd
Date:
Problem:
*/

#include<iostream>
#include<string>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<algorithm>
#include<functional>
#include<numeric>
#include<cmath>
#include <climits>

using namespace std;

#define ain(a) for(int i=0;i<a.size();i++) cin >> a[i]
#define aout(a) for(int i=0;i<a.size();i++) { if(i > 0) cout << " "; cout << a[i]; }; cout << endl
#define couty cout << "YES\n"
#define coutn cout << "NO\n";

#define endl "\n"

#define pb push_back
#define eb emplace_back
#define all(a) a.begin(),a.end()

#define nl cout << endl

#define add(m, e) if(m.find(e) == m.end()) m[e] = 0; m[e]++;
#define precision(x) printf("%.12f\n", x);

#ifdef LOCAL_JUDGE
#include "local.hpp"
#else
template <typename Head, typename... Tail> void dout(Head&& h, Tail&&... t) {}
#endif

typedef long long ll;
#define int ll
typedef pair<int,int> pii; typedef pair<ll,int> pli; typedef tuple<ll,int,int> tllii;
typedef vector<int> vi; typedef vector<bool> vb; typedef vector<ll> vll; typedef vector<vector<int> > vvi;

ll inf = 1e18 + 1;

map<int, int> freq1;
map<int, int> freq2;

void search1(vi arr, int k, int s){
    if(k == arr.size()){
        freq1[s]++;
    }
    else{
        search1(arr, k + 1, s);
        search1(arr, k + 1, s + arr[k]);
    }
}

void search2(vi arr, int k, int s){
    if(k == arr.size()){
        freq2[s]++;
    }
    else{
        search2(arr, k + 1, s);
        search2(arr, k + 1, s + arr[k]);
    }
}

void solve() {
    int n, x;
    cin >> n >> x;
    vll arr1;
    vll arr2;
    for(int i = 0; i < n; i++){
        int a;
        cin >> a;
        if(i % 2 == 0) arr1.pb(a);
        else arr2.pb(a);
    }
    search1(arr1, 0, 0);
    search2(arr2, 0, 0);
    ll ans = 0;
    for(auto [a, b]: freq1){
        if(freq2.find(x - a) != freq2.end()){
            ans +=  b * freq2[x - a];
        }
    }
    cout << ans << endl;
}

signed main(signed argc,char *argv[]){
#ifdef LOCAL_JUDGE
	freopen(argc > 1 ? argv[1] : "in.txt", "r", stdin);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
 
	int t = 1;
	//cin >> t;
	for(int i=1;i<=t;i++) {
		dout("***",i);
		solve();
	}
}

I get a timeout despite using the meet in the middle strategy, can anyone tell me how to optimize this? I know the code is not the best.

#2

Use PBDS with custom hash. Besides, a recursive function search slows down your program. Try to use a while loop.

1 Like
#3

Hi You’re using a map which slowes a lot.Instead you can use a normal vector and after pushing all elements into vector you can sort (O(20 log 20) which is quite small)) vectors and use binary search(Equal Range) to find answer.
Here is my code:

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
typedef unsigned int ui;

int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;ll x;cin>>n>>x;
    vector<ll>Fere,Fer;
    vector<int>v(n);
    for(int i=0;i<n;i++)cin>>v[i];
    //(I created subsets using while loop instead recursive.)
    int now=n/2;
	for(int mask=0;mask<(1<<now);mask++){
		ll tot=0;
		for(int i=0;i<now;i++){
			if(mask&(1<<i))tot+=v[i];
		}
		if(tot<=x)Fere.pb(tot);
	}
	for(int mask=0;mask<(1<<(n-now));mask++){
		ll tot=0;
		for(int i=0;i<(n-now);i++){
			if(mask&(1<<i))tot+=v[i+now];
		}
		if(tot<=x)Fer.pb(tot);
	}
	//sort(Fere.begin(),Fere.end());
	ll ans=0;
	sort(Fer.begin(),Fer.end());
	//for(int e:Fer)cout<<e<<' ';
	for(ll e:Fere){
		//cout<<e<<' ';
		auto it=equal_range(Fer.begin(),Fer.end(),x-e);
		ans+=(it.second-it.first);
	}
	cout<<ans<<'\n';
    return 0;
    //How did we get here?
}

Hope it helps.