1047 - Zones

All about problems in Volume 10. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

mafattah
New poster
Posts: 23
Joined: Fri Apr 26, 2002 1:00 am
Location: Cairo, Egypt

Problem J - World Finals 2005

Post by mafattah » Mon Apr 11, 2005 7:24 am

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
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Re: Problem J - World Finals 2005

Post by Per » Mon Apr 11, 2005 8:10 am

mafattah wrote: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.
mafattah wrote: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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Mon Apr 11, 2005 8:54 pm

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
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Tue Apr 12, 2005 9:55 am

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Tue Apr 12, 2005 8:31 pm

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
Last edited by Adrian Kuegel on Tue Apr 12, 2005 8:51 pm, edited 1 time in total.

Robert_Alonso
New poster
Posts: 8
Joined: Fri Jul 25, 2014 2:04 am

1047 - Zones

Post by Robert_Alonso » Fri Jul 25, 2014 3:53 am

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.
Last edited by Robert_Alonso on Wed Jul 30, 2014 4:37 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 1047 - Zones WA

Post by brianfry713 » Fri Jul 25, 2014 7:18 pm

Print a blank line after each test case, including the last one.
Check input and AC output for thousands of problems on uDebug!

Robert_Alonso
New poster
Posts: 8
Joined: Fri Jul 25, 2014 2:04 am

Re: 1047 - Zones WA

Post by Robert_Alonso » Sat Jul 26, 2014 2:36 am

brianfry713 wrote: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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 1047 - Zones WA

Post by brianfry713 » Mon Jul 28, 2014 8:00 pm

Post your updated code. Don't print a space at the end of a line. Blank lines should not have any spaces.
Check input and AC output for thousands of problems on uDebug!

Robert_Alonso
New poster
Posts: 8
Joined: Fri Jul 25, 2014 2:04 am

Re: 1047 - Zones WA

Post by Robert_Alonso » Tue Jul 29, 2014 6:51 pm

Here it is:

Code: Select all

Removed after AC.
Last edited by Robert_Alonso on Wed Jul 30, 2014 4:37 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 1047 - Zones WA

Post by brianfry713 » Tue Jul 29, 2014 8:10 pm

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

Check input and AC output for thousands of problems on uDebug!

Robert_Alonso
New poster
Posts: 8
Joined: Fri Jul 25, 2014 2:04 am

Re: 1047 - Zones

Post by Robert_Alonso » Wed Jul 30, 2014 4:36 pm

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

Lim.YuDe
New poster
Posts: 15
Joined: Sat Dec 13, 2014 1:32 pm

Re: 1047 - Zones

Post by Lim.YuDe » Tue Jan 13, 2015 5:58 pm

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
Last edited by Lim.YuDe on Wed Jan 14, 2015 3:49 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 1047 - Zones

Post by brianfry713 » Tue Jan 13, 2015 10:51 pm

Print a blank line after each test case, including the last one.
Check input and AC output for thousands of problems on uDebug!

Lim.YuDe
New poster
Posts: 15
Joined: Sat Dec 13, 2014 1:32 pm

Re: 1047 - Zones

Post by Lim.YuDe » Wed Jan 14, 2015 3:48 am

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

Post Reply

Return to “Volume 10 (1000-1099)”