1047 - Zones

[mafattah]

Anybody knows a solution for problem J in the last ICPC World Finals that is more efficient than O(n^2 * 2^n)? Namely, checking all possible subsets?

Also, does anybody know how much vectors are less efficient than arrays, in case I only use .size() and operator[]?

Thanks

[Per]

Anybody knows a solution for problem J in the last ICPC World Finals that is more efficient than O(n^2 * 2^n)? Namely, checking all possible subsets?

Isn't checking all possible subsets actually O((n+t)*(n choose k)), where k is the number of towers to be built? But apart from that, no, I don't know of a better solution.

Also, does anybody know how much vectors are less efficient than arrays, in case I only use .size() and operator[]?

It depends heavily on how much optimisation you use when compiling. When not using any optimisation, you can get quite a difference (more than twice as slow). If I remember correctly, g++ starts inlining such methods when using -O2, and then it doesn't make that big a difference.

[Adrian Kuegel]

I think using bit operations you can get it in O(t * (n choose k) ) (well, of course only if n <= 32, but it was <=20, so that works).

[Per]

Yeah, we did it with bitmasks. I think you'll get something like O(n*t*(n choose k)) if you're not using bitmasks.

How do you get rid of the factor n? For each subset of size k that you check, you have to add up k of n numbers. But if you're using bitmasks, wouldn't you have to check all n possible bits to see if they're set?

[Adrian Kuegel]

I just implemented it, to check my idea.
Well, I need to precalculate a table that gives me the # bits of a bitmask in constant time, but then it is complexity O(m * (n choose k) )
(m number of common areas)

Code: Select all

#include <stdio.h>

int sol,best,n,k;
int c[20];
int comm[10][2],t;
int nbits[1<<20];

int getsign(int a) {
	if (nbits[a] == 1)
		return 0;
	if (nbits[a]&1)
		return 1;
	return -1;
}

void doit(int pos, int sel, int bitsel, int sum) {
	if (n-pos<k-sel)
		return;
	if (k == sel) {
		for (int i=0; i<t; i++)
			if (comm[i][0]&bitsel)
				sum += getsign(comm[i][0]&bitsel)*comm[i][1];
		if (best<sum) {
			best = sum;
			sol = bitsel;
		}
		return;
	}
	doit(pos+1,sel+1,bitsel|(1<<pos),sum+c[pos]);
	doit(pos+1,sel,bitsel,sum);
}

int cnt_bits(int a) {
	if (!a)
		return 0;
	if (nbits[a])
		return nbits[a];
	return nbits[a] = cnt_bits(a>>1)+(a&1);
}

int main() {
	int scen = 0;
	for (int i=(1<<20)-1; i>=0; i--)
		cnt_bits(i);
	while(scanf("%d %d",&n,&k)==2 && (n+k)) {
		for (int i=0; i<n; i++)
			scanf("%d",&c[i]);
		scanf("%d",&t);
		for (int i=0; i<t; i++) {
			comm[i][0] = 0;
			int cnt;
			scanf("%d",&cnt);
			for (int j=0; j<cnt; j++) {
				int b;
				scanf("%d",&b);
				comm[i][0] |= 1<<(b-1);
			}
			scanf("%d",&comm[i][1]);
		}
		best = -1;
		doit(0,0,0,0);
		printf("Case Number %d\n",++scen);
		printf("Number of Customers: %d\n",best);
		printf("Locations recommended:");
		for (int i=0; i<n; i++)
			if (sol&(1<<i))
				printf(" %d",i+1);
		puts("\n");
	}
	return 0;
}

edit: I just thought again, and this code doesn't work for cases like:
3 2
5 5 1
2
2 1 2 3
3 1 2 3 1

[Robert_Alonso]

Hi, I've been trying this problem, but got WA. Can anyone tell me what's wrong here? Thanks in advance.

Code: Select all

Removed after AC.

[brianfry713]

Print a blank line after each test case, including the last one.

[Robert_Alonso]

Print a blank line after each test case, including the last one.

Hi, I've included a blank line after the each test case( printf("\n\n"); ), but still got WA. However, while taking a look at the sample output, I noticed that it does include a white space at the end of each line, and two white spaces at the end of the blank lines, but the problem output specification says that there are no blank spaces at the end of any line. Please help. Thank you.

[brianfry713]

Post your updated code. Don't print a space at the end of a line. Blank lines should not have any spaces.

[Robert_Alonso]

Here it is:

Code: Select all

Removed after AC.

[brianfry713]

Input:

Code: Select all

2  2
2 2
1
2  1 2      1
3  2
4 4 4
4
2  1 2      1
2  1 3      1
2  2 3      1
3  1 2 3    1
4  2
7 7 7 7
9
2  1 2      1
2  1 3      1
2  2 4      1
2  3 4      1
3  1 2 3    1
3  1 2 4    1
3  1 3 4    1
3  2 3 4    1
4  1 2 3 4  1
0 0

AC output:

Code: Select all

Case Number  1
Number of Customers: 3
Locations recommended: 1 2

Case Number  2
Number of Customers: 6
Locations recommended: 1 2

Case Number  3
Number of Customers: 11
Locations recommended: 1 4

[Robert_Alonso]

Finally, after rewriting the code from scratch and simplify some parts, got AC. Thank you very much brianfry.

[Lim.YuDe]

When I run this on my compiler the following code works with 0 errors and 0 warnings, but when I submit it I get Compilation Error.
Any idea why I get CE for this code?

EDIT: FIXED Compilation Error, but now I get WA. I have tested the input kindly posted here by Brianfry, and also the sample input given, and I get the output expected. Does anybody have any idea what is wrong with my code? Thanks in advance

Code: Select all

Removed after AC

[brianfry713]

Print a blank line after each test case, including the last one.

[Lim.YuDe]

Got AC. Thank you so much Brianfry. I need to read the output format better next time.