## 1047 - Zones

Moderator: Board moderators

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

### Problem J - World Finals 2005

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

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.

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

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

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

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

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 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

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

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

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

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

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

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