Model Solution of GEEK04

geek04.cpp

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> a;
int dp[1<<20][2];

int rec(int lft_mask, int turn) {
	if (lft_mask == 0) {
		return 0;
	}
	// cerr << lft_mask << " " << turn << "\n";
	int &res = dp[lft_mask][turn];
	if (res != -1) {
		return res;
	}
	if (turn) {
		int pos = -1;
		res = INT_MAX;
		int rgt_mask = ((1<<n) - 1) ^ lft_mask;
		for(int i = 0; i < n; ++i) {
			if (rgt_mask & (1<<i)) {
				if (res > a[i]) {
					pos = i;
					res = a[i];
				}
			}
		}
		res += rec(lft_mask ^ (1<<pos), turn ^ 1);
	}
	else {
		if (__builtin_popcount(lft_mask) == 1) {
			res = INT_MAX;
			for(int i = 0; i < n; ++i) {
				if (lft_mask & (1<<i)) {
					res = min(res, a[i]);
					res += rec(lft_mask ^ (1<<i), turn ^ 1);
				}
			}
		}
		else {
			res = INT_MAX;
			for(int i = 0; i < n; ++i) {
				if (lft_mask & (1<<i)) {
					for(int j = i+1; j < n; ++j) {
						if (lft_mask & (1<<j)) {
							int lft = lft_mask ^ (1<<i) ^ (1<<j);
							int val = max(a[i], a[j]) + rec(lft, turn ^ 1);
							res = min(res, val);
						}
					}
				}
			}
		}
	}
	assert(res >= 0);
	return res;
}

int main() {
	ios_base::sync_with_stdio(false);
	int t;
	cin >> t;
	assert(1 <= t && t <= 10);
	while(t--) {
		cin >> n;
		assert(1 <= n && n <= 20);
		a.resize(n);
		for(int i = 0; i < n; ++i) {
			cin >> a[i];
		}
		memset(dp, -1, sizeof(dp));
		cout << rec((1<<n)-1, 0) << "\n";
	}
	return 0;
}

Can you provide the original test cases that you used at codechef?

Hi @bansal1232, it is not possible to share test cases used in codechef contests. It is against their rules, as I was told before. Btw, you can generate random test cases easily for this problem and then locally compare the running time for your codes. Don't forget to compile your code with "-O2" flag as it decreases the execution time of your code significantly and is used in all online judges too.

@likecs Can you please tell me why I am getting TLE in last two cases even I have not used recursion
https://www.codechef.com/viewsolution/16377126