USACO FEB08 Problem 'cgame' Analysis

by Richard Peng

The first observation we can make is that the dimensions are independent of each other. So the problem is essentially the following:

• Given N numbers, divide them into two groups such that the sum of the two groups is as close as possible.
• This is the well-known knapsack problem, but the bounds of this problem makes the 'standard' DP approach not viable. That's the reason this problem is output only and the solution is by hacking.

There are, of course, many ways to hack this. My code used three techniques, which are:

• If N is small, try all possibilities.
• Sort the numbers in decreasing size order, then loop through them and assign numbers to the group with smaller sum.
• After the previous step, run many iterations of the following:
  • pick two numbers, one from each group
  • if swapping them decreases the difference, swap with high probability,
  otherwise, swap with low probability.

These three can get most of the points in a few seconds of CPU time. There are a few other interesting techniques that's worth trying. Most are variants of three where instead of swapping two elements, the groups are broken into 'chunks' and swapped either greedily or using something along the idea of second step. The following is another interesting approach suggested by John Pardon:

Suppose we want to partition a set of positive numbers into two sets of similar size. Create a graph whose vertices are these numbers. Also, each component of the graph will have a 'potential', initially equal to the value of the only vertex in each component. Each component also has a 'head'. Iteratively, take the to components with the highest potential. Insert an edge between their heads, make the potential equal to the difference of the previous potentials, and make the new head the head of the component whose initial potential was greater. Eventually there is one component, a tree. Two-coloring this tree gives an excellent partition.

One possible code to compute the answers from our contest director:

#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<set>
using namespace std;

#define K 2000000
#define lint long long

lint N, Nr[2],ar[2][50000];
lint L[50000][2];
set< pair<lint, lint> > S;

lint abso(lint x) {
    return x<0?-x:x;
}

int main() {
    lint i,j,r,k,diff,dis,tn;
    freopen("cgame.in","r",stdin);
    freopen("cgame.out","w",stdout);
    srand(time(0));
    scanf("%d %d",&tn,&N);
    N--;
    for(i=0;i<N;i++) {
        scanf("%d %d",&L[i][0],&L[i][1]);
    }
    if(N<=30) {
        for(r=0;r<2;r++) {
            for(k=0;k<(1<<N);k++) {
                dis = 0;
                for(i=0;i<N;i++) {
                    ar[r][i] = (k&(1<<i))==0?1:-1;
                    dis+=L[i][r]*ar[r][i];
                }
                if(dis==0) break;
            }
        }
    } else {
        for(r=0;r<2;r++) {
            
            for(i=0;i<N;i++) {
                S.insert(make_pair(-L[i][r],i));
            }
            
            Nr[0]=Nr[1]=0;

            for(i=0;i<N;i++) {
                pair<int,int> t = *S.begin();
                S.erase(t);
                if(Nr[0]>Nr[1]) {
                    ar[r][t.second]=1;
                    Nr[1]-=t.first;
                } else {
                    ar[r][t.second]=-1;
                    Nr[0]-=t.first;
                }
            }
            
            dis = Nr[0]-Nr[1];

            for(k=0;k<K;k++) {
                i=j=0;
                while(ar[r][i]==ar[r][j]) {
                    i = rand()%N;
                    j = rand()%N;
                }
                if(ar[r][i]==1) i^=j^=i^=j;
                diff = L[i][r]-L[j][r];
                if((dis>0&&diff>0)||(dis<0&&diff<0)) {
                    if(abso(dis-2*diff)*exp(-K/(k+1.0)-1)<=abso(dis)) {
                        dis -= 2*diff;
                        Nr[0] -= diff;
                        Nr[1] += diff;
                        ar[r][i]=1;
                        ar[r][j]=-1;
                    }
                }
            }

        }
    }
    printf("#FILE cgame %d\n",tn);
    i=j=0;
    for(k=0;k<=N;k++) {
        printf("%I64d %I64d\n",i,j);
        i += L[k][0]*ar[0][k];
        j += L[k][1]*ar[1][k];
    }
    return 0;
}