SRM 602: High note

So there we go, the last SRM of the year. I did sort of good, at least it is a nice improvement over the last few matches.

Div1 250: The one with rating

Your initial rating is `X` , there are `n` matches ahead. If during match `i` you have `x` rating, then you have two choices:

• Increase your rating by `D_i`: `x = x + D_i`.
• Decrease your rating by `D_i`, but if it becomes negative set it to zero : `x = max(0, x -D_i)`.

Constraints are large: `(n <= 50)`, `D_i <= 1000000000`. Whenever your rating changes from bellow 2200 to >= 2200 and vice versa, your rating changes color. Also, you don't like having 2200 or more rating too frequently so, you shouldn't have more than 1199 rating in two consecutive matches. Return the maximum number of rating color changes there can be. X is initially less than 2200.

So besides the large constraints, you never want rating to stay higher than 2199 in two consecutive matches. If `x + D_i >= 2200` , then you should make sure that either the match `i` is the last match or that after match `i+1`, the rating can drop back bellow 2200: `x + D_i - D_(i+1) < 2200`. If that is true, then you can skip to match `i+2`. This ensures that the rating you remember is always < 2200. Limiting the number of states of the function. We can now use dynamic programming:

int getmax(vector<int> D, int X)
{
    const int BROWN = 2200;
    int dp[D.size() + 1][BROWN + 1];
    function<int(int,int)> f = [&](int i, int x) {
        int & res = dp[i][x];
        if (res == -1) {
            if (i == D.size()) {
                //base 
                res = 0;
            } else {
                // { x < 2200 }
                // up:
                if (x + D[i] >= BROWN) {
                    // become brown, must be "ciel" in the next move
                    if (i + 1 < D.size()) {
                        if (x + D[i] - D[i+1] < BROWN) {
                            // can do it
                            res = 2 + f(i + 2, std::max(0, x + D[i] - D[i+1]) );
                        }
                    } else {
                        res = 1 + f(i + 1, BROWN );
                    }
                } else {
                    res = f(i + 1, x + D[i]);
                }
                // down:
                res = std::max( res, f(i + 1, max(0, x - D[i]) ) );
            }
        }
        return res;
    };
    memset(dp, -1, sizeof(dp));
    return f(0, X);
}

I wish I was faster on this problem, it took me a while to get the brain to work. Oh well.

To be fair, I had a couple of distractions. A message appeared saying that "If you see only 5 examples, you should reopen the problem because there are 6 examples!". So I reopened the problem, and something funny: There were 7 examples. I felt like this is either a typo in the message or a mistake when adding the examples that the admins should really know about... Then I noticed that the message I received was about the 550 points problem ... Oh, so nevermind...

... wait. I could swear that I noticed 5 examples in the 250 problem the first time I opened! Indeed, after checking out the problem statement that was generated by Greed, I could notice that there were 5 examples in the first version even though there are 7 examples now. I notified the admins that the number of examples in the div1 250 problem also had discrepancies...

Div1 550: the one with rectangles

There are up to 200000 rectangles of dimensions <= 1000000000. Split the rectangles in 2 groups of equal number of rectangles. Then calculate the maximum intersection between the rectangle areas in each group - Sides must always be paralel to the xy axis - . Return the maximum possible sum between the intersection areas of the two groups.

Oh well, I guess my new year will involve me spending lots of time on this problem. It appears a bit complicated. During the match, I tried many heuristics that were wrong - E.g: Sorting by smallest dimension and making the first group have the smallest rectangles. Also tried sorting in row-major order . Well, things like that. No luck.

My incomplete solution idea is that one of the groups ought to have the smallest width and smallest height rectangles. So maybe there is an optimal-substructure there? No idea.

Challenge phase

There were 3 submissions for 550, two from blue coders. I opened one from a blue coder and could notice something strange. It had an if N < 2 return X[0]*Y[0]. Which doesn't make a lot of sense. If N = 1, there are still two rectangles and you should move them to different groups still. I thought that any case with N = 1 should make it fail, and indeed, I got 50 challenge points :)

Later I was about to go get lunch, but maybe my challenge luck could become a streak. I opened the other blue coder's code, and their code seemed to use one of the heuristics that I tried and was wrong. Definitely the last example case should make it fail... however, I hesitated too long to try challenge it, and someone else got that challenge. This someone else, cup_of_tea already had a challenge and climbed to first place in my room. Not cool!

Comments

It is a shame there were issues with the example cases . So far the admins decided to keep the match rated. It was otherwise a good match, even though 550 seemed too tough for me.