SRM 588: ouch (Update)

As I write this, I have to go, I am scheduling this to be up the time the challenge phase ends.

Div1 medium: The one with keys

There are up to 12 rooms, each with some red and green locks (up to 10 of each kind). You can use red or white keys to open red locks and green or white keys to open green locks. Each key is consumed once you use it. Each room has keys inside. What is the maximum number of keys you can have?

I was at first trying to make a viable dynamic programming solution. Similar to a GCJ problem. But I was not able to optimize it.

I eventually settled for a brute force search. Whenever you decide to open a room, you should only use white keys if you NEED to. This approach was slow, so I optimized it using all the dirtiest tricks in the book. Let us see if it passes.

Update: Turns out it passes system tests, so I will explain it.

Try all permutations of the order in which you open the rooms.

If you decide to enter a room and you have enough red and green keys, then you simply shouldn't use white keys. You should always use as little white keys as possible. Turns out this is also the "key" to solve it using dynamic programming.

With this, your approach needs `O(n!)` time, 12! is high, but not very high. So we can try some optimizations.

Imagine that at a given moment, there is one room that can be opened and after opening it, you end up with at least as many keys of each type as before. Then you should always open this room. So you shouldn't try sequences in which this room isn't opened.

Another special case, there is a room that you can open, but after opening it you end up with less keys of each type. This room is never a good idea. Ignore it.

I think that the two previous optimizations are enough , I was about to submit this, but last second I decided I could do an extra optimization, give priority to moves that give the maximum number of total keys, and cut the search when we tried too many options. I am not sure this is necessary, but I put it just in case.. Update 2: Yeah, it turns out this optimization wasn't needed.

Before the match I found out std::function causes a bug in TopCoder. That was too bad, because since there is no sane way to have anonymous recursion in c++ without using it, I had to use an outside function for the backtracking. This meant I had to copy all 5 argument variables as class members. What a bore.

vector<int> doorR,doorG,roomR,roomG,roomW;
int n, best, options[12];

void rec(int p, int r, int g, int w)
{
    best = std::max(best, r + g + w);

    if (p < n) {
        //each tuple is (i, nr,ng,nb):
        tuple<int,int,int,int> results[n-p]; //possible options
        int t = 0;
        
        for (int i=p; i<n; i++) {
            // for each candidate options[i], find if it is possible,
            // save it in results
            int &x = options[i];
            int nr = r - doorR[x];
            int ng = g - doorG[x];
            int nw = w;
            if (nr < 0) {
                // Not enough red keys, use white keys
                nw += nr;
                nr = 0;
            }
            if (ng < 0) {
                // Not enough green keys, use white keys
                nw += ng;
                ng = 0;
            }
            if (nw >= 0) {
                // if the number of white keys is non-negative we can do it
                // Increase the number of keys
                nr += roomR[x];
                ng += roomG[x];
                nw += roomW[x];
                if ( nr >= r && ng >= g && nw >= w) {
                    // This move is always a good idea, we should do it:
                    swap(options[p], options[i]);
                    rec(p+1, nr,ng,nw);
                    t = 0;
                    swap(options[p], options[i]);
                    break;
                } else if ( nr > r || ng > g || nw > w) {
                    // Make sure the move is a good idea before adding it
                    results[t++] = make_tuple(i,nr,ng,nw);
                }
            }
        }
        // process tuples:
        for (int j=0; j < t; j++) {
            int i, nr,ng,nw;
            tie(i, nr,ng,nw) = results[j];
            swap(options[p], options[i]);
            rec(p + 1, nr, ng, nw);
            swap(options[i], options[p]);
        }
    } 
}

int maxKeys(vector <int> doorR, vector <int> doorG, vector <int> roomR, vector <int> roomG, vector <int> roomW, vector <int> keys)
{
    // copy stuff, this is tedious:
    this->n = doorR.size();
    this->doorR = doorR;
    this->doorG = doorG;
    this->roomR = roomR;
    this->roomG = roomG;
    this->roomW = roomW;
    best = 0;
    for (int i=0; i<n; i++) {
        options[i] = i;
    }
    rec(0, keys[0], keys[1], keys[2]);
    return best;
}

Div1 easy: The one with songs

You have T time available to play as many songs as you can. Each song has a duration and a tone. If the tones of two consecutive songs are `x, y` then you need to rest `abs(x-y)` time units before playing the second song. What is the maximum number of songs?

It took me too long to correctly code this solution. As usual, I waited till there were less than 10 minutes before opening this problem.

The trick is, let us say you decide to play some songs. If the minimum tone is `p` and the maximum tone of the songs you play is `q`, then the minimum time you will need to wait because of the tone is always `q - p`. So, let us pick the minimum and maximum tone of the songs you will play, `O(n^2)` options for this pair. The rest is just to play the best song durations between these tones such that the total duration is less than or equal to `T - q + p`.

int maxSongs(vector <int> duration, vector <int> tone, int T)
{ 
    //sort the tones:
    int n = tone.size();
    for (int i=0; i<n; i++) {
        for (int j=i+1; j<n; j++) {
            if (tone[j] < tone[i]) {
                swap(tone[j], tone[i]);
                swap(duration[j], duration[i]);
            }
        }
    }
    int res = 0;
    // pick the minimum and maximum tone:
    for (int a=0; a < n; a++) {
        for (int b=a; b < n; b++) {
            int t = T - tone[b] + tone[a];
            int c = 0;
            // save the durations in a vector
            int tim = 0;
            vector<int> d;
            for (int i=a; i<=b; i++) {
                d.push_back(duration[i]);
            }
            // sort the durations, so that we pick the smallest c durations:
            sort(d.begin(), d.end());
            for (int x: d) {
                if (x <= t) {
                    t -= x;
                    c ++;
                }
            }
            // remember the best
            res =std::max(res, c);
        }
    }
    return res;
}