SRM 592 - sloow

d1 300 - The one with colors

So you have a sequence of balls, each has one of three colors: red, green and blue. You need to place the balls in a row. The order in which to place the balls is given by a string S. When you place a ball, you get points equal to the number of different colors to its right + the number of different colors to its left. Find the maximum possible score.

At first I thought of a dynamic programming solution. It was correct and all, but perhaps I should have waited to think of something better.

Let us name two sides of the row, the left and right side. When we place a new ball, it is best to place it between the two sides. So the score of that step is equal to the number of different colors in the right side + the number of different colors in the left side. The trick is that after adding this ball, we decide whether it belongs the left or the right side. In my dynamic programming solution I simulated both possibilities, but it is not needed. It is always better to add the ball to a side that doesn't already contain its color (This decision will increase the score of following steps by 1, any other decision won't). If both sides contain the color, it doesn't really matter.

int getNumber(string s)
{
    set<char> s1, s2;
    int res = 0;
    for (char ch: s) {
        res += s1.size() + s2.size();
        // if s1 already contains s[i] insert it to s2:
        ( s1.count(ch) ? s2 : s1).insert(ch);
    }
    return res;
}

There are other ways to implement the same logic. For example, in step i, the maximum score you can get is equal to min(2, number of red balls already placed ) + min(2, number of blue balls) + min(2, number of green balls). But the resulting code is actually more complicated.

d1 500: The one with permutations

Given `k` and `n` , count the number of pairs of permutations `(A, B)` of length `n` such that `sum_(i=1)^(i<=n)( max(A_i, B_i) ) >= K`

I spent most of the match trying to come up with a way to divide this problem into workable sub-problems, I sort of knew it would be a dynamic programming solution, but I had no idea how. I was trying and trying to find a way to simplify sub-problems. Oh well.

The rest

Opened div1 hard. I think it will be an approachable one once I get help. Tried to challenge but there was only one suspicious solution to div1 250 in my room and it got challenged before I could think of something.