SRM 657

I guess I just solved the div1 easy. Tried the div1 medium, modulos, modulos , modulos. But I finished the div1 easy editorial, you can find it at http://apps.topcoder.com/wiki/display/tc/SRM+657. Or here, because really, why not:

The problem consists of 6 variables: E, EM, M, MH, H, they are the number of problems you can use in problem sets. Each problem set needs an Easy, A Medium and a Hard problem to be used. E,M and H problems MUST be used as easy, medium or hard, respectively. There are EM problems that can be either easy or medium and MH problems that can be either Medium or Hard. What is the maximum number of problem sets you can make without repeating any problem? Oh, and each variable is a integer as long as `10^18`.

Two decisions are involved in this problem:

• Of the EM problems that can be easy or medium, how many will be assigned as medium? Let that number be `a`
• Of the MH problems that can be medium or hard, how many will be assigned as medium? Let that number be `b`

When `a` and `b` are known, we can calculate the number of problems of each difficulty we have available:

• `E + ("EM" - a) ` easy problems.
• `M + a + b` medium problems.
• `H + ("MH" - b) ` hard problems.

To have a problem set we need one of each kind of problems, so the maximum problem sets is `min(E + "EM" - a, M + a + b, H + "MH" - b)`.

Imagine we wanted to see if it is possible to have `x` problems in total:

• If `E + "EM" < x`, no matter what value of `a` we pick, the number of easy problems would be too small.
• If `E + "EM" >= x`, then there are normally enough easy problems unless `a` becomes too large. We can find the maximum allowed value of `a`: `M_a = x - E + "EM"`. Also `a` cannot be larger than `"EM"`
• Similarly, `H + "MH"` must be at least `x` and `M_b = x - H - "MH"` is the maximum allowed value for `b`.
• We just need `M + a + b` to be at least `x`, imagine we take the maximum allowed values: if `M + M_a + M_b >= x` then we can know `x` is a valid number of problem sets

Now note that if a value of `x` is allowed, then so will all smaller values and if a value of `x` is not allowed , no value larger than `x` will be allowed. So we can use Binary Search to find the maximum allowed value for `x`, this is the maximum possible number of problem sets.

    
long allowedX(long E, long EM, long M, long MH, long H, long x)
{
    if (E + EM < x) {
        return false;
    }
    long aa = std::min(EM, E + EM - x); //maximum a
    if (H + MH < x) {
        return false;
    }
    long bb = std::min(MH, H + MH - x); //maximum b
    return (M + aa + bb >= x); 

}

long maxSets(long E, long EM, long M, long MH, long H)
{
    // We have to maximize:
    // min(E + EM - a, M + a + b, H + MH - b)
    // where 0 <= a <= EM , 0 <= b <= MH
    long lo = 0; // we know 0 is allowed
    long hi = M + MH + 1; // we know this will never be allowed
    while (lo + 1 < hi) {
        long x = (lo + hi) / 2;
        if (allowedX(E,EM,M,MH,H, x)) {
            lo = x;
        } else {
            hi = x;
        }
    }
    return lo;
}

That was the solution in the editorial, but I prefer my lambda solution:

long maxSets(long E, long EM, long M, long MH, long H)
{
    // We have to maximize:
    // min(E + EM - a, M + a + b, H + MH - b)
    // where 0 <= a <= EM , 0 <= b <= MH
    return BinarySearch<long>( 0LL, H + MH + 1,  [&](long x) {
            if (E + EM < x) {
                return false;
            }
            long aa = std::min(EM, E + EM - x); //maximum a
            if (H + MH < x) {
                return false;
            }
            long bb = std::min(MH, H + MH - x); //maximum b
            return (M + aa + bb >= x); 
    });
}

It uses this Binary Search library function because it is funny to use functions as arguments.

// Library code
// takes lo, hi, P() such that:
// P(lo) is true
// P(hi) is false
// If P(x) is true and (x > y) then P(y) is true
// If P(x) is false and (x < y) then P(y) is false
// returns the maximum x such that P(x) is true
template<class D> D BinarySearch(D lo, D hi, std::function<bool(D)> P) {
    while (lo + 1 < hi) {
        D ha = lo + (hi - lo) / 2;
        if (P(ha)) {
            lo = ha;
        } else {
            hi = ha;
        }
    }
    return lo;
}