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 \(a_0, a_1, a_2\). For each target number of tables T, we check:
1. if \(T \leq a_0\) then if we can fill all \(2T\) table with \(a_0\), and if the rest of \(T\) can be filled with \(a_1+a_2\), then T is reachable, otherwise we must lower T.
2. else \(2T \geq a_0\). Then we check, if \(T \leq a_0\), if so if we can fill in all \(3T\) with \(a_0 + a_1 + a_2\), then T is reachable, otherwise lower T. Lastly, if \(T > a_0\), then \(a_0 + a_1 + a_2\) 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,g \leq 200000\))

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 = \frac{h(h+1)}{2}\)
Proof by induction:
Let \(S_h\) 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 \(S_1\).
Given \(h > 1\), we can built \(S_h\) from \(S_{h-1}\) by doing the following:
- for each pair (r, g) in \(S_{h-1}\), add h such that (r+h, g) and (r, g+h) is in \(S_h\). 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 \(S_h\) 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;
}