SRM 605

A slow day. It was an 8:00 AM match and I may or may not have stayed up till 3:00 AM the day after writing a very bad editorial. So I wasn't at 100% speed.

250: The one with hamburgers

You are given taste[] and type[], each hamburger is of type type[i] and has a taste value taste[i]. The joy to eat is equal to the total sum of the hamburgers chosen multiplied by the number of distinct types eaten. What is the maximum joy? (Note multiple hamburgers may be of the same type and that taste[i] can be negative). We can choose to eat zero hamburgers, so result should never be negative.

Let's say you fix the number of types `y`, then we should find the `y` types with the maximum sums of tastes and sum those tastes together. Picking the best taste sum of each type is a separate problem of its own. Normally, you should pick all non-negative tastes . The only reason to pick a negative taste is when there are only negative tastes of a given type. In that case, you should only pick one negative number, the largest one (closest to 0). Sometimes, even though a type has negative sum, it is a good idea to try it because it increases the number of types.

The rest is to solve the implementation of finding the best possible sum of tastes for each type and then the best sum of `y` types. I used the STL which makes everything cute:

int getNumber(vector<int> type, vector<int> taste)
{
    // first of all, save all tastes for each type.
    map<int, vector<int> > typeTastes;
    for (int i = 0; i < type.size(); i++) {
        typeTastes[ type[i] ].push_back(taste[i]);
    }
    vector<int> tasteResult;
    // for each type:
    for (auto &q: typeTastes) {
        auto &p = q.second;
        // sort tastes in non-increasing order:
        sort(p.rbegin(), p.rend());
        // Find the best sum, try to get all the non-negative numbers
        int s = 0;
        int i = 0;
        while ( (i < p.size()) && (p[i] >= 0) ) {
            s += p[i];
            i++;
        }
        // sometimes all numbers are negative... 
        if (i == 0) { 
            s += p[0]; //pick the largest
        }
        //add this sum to the list of types:
        tasteResult.push_back(s);
    }
    // now try the best number of types:
    sort(tasteResult.rbegin(), tasteResult.rend());
    int res = 0, sum = 0;
    for (int i = 0; i < tasteResult.size(); i++) {
        sum += tasteResult[i];
        res = std::max(res,  (i + 1) * sum );
    }
    return res;
}

450: The one with sets

You have a set of all natural numbers from 1 to `2N`, inclusive. Partition the set in two sets of the same size such that, after sorting the sets, the absolute value of the difference of their i-th elements is at least `K`. Given `N <= 50` and `K <= 10`, count the total number of valid ways to pick these partitions.

As usual, I wasted most of my time coding a dynamic programming that was actually wrong. I didn't at first notice that the sets should be sorted ...

Anyway, the trick is that `K <= 10`. Assume you decide the contents of the sets going from highest integer to the lowest. You begin deciding the position of `n = 2N`, then `n = 2N-1` and so and so. You can represent the integers added to each set using two things: a) The number of integers whose difference with the current number is at least one in each of the two sets and b) The bitmasks representing the set of the other integers that went to each of the two sets. After some inspection, you only need one bitmask and one count, the other set's can be found using `N` and `n`.

Anyway, let's say you want to add `n` to set A. From the bit masks and counts there are four things we should know:

• `bA` : The number of bad numbers in A, numbers smaller than `n + K`.
• `bB` : The number of bad numbers in B, numbers smaller than `n + K`.
• `gA` : The number of good numbers in A, numbers that are at least `n + K`.
• `gB` : take a guess

Since `A` and `B` are sorted, you can assume that the last `bA + gA` spots in `A` are taken and the last `bB + gB` spots in `B` are taken.

If we want to add `n` to `A` one of the following must be true:

• The largest position in `A` will be matched to a good number in B
• The largest position in `A` will be matched to nothing in `B`.

I am pretty sure this logic is correct, but when I learned it I had only 8 minutes to implement it and it is quite complicated to.