1047  Zones
Moderator: Board moderators
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
Also, does anybody know how much vectors are less efficient than arrays, in case I only use .size() and operator[]?
Thanks
Re: Problem J  World Finals 2005
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: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?
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.mafattah wrote:Also, does anybody know how much vectors are less efficient than arrays, in case I only use .size() and operator[]?

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
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?
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)
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
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 (npos<ksel)
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<<(b1);
}
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;
}
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.

 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.

 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!

 New poster
 Posts: 8
 Joined: Fri Jul 25, 2014 2:04 am
Re: 1047  Zones WA
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 wrote:Print a blank line after each test case, including the last one.

 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!

 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.

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 1047  Zones WA
Input:AC output:
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
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!

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

 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!
Re: 1047  Zones
Got AC. Thank you so much Brianfry. I need to read the output format better next time.