Topcoder open 2012: Round 1B

I have posted my TCO 2012 post about round 1B: http://community.topcoder.com/tco12/algorithm-track-round-1b/

Bonus comments:

• I think the best way to describe the problem set is intense. I really liked it. I solved all problems, but it made me feel like I had worked hard to get it rather than making me feel it was an easy problem set
• The guessing contest seems to have been a popular idea. But it is going to be hard to compute all those results after each round. Today it really took me much longer than needed.
• The recurrence for 1000 is as follows f(p, subset). p is the number of left-most back seats that have already been matched. subset contains all the front seats that are already matched (each to one of those p seats). Then, for position #p, you just have to pick a front seat not in the subset that can be moved to #p, calculate the cost to move it and recurse to f(p+1, subset union (picked seat)). You can then optimize this recurrence by noticing that #p is always equal to the length of the subset. And of course, the usual trick to use bitmasks to represent subsets.
• Cute code for the problems:

#define for_each(q, s) for(typeof(s.begin()) q=s.begin(); q!=s.end(); q++) 
struct FoxAndKgram 
{ 
    int maxK(vector <int> len) 
    { 
        map<int,int> cnt; 
        // Number of pencils of each length: 
        for_each(x, len) { 
            cnt[*x]++; 
        } 
        for (int k = 50; k >= 1; k--) { 
            int allowed = cnt[k]; //can use all pencils of size k 
             
            // for each pair (i,j) such that (j > i) and i + j = k - 1: 
            for (int i=1; (i < k) && (k - 1 - i > i); i++) { 
                allowed += min(cnt[i], cnt[k-1-i]); 
            } 
            // if odd, we can use two k/2 pencils in each row 
            if (k % 2 == 1) { 
                allowed += cnt[k/2]/2; 
            } 
            // k is valid if : 
            if (allowed >= k) { 
                return k; 
            } 
        } 
        return 0; 
    } 
}; 

struct FoxAndDoraemon 
{ 
    int minTime(vector <int> workCost, int splitCost) 
    { 
        int n = workCost.size(); 
        sort(workCost.rbegin(), workCost.rend()); 
        // need to split n-1 times. 
        // tree shape?              Third example needs 2nd tree shape 
        //           o            But in other times, it is possible we need 
        //          / \          The first one. 
        //         o   o 
        //        / \ / \  .. 
        //        o o o o 
        // vs. 
        // 
        //           o 
        //          / \   .. 
        //         o   o 
        //        / \                        .. 
        //        o o            ? ?  ? 
        //       / \                          .. 
        //      o   o 
        // 
        // max time  is 50*3600 + 50*3600 
        // linear search? 
         
        // Binary search works too, but is not needed. 
        for (int t=1; t<=50*3600*2; t++) { 
            //Is it possible to do it in time = t? 
            // If at one time, we are forced to do a given homework instead 
            // of splitting, do homework. 
            int trees = 1; 
            int done = 0; 
            int current = 0; 
            while ( (done < n) && (trees > 0) && (current < t) ) { 
                while ( (done < n) && (current + workCost[done] + splitCost > t) ) { 
                    if ( (current + workCost[done] > t) || (trees <= 0) ) { 
                        // impossible time. Dijkstra... Forgive me! 
                        goto next; 
                    } 
                    trees -= 1; 
                    done++; 
                } 
                // split current trees 
                trees *= 2; 
                current += splitCost; 
                if (trees >= n - done) { 
                    break; 
                } 
            } 
            if (trees >= n - done) { 
                return t; 
            } 
            next:; 
        } 
        return -1; 
         
         
    } 
}; 

const int INF = 16*16*2; 
struct FoxAndPhotography 
{ 
    int dp[1<<16]; 
    vector <int> heightsFront; 
    vector <int> heightsBack; 
    int n; 
     
    int rec(int mask) 
    { 
        int & res = dp[mask]; 
        if (res == -1) { 
            int p = __builtin_popcount(mask); 
            if (p == n) { 
                res = 0; 
            } else { 
                res = INF; 
                // decide which front passager gets matched to  
                // back passenger #p  
                int behind = 0; 
                for (int i=0; i<n; i++) { 
                    if (!( (1<<i)&mask )) { 
                        if (heightsFront[i] < heightsBack[p]) { 
                            // There are {behind} people to the left of 
                            // person i. That is the cost to take her to 
                            // position #p. 
                            res = std::min(res, behind + rec(mask|(1<<i)) ); 
                        } 
                        behind++;                         
                    } 
                } 
            } 
        } 
        return res; 
    } 
     
    int getMinimumSwaps(vector <int> heightsFront, vector <int> heightsBack) 
    { 
        // it is only necessary to swap the people in one of the rows. 
        // swapping two persons in the front is equivalent to swapping the same 
        // two positions in the back 
        memset(dp, -1, sizeof(dp)); 
        this->heightsFront = heightsFront; 
        this->heightsBack = heightsBack; 
        n = heightsFront.size(); 
        int x =  rec(0); 
        return ( (x >= INF) ? (-1): x); 
    } 
};