SRM 601: Another slow day

At least it wasn't catastrophically bad this time.

Div1 250 - The one with apples and organges

You have `n <= 50` bags. Bag `i` has apples[i] apples and oranges[i] oranges. The process to make a valid gift involves taking exactly X fruit (`X > 0`) from each bag (The number of apples and oranges you take from each bag must be exactly X). The number of apples and oranges determines the kind of gift you make. Count the total number of different kinds of gifts you can make, that is, the total number of distinct pairs `(A,O)` where `A` is the number of apples and `O` is the number of oranges.

The trick is to notice that the value of `X` you pick uniquely determines the sum `(A + O = nX)`, which means that it is impossible to get the same pair using two different values of `X` . The problem is now about counting the number of pairs for each `X`.

Given `X`, then the number of apples you get in total uniquely determines a pair `(O = A - nX)`, so we just need to count the total number of ways to pick `A` given `X`

The next important fact is to notice that the set of valid `A` values ought to be a interval. So if you know `a_0` and `a_1` are valid and `a_0 <= a_1` , then all `a_0 <= i <= a_1` must be valid too. Then you just need to find the minimum and maximum possible number of apples. The maximum can be found by picking the largest possible number of apples from each bag. The minimum number of apples can be found by picking the largest number of oranges from each bag. Once you get the minimum and maximum number of apples, just subtract them to count the total number of ways to pick it.

long getNumber(vector<int> apple, vector<int> orange)
{
    int n = apple.size();
    int m = 2000000;
    for (int i = 0; i < n; i++) {
        m = std::min(m, apple[i] + orange[i]);
    }
    long res = 0;
    
    // For each valid X:
    for (int X = 1; X <= m; X++) {
        // If we take X, then there are nX in total.
        
        // maximum:
        int mx = 0;
        for (int a: apple) {
            mx += std::min(X, a);
        }
        // minimum:
        int mn = 0;
        for (int o: orange) {
            mn += std::max<int>(0, X - o );
        }
        // total:
        if (mx >= mn) {
            res += mx - mn + 1;
        }
    }
    return res;
}

Div1 500: The one with xor

I couldn't think of a solid solution. I did make the conclusion that you can first pick the first bit position at which the xors differ. Then the problem is about counting the number of ways to have xors: yyyyy1????? and yyyyy0?????. It seems this is the starting point of a solution, but no luck yet.

Comments?

So far it seems like an ok match. Time to write the editorial. Got to rush because I don't want to be busy with it during Christmas. ... Or do I?