TopCoder Open 2012 - Round 1B

All round 1 are held in 1:00AM  in my country.

So I have to either stay up late or sleep early and wake up to participate in the match.

In round 1A, I stayed up, and it was very tiring for me.

So this time, I decided to sleep early. How did it turn out?

When I woke up, the match was already over. OMG...

Nevertheless, I went to the practice room and tried to solve all problems.

Problems looked somewhat easier than the previous match (1A). What surprised me was that the cutoff for this match is a lot lower than 1A even though it seemed easier than the last match. I really should've participated in the match.

I solved 250 and 500 on my own, and got the correct answer.

I had trouble solving 1000, so I ended up looking at writer's solution, which was a lot simpler than I thought.

250 - FoxAndKgram

Approach

Let's turn this into a simpler problem.

Q1 : If we know the value of k (as in k-gram), is it possible to make it?

Note that we do not need to use all pencils, which means we can try the greedy approach.

Step 1) Find all pencils whose length is equal to k.

Step 2) Excluding pencils found in Step 1, find all pairs of pencils who sum is (k-1)

If number of pencils found in Step 1 and number of pairs of pencils found in Step 2 is bigger than or equal to k, it is possible.

Let N = number of pencils.

Then the above greedy approach takes O(2*N), or O(N), which is good enough considering the small constraint for N : 1 <= N <= 50

Now that we've found an efficient way to answer Q1, we can simply try all possible values of k.

Note that 1 <= k <= number of pencils. In other words, k cannot be higher than the number of pencils.

Proof : Yang takes one pencil, Yin takes two pencils, and each row has to be either Yang or Yin.

So each row needs at least one pencil, which means the maximum number of rows we can possibly create is the number of pencils.

So we basically try all possible k, and see if the current value for k is correct.

The overall running time is O(N) * O(N) = O(N^2)

Source Code

1:  bool isPossible(int);  
2:  vector<int> len;  
3:  int N;  
4:    
5:  int FoxAndKgram::maxK(vector <int> leng) {  
6:      
7:    len = leng;  
8:    N = len.size();  
9:    int res = 0;  
10:      
11:    for(int k=1; k <= N; k++)  
12:      if(isPossible(k))  
13:        res = k;  
14:      
15:    return res;  
16:  }  
17:    
18:  //return true if k is a valid k-gram value  
19:  bool isPossible(int k)  
20:  {  
21:    int res = 0;  
22:    vector<bool> used(N,false);  
23:      
24:    //find Yang  
25:    for(int i=0; i < N; i++)  
26:      if(len[i] == k)  
27:      {  
28:        used[i] = true;  
29:        res++;  
30:      }  
31:      
32:    //find Yin  
33:    for(int i=0; i < N; i++)  
34:      for(int j=i+1; j < N; j++)  
35:        if(!used[i] && !used[j] && (len[i] + len[j] + 1) == k)  
36:        {  
37:          used[i] = used[j] = true;  
38:          res++;  
39:        }  
40:      
41:    return res >= k;  
42:  }  
43:    

500 - FoxAndDoraemon

Approach

This can be solved using dynamic programming if we make a few key observations.

Observation 1 : It is optimal to start the longest work first.

Observation 2 : It is optimal to use the split hammer on all available foxes.
Explanation : This is an easy to miss observation. Note that the effect of the split hammer is instantaneous, which means it is possible to use the split hammer on multiple foxes at the same time (You can confirm this observation by looking at test case 1). We have problems when we have less foxes than we need, which means more foxes means better.

Let N = number of works.

Using Observation 1, let's sort all works in ascending order, and start by taking (N-1)th work.

Let's start doing dynamic programming.
Recurrence.
When processing (i)th job, we have two options
1) Split fox
2) Start the current job

Note that option 1) is unnecessary when you have more foxes than you need.
Als note that it is unwise to choose option 2) when you have only one fox left and there are more than moe jobs left.

State.
dp[i][j] = minimum number of time required to finish all jobs when there are [0...i) jobs left with j foxes.

Source Code

1:    
2:  const int maxN = 55;  
3:  int dp[maxN][maxN*2];  
4:  int N;  
5:  int splitC;  
6:  vector<int> workC;  
7:    
8:  int rec(int,int);  
9:  int FoxAndDoraemon::minTime(vector <int> workCost, int splitCost) {  
10:      
11:    sort(workCost.begin(), workCost.end());  
12:    N = workCost.size();  
13:    splitC = splitCost;  
14:    workC = workCost;  
15:       memset(dp, -1, sizeof(dp));  
16:      
17:    return rec(N-1, 1);  
18:  }  
19:    
20:  int rec(int jobs, int fox)  
21:  {  
22:    if(jobs == -1) return 0;  
23:      
24:    int& val = dp[jobs][fox];  
25:    if(val != -1) return val;  
26:    val = 0;  
27:      
28:    if( (jobs+1) <= fox) val = max(workC[jobs] , rec(jobs-1, fox-1));  
29:    else  
30:    {  
31:      //split fox  
32:      val = splitC + rec(jobs, fox + 1);  
33:        
34:      if( !(fox == 1 && jobs > 0) )  
35:        val = min(val, max(workC[jobs], rec(jobs-1, fox-1)));  
36:    }  
37:    return val;  
38:  }  
39:    

1000 - FoxAndPhotography

Approach

This problem can also solved using dynamic programming.
For each person in the first row, we need to determine where to put him.

Let N = number of members in heightsFront.

State
mask
= it is a bitmask representing which column has been taken care of.
= (i)th bit is 0 if (i)th column needs to be processed, and 1 if it is already processed.

dp[mask] 

= minimum number of swaps needed when the current state is mask.

Recurrence
At each state (mask, cur) where cur represents the current member of the first row we are looking at,
we need to decide where to put this guy.
Go through each member of the back row, and if the (i)th member of the back row is not processed and is taller than the current member of the first row, try putting the current guy in front of the (i)th person in the back row. Keep doing this until we assigned all members of the first row to their appropriate slots.
Now, you might be wondering below two questions.

Q1) It seems like the state consists of two variables : mask and cur. Then why are we not using "cur" in  dp, i.e. dp[mask][cur] ?
We start at mask = 0 (No front person is assigned to any position), and at each iteration, we assign one front person to a position, making one of N bits in mask 1.  Then (cur) is simply (N - number of unset bits in mask). So we really do not need to store "cur" as it is already encoded in mask.

Q2) How do we calculate how many swaps we need at each iteration?
At each iteration, the member in the first row who was originally at position (cur) is actually at the first unprocessed position of the back row. Let's take a look at test case 2.  I will color currently processed member blue, processed member red, and unprocessed member black.
Original position of the first row
140 141 142 143

Swapping process
 140 144 142 143
=> 141 140 142 143
=> 141 142 140 143
=> 141 142 143 140
=> 142 141 143 140
=> 142 143 141 140
=> 143 142 144 140
=> 143 142 144 140

So if we want to put the current member at (i)th position, the minimum number of swaps required is (number of unprocessed elements before i).

Source Code

1:    
2:  int dp[1<<16];  
3:  int N;  
4:  int INF = (15*16)/2 + 10;  
5:  vector<int> hF;  
6:  vector<int> hB;  
7:    
8:  int rec(int,int);  
9:    
10:  int FoxAndPhotography::getMinimumSwaps(vector <int> heightsFront, vector <int> heightsBack) {  
11:         
12:    hF = heightsFront;  
13:    hB = heightsBack;  
14:    N = hF.size();  
15:      
16:    memset(dp, -1, sizeof(dp));  
17:    int res = rec(0,0);  
18:    if(res >= INF) return -1;  
19:    return res;  
20:  }  
21:    
22:  int rec(int mask, int cur)  
23:  {  
24:    if(cur == N) return 0;  
25:      
26:    int& val = dp[mask];  
27:    if(val >= 0) return val;  
28:      
29:    val = INF;  
30:    int prev = 0;  
31:    for(int i=0; i < N; i++)  
32:    {  
33:      //If (i)th member in backrow is not taken care of,  
34:      //and if the person at position 'cur' at front row is  
35:      //shorter than (i)th person in backrow, try swappping.  
36:      if( (mask & (1<<i)) == 0)  
37:      {  
38:        if(hF[cur] < hB[i])  
39:          val = min(val, prev + rec( mask + (1<<i) , cur+1));  
40:        prev++;  
41:      }  
42:    }  
43:    return val;  
44:  }