SRM 536 DIV2

It's been a long time since I posted my last blog.

Google Code Jam Korea kept me busy, and the fact that the average page view of my blog is about 8 kept me from investing my time to this blog.

Maybe, one day, this blog becomes useful to some people. If anybody happens to visit this blog, please let me know that you were here by leaving comments. Simple "Hi" or "I read your blog. Nice." will be enough.

So many people solved 250 and 500, and so did I.  It looked like fast submission was key to getting a high rank.
After today's SRM, I became blue again, and got back to DIV 1.


250 - BinaryPolynomialDivTwo

Summary
The problem asks us to calculate binary polynomial P for given array of coefficients, A.
If P(x) == 0, it is called "root".
If P(x) == 1, it is not a "root".
We need to find out how many roots are possible, given that x is either 0 or 1.

Approach
Note that pow(0,0) is 1 , and pow(0,i) is 0  for 0 < i
So, P(0) is 1 if and only if A[0] is 1.

For P(1),  pow(i,1) is 1 for all i.
So let sum = number of coefficient 1 in A.
P(1) = (sum%2 == 0) ? 1 : 0;

Source Code

1:    
2:  int BinaryPolynomialDivTwo::countRoots(vector <int> a) {  
3:         
4:    int one = 0;  
5:    int N = a.size();  
6:    int ans = 0;  
7:      
8:    if(a[0] == 0) ans++;  
9:      
10:    REP(i,0,N)  
11:      if(a[i] == 1) one++;  
12:    
13:    if(one%2 == 0) ans++;  
14:      
15:    return ans;  
16:  }  

500 - RollingDiceDivTwo

Summary
Every time we through the same number of dice, and each dice has different number of faces.
Every time we through, we record which face of each dice showed up. However, we do not record them in order.
For example, we may record faces of
(dice1, dice2, dice3)   in the first round, but
(dice3, dice1, dice2)  in the second round.
In other words, the order of faces of dices written are completely random.
We need to find the minimum possible total number of faces of all dice.


Approach
We can use greedy algorithm.
1. For each recorded round, sort the record in non-decreasing order.
    Now, for each round i, rolls[i][0] <= rolls[i][1] <= rolls[i][2] ..

2. For each "column," find the maximum number of faces.

3. The maximum number of faces for each record column is the minimum possible total number of faces.


Source Code

1:    
2:  int RollingDiceDivTwo::minimumFaces(vector <string> rolls) {  
3:         
4:    int R = rolls.size();  
5:    int C = rolls[0].size();  
6:      
7:    vector< vector<int> > dice(R, vector<int>(C,0));  
8:      
9:    vector<int> maxFace(C,0);  
10:      
11:    REP(i,0,R)  
12:    {  
13:      REP(j,0,C)  
14:      {  
15:        dice[i][j] = (rolls[i][j] - '0');  
16:      }  
17:      sort(dice[i].begin(), dice[i].end());  
18:      REP(j,0,C)  
19:      {  
20:        maxFace[j] = max(maxFace[j], dice[i][j]);  
21:      }  
22:    }  
23:    int ans = 0;  
24:    REP(i,0,C)  
25:    ans += maxFace[i];  
26:      
27:    return ans;  
28:  }  
29:    

1000 - MergersDivTwo
Summary
Problem statement is very direct about what it wants. I think the statement itself is good enough.


Approach
The problem is asking for "maximum possible revenue of the final company that can be created in any series of mergers that joins all the companies."
Note the words "maximum" and "possible."
Do you see that it can be rephrased as "pick the maximum value among all possible outcomes" ?

Now, it is clear that we need to try all possible values, but also note that we can be "smart" about trying possible outcomes if we make some observations.

Observation 1 : It is always better to merge companies with higher revenue later.
Reasoning.
Say we are merging K companies from c1 to cK.
And let maxC = company with maximum revenue in [c1,cK]
             RES = result revenue after merging operation
Then it is obvious that after merging operation, RES <= maxC.
Also note that RES will be lower if elements in [c1, cK] have lower values.
So, in order to maximize RES, we want the revenues of companies included in merging operation to be as high as possible.
Let T = the last merging operation.
Then to maximize our answer, companies in T must have highest revenues possible.
Then the company with the maximum revenue should be included in T,
and the company should not be included in previous merges because it will decrease its revenue.
Keep applying the same logic to the company with the second highest revenue, and so on.


From observation 1, we know that we have to sort companies in non-decreasing order by their revenues.

Now, what we are not sure about is how many companies we should merge at each step. After all, the problem statement said we need AT LEAST K companies to merge, not EXACTLY K companies.
This is where "trying all possible values" come in.
We try merging C companies where K <= C.
And, we use array to store the current best value.

I explained the procedure in detail in my source, using comments.


Source Code

1:  double MergersDivTwo::findMaximum(vector <int> revs, int K) {  
2:         
3:    int N = revs.size();  
4:    double dp[N]; //d[i] = best result after merging operations [0...i]  
5:    double sum[N]; //sum[i] = sum of revenues inside [0, i]  
6:    sort(revs.begin(), revs.end());  
7:      
8:    sum[0] = revs[0];  
9:    for(int i=1; i < N; i++)  
10:      sum[i] = sum[i-1] + revs[i];  
11:      
12:    for(int i = K-1; i < N; i++)  
13:      dp[i] = sum[i] / double(i+1); //default value is merging [0,i] companies altogether.  
14:      
15:    /*  
16:     At each iteration, we have two options  
17:     1) Keep the current dp[j]  
18:     2) Merge all companies between [i,j]   
19:     Note that after first merge, we always one "previously merged company",   
20:     so we only need (K-1) companies to meet the minimum company number requirement.  
21:     */  
22:    for(int i = K; i < N; i++)  
23:      for(int j = i + (K-1) - 1, cnt = K; j < N; j++, cnt++)  
24:        dp[j] = max(dp[j], (dp[i-1] +sum[j] - sum[i-1])/double(cnt));  
25:      
26:    return dp[N-1];  
27:  }  
28: