SRM 589: Read the statement! (upd)

So another SRM. This time the scores were very special: 250-450-900. It seemed like a good match to use my strategy. At the end though, I didn't take much advantage of it, because of two blunders...

Div1 450: The one with gears

We have gears of three colors, red, green , blue. Initially, some pairs of gears are meshing: If one of the gears in a meshing pair turns in a direction, the other gear must turn in the other direction. No two gears of the same color ever mesh. We want to be able to turn all the gears in such a way that all the (remaining) gears of the same color turn in the same direction. What is the minimum number of gears to remove?

I think using clock-wise and anti-clockwise for the directions is too verbose, so let us call say that some gears are positive and some gears are negative. Now all the gears of the same color must have the same *sign* and two connected (meshed) gears must have different signs.

There are only three colors and two signs, so how about we do brute force for the signs? There will always be two colors with the same sign, otherwise it doesn't matter which sign. So two colors have equal sign, let us say positive, and another color is negative. Between the two positive colors, there should be no connections...

We can actually ignore the negative gears, all their connections are already valid and removing them won't fix anything. So now we only have gears of two colors that should never be connected. This is the independent set in a bipartite graph. So let us just run max flow...

During the match, I took a bit of time because at first I was considering the negative gears, causing a single wrong case (the other example cases were very weak). It was early in the morning, I was just confused...

Div1 900: The one with bits

You want a binary string of N bits (N is up to 300) to be one in which the prefix of length N-M and the suffix of length N-M are equal. You can flip a single bit at cost 1 and you can also flip the first K*M bits at cost 1 (for any positive K). What is the minimum cost?

I think I have some ideas. Unlike most div1 hards, I think I can solve this in a few hours and without help. It is a dynamic programming problem with complications.

Div1 250: The one with palindromes

Turn a string palindrome (again?). This time your only allowed move is to pick two alphabet letters X and Y , and turn all the X letters into Y. Return the minimum number of letter positions you need to change.

I only had 10 minutes, so I rushed to code a solution, which was mostly right. I missed the fact that you want to minimize the number of changed positions (it didn't help that this fact was disguised by some talk about seconds). Not the number of changed letters. I only noticed when there were some seconds left before the end of the challenge phase. I fixed the code some time before the end of intermission.

Anyway... The palindrome requirement means that some pairs of positions must be equal. This means that at the end the letters in that pair of position must be equal. This creates a relationship/connection between pairs of letters. At the end, all letters in a group of letters that are connected (directly or indirectly) must be equal. We have to change each of these letters to the same letter. It is best to pick the letter that appears the maximum number of times. Repeat for each connected component.

int getmin(string S) 
{
    int n = S.length();
    vector<bool> visited(26, false);

    // This DFS finds a list of all letters that are *connected* to letter ch:
    // Returns the maximum number of times one of the connected letters appears
    function<int(char)> dfs = [&](char ch)->int {
        if (!visited[ch - 'a']) {
            int res  = count(S.begin(), S.end(), ch);
            visited[ch - 'a'] = true;
            // Two letters are connected if the palindrome rule states that
            // two positions that contain the letters must be equal:
            for (int j=0; j<n; j++) {
                if (S[j] == ch) {
                    res = std::max(res, dfs( S[n-j-1] ) );
                }
            }
            return res;
        }
        return 0;
    };

    // For each group of connected letters, find the letter that appears the
    // maximum number of times, subtract it from the total cost:
    int res = S.length();
    for (char ch = 'a'; ch <= 'z'; ch++) {
        res -= dfs(ch);
    }
    
    return res;
    
    
}

Update Maybe that lambda stuff makes the code appear complicated, here is a python version:

def getmin(S):
    n = len(S)
    visited = set()
    
    # This DFS finds a list of all letters that are *connected* to letter ch:
    # Returns the maximum number of times one of the connected letters appears
    def dfs(ch):
        if ch not in visited:
            visited.add(ch)
            res = S.count(ch)
            # Two letters are connected if the palindrome rule states that
            # positions that contain the letters must be equal:
            for i in range(0,n):
                if S[i] == ch:
                    res = max(res, dfs( S[n - i - 1]) )
            return res
        return 0
    
    # for each connected component, subtract the letter with the maximum number
    # of position: Call dfs for each of the letters in string.lowercase :)
    return n - sum( dfs(ch) for ch in string.lowercase )

Outcome / Comments / etc?

So I am back to yellow, I could have gotten much better rating if I paid attention when reading the 250.

What did you think about the match?