SRM 563: The trend has been stopped, for now

So, to recap, I made the decision that from now on I will never solve a TopCoder division 1 easy problem in more than 10 minutes. This new strategy to open the hard and medium problems first and never open the easy until there are 10 minutes left is, of course, suicidal. It does not help that my rating was already trending downwards before making this decision.

Div1 hard

This problem seemed complicated. In fact, for a second I wondered if the match was going to be canceled because the problem is actually impossible.

I have not shared this but it has been decided that starting in SRM 564 I will always write the editorial, unless it is an exceptional case. Which means I now receive the editorial assignment and explanation of hard problem just half an hour after results are announced. In theory, this should make editorials arrive faster... in theory. What is important to know is that I now read the short explanation for this problem, and it turns out it was not difficult at all ...

Div1 Medium - The one with magic cards

5 minutes after opening the hard problem, I gave up and opened the medium problem. My first reaction was that it seemed approachable. And it was.

You got a list of cards from left to right. Each card has a level and a damage value. You can use a card with level L and damage D if and only if there are at least L-1 cards to its right. In case you use the card, you perform D damage and the card and the L-1 cards to its right get removed from the game. Another allowed step is to move the right-most card to the left-most place of the list of cards. What is the maximum total amount of damage you can make?

The first step is to alter the problem a bit. You actually have a circle of cards, placed in clockwise order. At every point, you can take any of the cards of level L, take the L-1 cards to its right and the card itself and perform D damage. These two variations are equivalent.

To solve the variation, consider another variation. In which you have the cards in a line. Once again, you can pick any card and remove it and the L-1 cards next to it. But this time it is not a circle (for now).

To solve this easier variation of the problem we use dynamic programming. The issue is that you can remove cards in any order and the order can alter the result dramatically. Thus the main thing to approach is how to decide their removals following a fixed order...

In fact, imagine that we decide to use the i-th card. This means that the level[i]-1 next cards to it have to be removed. But then after this decision, we decide to also use card i+1. We got to use card i+1 before using card i. When we decided to remove card i, we decided that we owe level[i]-1 cards. After deciding that we will use card i+1 before card i, we actually increase the amount of cards owed by (level[i+1]-1), so that then we can decide what to do with card i+2, and so and so, assuming an amount of owed cards.

A different case is what happens when we decide not to use card i+1, then we will remove this card when we remove the owed cards. This means we will need one less card. The number of owed cards decreases by 1.

That logic allows a dynamic programming solution. f(p, owed) finds the maximum damage you can make by using the cards with index greater than or equal to p, and you currently owe owed cards. Note that the base case is when p=n, then owed must be 0.

The next issue is what to do in the circular case. There are two clever work around to this. The first one is to try all n ways to rotate the vector of cards, and then just solve using the previous method.

The second method is to assume that there was an amount initOwed of cards that we will owe after processing the last card in the input. Then at the start of the simulation, when p=0 we already owe some cards (that we will assume we will define to owe later). The base case changes, the amount of owed cards at the end must be the same as the one that was planned in advance.

It is funny but I used both approaches at the same time. But of course, only one is necessary.

Here is the code anyways:

Div1 easy

It was worth 300 points. I opened it with 9:50ish minutes left, and I knew it was going to be difficult. For the first 5 minutes I implemented a solution that turned out to be wrong. I tried to use the remaining time to come up with a solution or a cheap trick that allowed the wrong solution to work. With no success.

Challenge phase/etc

Not much happened afterwards. I eventually passed system tests in div1 500. At least the trend towards the bottom of the ratings is not going on.

int n; 
vector<int> lvl, dmg; 
 
int dp[MAX+1][MAX+1]; 
 
int rec(int p, int owed) 
{ 
    int & res = dp[p][owed]; 
    if (res == -1) { 
        if (p == n) { 
            if (owed == 0) { 
                res = 0; 
            } else { 
                res = -INF; 
            } 
        } else { 
            res = -INF; 
            //use this? 
            if (owed + lvl[p] - 1 <= n) { 
                res = std::max(res, dmg[p] + rec(p+1, owed + lvl[p] - 1 ) ); 
            } 
            //do not use this 
            res = std::max(res, rec(p+1, std::max(owed - 1, 0) ) ); 
        } 
    } 
    return res; 
} 
 
int maxDamage(vector <int> level, vector <int> damage) 
{ 
    n = level.size(); 
    lvl.resize(n); 
    dmg.resize(n); 
    int res = 0; 
    for (int start = 0; start < n; start++) { 
        for (int i=0; i < n; i++) { 
            int j; 
            if (i < start) { 
                j = (n - start) + i; 
            } else { 
                j = i - start; 
            } 
            lvl[i] = level[j]; 
            dmg[i] = damage[j]; 
        } 
 
        memset(dp, -1, sizeof(dp)); 
        res = std::max(res, rec(0, 0) ); 
    } 
    return res; 
}