## Problem J - World Finals 2005

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
mafattah
New poster

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

### 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.
Per
A great helper

Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

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).
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?
Per
A great helper

Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

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

Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

### problem D

while we are at a discussion about problem J, can some one tell me a hint for problem D?

btw, was that Kismans? Its sad that judges don't sign their problem in the world finals

abishek
Experienced poster

Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

I don't know who was the problem author of D, but I know it was not Derek Kisman (he said none of the finals problems were from him).
Guru

Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Here's how we did problem D:

First, finding the number of shuffles is fairly easy.

Then, we construct a permutation P based on the "misplaced" elements of the input (if the element at the place where we should have an A was B (where we might have B = A), this permutation maps A -> B).

Next we look at the cycle structure of P. The assumption of our solution which we never proved but which seems innocent enough if you think about it a while is that any two elements which have been accidentally swapped in an error in one of the shuffles must be in the same cycle of P. Matching this against pairs of elements which were actually adjacent during the performed shuffles, we get a relatively small set of possible errors which could have been made.

Then, finally, we simply do an exhaustive search among these (relatively few) possible errors to find the way using as few errors as possible.
Per
A great helper

Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

By the way, regarding the problem set: despite us not doing as good as we had hoped, I really enjoyed the problem set, it was definitely one of the better ones I've seen (and I've seen quite a few by now ).
Per
A great helper

Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

the problem set was very good and I really enjoyed it, though I should crib saying that too much of geometry was there. A, B, E, F, G all had some kind of floating point operations involved and I have always hated floating point numbers

abishek
Experienced poster

Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

I would be very grateful if someone gives hints to problems C and I...(am I asking for too much??).
mido
Learning poster

Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt

problem C is very similar to a topcoder problem; for an idea for the solution read the description of the solution for topcoder problem Triptych: http://www.topcoder.com/index?t=statist ... nline_rd_4
And problem I can be solved with greedy in O(n^2)
If I said something wrong, please someone who participated in the finals correct me.
Guru

Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

### hmm

abishek Said
"the problem set was very good and I really enjoyed it, though I should crib saying that too much of geometry was there. A, B, E, F, G all had some kind of floating point operations involved and I have always hated floating point numbers "

F had nothing to do with floating point number. Although at first sight I also thought that floating point number is a must for this problem. As far as I know that G had nothing to do with floating point number as well. G was the hardest problem according to derek (he solved all the problems I didn't). Voronoi diagram was not required for B. I guess some teams did not touch it considering that they need to implement V diagram.

The Author of D was Bonomo.
shahriar_manzoor

Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

Per wrote:By the way, regarding the problem set: despite us not doing as good as we had hoped, I really enjoyed the problem set, it was definitely one of the better ones I've seen (and I've seen quite a few by now ).

I quite agree and said so at the coaches' briefing. I believe there was general consensus.
gvcormac
Problemsetter & Reviewer

Posts: 194
Joined: Fri Mar 15, 2002 2:00 am

### Re: hmm

shahriar_manzoor wrote:Voronoi diagram was not required for B. I guess some teams did not touch it considering that they need to implement V diagram.

I think we need to find the number of intersections of the road with vornoi boundaries in problem B. But I don't see how to find it without the vornoi diagram itself.

May be I missed it but where the judges ever called to the stage or introduced at the finals?
I don't think so. (except for the price winning ceremony where judges just accompanied the teams)

abishek
Experienced poster

Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

Next

### Who is online

Users browsing this forum: No registered users and 0 guests