SPOJ SUBSUMS Solution

| July 01, 2015

The correct, optimal and working solution for programming question SUBSUMS on spoj

#include <stdio.h>
#include <stdlib.h>

#define MAXN 35

unsigned long long int answer;

int N, A, B;

int seq[MAXN];

int numbers[2][1<<20];
int count[2];

int intCmp(const void *ap, const void *bp){
	int a = *(int *)ap;
	int b = *(int *)bp;
	if (a > b) return 1;
	else if (a < b) return -1;
	else return 0;
}

int generateSubsets(int arr[1<<20], int *seq, int c){
	int i, j;
	for (i = 0; i < (1<<c); i++)
		for (j = 0; j < c; j++)
			if (i & (1<<j))
				arr[i] += seq[j];
	return 1<<c;
}

int lower(int n){
	int lo = 0, hi = count[1], mid;

	while (lo < hi){
		mid = (lo + hi) / 2;
		if (n + numbers[1][mid] >= A)
			hi = mid;
		else
			lo = mid + 1;
	}

	return hi;
}

int upper(int n){
	int lo = 0, hi = count[1], mid;

	while (lo < hi){
		mid = (lo + hi) / 2;
		if (n + numbers[1][mid] <= B)
			lo = mid + 1;
		else
			hi = mid;
	}

	return lo - 1;
}

int main(void){
	int i;

	scanf("%d %d %d", &N, &A, &B);

	for (i = 0; i < N; i++)
		scanf("%d", &seq[i]);

	count[0] = generateSubsets(numbers[0], seq, (N+1)/2);
	count[1] = generateSubsets(numbers[1], seq + (N+1)/2, N/2);

	qsort(numbers[0], count[0], sizeof(numbers[0][0]), intCmp);
	qsort(numbers[1], count[1], sizeof(numbers[1][0]), intCmp);

	int lo = count[1] - 1, hi = count[1] - 1;

	for (i = 0; i < count[0]; i++){
		int lo = lower(numbers[0][i]);
		int hi = upper(numbers[0][i]);
		if (lo <= hi)
			answer += hi - lo + 1;
	}

	printf("%llu\n", answer);

	return 0;
}