Processing math: 100%

Friday, October 17, 2014

a bit of cf: Codeforces Round #273 (Div. 2)

Problem B:
478B. Random Teams

Summary:
Divide N people into M groups, each group has at least one person. Find the minimum and maximum total number of pairing of people in the same group amongst all groupings.

Solution:
Haven't prove this yet:
Maximum is when M-1 groups have one person, and the last group has N-M+1 person.
Minimum is when M groups have equal number of people (or as evenly distributed as possible).



Problem C:
478C. Table Decorations

Summary:
Given 3 type of balloons with amount (r,g,b), find the maximum number of tables each with 3 balloons of different color drawn from (r,g,b).

Solution:
There is a one liner to solve this problem (wow) but my approach is using binary search:
First sort the (r, g, b) into descending order a0,a1,a2. For each target number of tables T, we check:
1. if Ta0 then if we can fill all 2T table with a0, and if the rest of T can be filled with a1+a2, then T is reachable, otherwise we must lower T.
2. else 2Ta0. Then we check, if Ta0, if so if we can fill in all 3T with a0+a1+a2, then T is reachable, otherwise lower T. Lastly, if T>a0, then a0+a1+a2 is less than 3T, hence unreachable.

Problem D:
478D. Red-Green Towers

Summary:
Given r red blocks and g green blocks, and T(h) is a tower of height h. Recursive definition of T:
1. T(1) is a tower with one block of either red or green color.
2. T(h) consists of a base of h blocks of all green or red colors and T(h-1) on top of the base.
If h is the tallest tower possible, find the number of ways to build that tower. (r,g200000)

Solution:
Firstly we need to notice that:
A tower of height h can be built using any number of red and green blocks r and g that satisfies r+g=h(h+1)2
Proof by induction:
Let Sh be the set of pairs of r, g that can form tower of height h.
Firstly for h = 1, we have (0, 1) and (1, 0) in S1.
Given h>1, we can built Sh from Sh1 by doing the following:
- for each pair (r, g) in Sh1, add h such that (r+h, g) and (r, g+h) is in Sh. This is true since if we can build a tower of heigh h-1 using (r,g), then we can build tower of h using (r+h, g) and (r, g+h) too.
- Notice that (r,g) ranges from 0 to (h-1)*(h)/2, and after proving that the new r in Sh ranges from 0 to h * (h+1)/2 (which is easy to intuitively deduct), the inductive proof is completed.

Now comes the dynamic programming to find the number of ways to build the tower, which is demonstrated by the following implementation:


#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

/*
H is the maximum height possible using r and g blocks
w[h][r] = number of ways to build tower of height h with r red blocks
for each h, g can be inferred from h and r: g = h*(h+1)/2 - r
w[h][r] = w[h-1][r-h]  {if r > h}
        + w[h-1][r]    {if g > h} 

then since each h only uses the row h-1, we can save more space but
the order of iteration of r becomes important.
*/

int mod = (int) 1e9 + 7;
int R, G;
int dp[200003];   

int main(){
    cin >> R >> G;
    int H;
    for(int i=1;i<=1000;++i){
        if( (i*(i+1))/2 > R+G ) {
            H = i-1;
            break;
        }
    }
    if(R > G) swap(R,G);
    dp[0] = dp[1] = 1;
    for(int h=2;h<=H;++h){
        int cur = (h*(h+1))/2;
        for(int r=R;r>=0;--r){
            int tmp = 0;
            if(r-h>=0) tmp = (tmp + dp[r-h])%mod;
            if(cur-r-h>=0) tmp = (tmp + dp[r])%mod;
            dp[r] = tmp;
        }
    }
    int ans = 0, tow = (H*(H+1))/2;
    for(int r=R;r>=0 && tow-r<=G;--r){
        ans = (ans + dp[r])%mod;
    }
    cout << ans << endl;
    return 0;
}

No comments:

Post a Comment