## Saturday, April 07, 2012

### Topcoder open 2012: Round 1B

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

• 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);     } }; Bruno said...

Hi could you explain the solution for the 1000? I could not understand very clear, specifically that 'behind' counter :p
What if the p is ahead the position i? And what about the people already matched between p and i?

Thank you! vexorian said...

Yes, this is the part that took me the most time to do.

Let us imagine you have already decided that ABCD have to change their positions to DCBA, what is the minimum cost to do this?

You will eventually find that it is a good idea to first move D to his position, then C, then B. Or maybe the opposite and first A, then B, then C..

Let us say for front positions ABCDEFGH that one state is like this:

(2, ABxDExGH)

The x are people that we already moved to their locations, so the mask will be like 00100100. 2 is p in the explanation, but as an optimization, it will be equal to the number of 1 bits in the mask (subset).

So, in reality the state represents the following thing:

CF ABDEGH

C and F are already in their positions. You now have to decide which of ABDEGH to move to the third position. But note that the cost to move one of them to the third position depends on the number of people that have not moved to their seat yet. For example, if we want to move E to this position:

ABxDExGH There are 3 people between E and the third position (AB D) we ignore the people that are already in the subset (mask).

So the cost to move E by swapping is behind = 3.

Maybe I should have called that variable "totheLeft" instead of "behind"

After moving E, the stuff becomes ABxDxxGH, that means our new mask is 00101100. Bruno said...

Got it! Thanks once again ^^ trungda said...

class FoxAndPhotography {
public:
int dp[1<<16];
int n;
int front;
int back;

int cal(int subset) {
if (dp[subset] != 1000) return dp[subset];
int m = __builtin_popcount(subset);
int left = 0;
int ret = 1000;
for (int i = n - 1; i >= 0; i --) {
if (!(subset & (1 << i))) {
if (back[n - i - 1] > front[m]) {
ret = min(ret, cal(subset | (1 << i)) + left);
}
left ++;
}
}
dp[subset] = ret;
return ret;
}

int getMinimumSwaps(vector heightsFront, vector heightsBack) {
n = heightsBack.size();
for (int i = 0; i < n; i ++) {
front[i] = heightsFront[i];
back[i] = heightsBack[i];
}
for (int i = 0; i < 65536; i ++)
dp[i] = 1000;
dp[(1 << n) - 1] = 0;
int res = cal(0);
if (res == 1000) return -1;
return res;
}

Hi! I got your idea and try to implement. My implementation is almost the same with yours but I kept getting TLE for testcase which has 16 elements.
Would you mind explaining for me what I did wrong here ? vexorian said...

I think you initialize your dp with 1000, but then use it as infinite when picking the best result.

But if the test case does not have a solution, there will be many states that always stay marked with 1000, and thus you will keep executing those states and doing a lot of processing.

Just use 1000000 to mark a state as not-visited and 1000 to mark it as impossible.(initialize dp[i]=1000000 and ret=1000)

Amit Ruparel said...

I've been trying to read your explanation for the 500-pt and I still don't get it. Any chance you can elaborate more? Thanks! vexorian said...

It is not so important because there is an editorial with an easier solution already.

But anyway, without knowing what is it that you can't understand it is difficult to know what to elaborate.

Either way, let us say you begin with one Fox. Since we are in a rush, there is no reason to wait without doing nothing, so we have to decide: will the Fox reproduce or work on a task? If it splits, there will be two foxes left after some time, and each of the foxes can split or work. The other thing is that it is never necessary for a Fox to split after doing the homework. Because you can just swap the order of both processes and you will get either a better result or the same result.

So in fact, what we do is split fox after fox , some in parallel until we get n foxes left, then we do the homework.Whenever a Fox splits, we can see it as a node in a tree becoming two children. This means that the Foxes make a binary tree. You will notice that the shape of the tree will determine the total time. There are many different binary trees with n leaves.

So, how to find the optimal way? What I did was to sort the durations of the homework in non-increasing order and put time limit. After this time limit is set, then there is a point in time in which you need to stop splitting one of the nodes you got left and instead order it to do the available homework that takes the most time. (The homework duration + the current time exceed the time limit), so we order the Fox to do homework, we will get some Foxes and homework remaining, and we must continue until either all homework is done or there is a piece of homework that needs to be done but we could not reproduce enough Foxes (In which case, we need to increase the time limit and repeat). Amit Ruparel said...

I don't get the time concept. Why do you go through the loop with t from 1 to 3600*50*2. I realize 50 and 3600 are the max bounds over the number of jobs and the time for each job, but I don't get your concept. What does that 'time' and the time limit exceeding stand for?