April 28, 2022 TCO22 Round 1B Editorial

TwoTowers

In this easy problem the main observation we need is that for any collection of rectangles we can build a tower from all of them without having to rotate any rectangles. Once we ask the question whether this is always possible, the positive answer is pretty straightforward: all we have to do is sort the rectangles by width. This will always give us a valid order in which they can be placed (top to bottom).

Once we know that building a tower is always possible, we can now think about its maximum height. Clearly, an A[i]xB[i] rectangle can contribute at most max(A[i],B[i]) to the height of the tower, so sum(max(A[i],B[i])) is an upper bound on the answer. And Alice can always make a tower this tall simply by rotating each rectangle to be at least as tall as wide – i.e., to have the longer dimension vertically.

In exactly the same spirit we can show that Bob’s height will be sum(min(A[i],B[i])) – the best he can to is flip all rectangles from Alice’s tower to make sure each is at most as tall as it is wide.

The final answer is then the difference between those two values.

Another way to compute the final answer is to notice that rotating a single rectangle changes the sum of heights by abs( A[i]-B[i] ), so when Bob takes Alice’s tower and starts to rebuild it, the maximum total change in difference he can make is sum( abs( A[i]-B[i] ) ).

public int maxDifference(int[] A, int[] B) {
    int N = A.length;
    int alice = 0;
    for (int n=0; n<N; ++n) alice += Math.max( A[n], B[n] );
    int bob = 0;
    for (int n=0; n<N; ++n) bob += Math.min( A[n], B[n] );
    return alice - bob;
}

TwoLineMinesweeper

A good way of viewing the problem is to imagine that instead of mines and empty spaces we are filling the bottom row with zeros and ones. Then, the numbers we are given in the first row are simply the local sums: each cell in the first row tells you the sum of its neighbors in the second row.

As we saw in one of the examples, the first row does not necessarily determine the second row – sometimes there is more than one solution. However, once we start playing around with the problem, we should quickly discover that there can never be more than two solutions. One very clean way how to show this is to simply try filling the row from the left to the right.

For the leftmost cell we will try both options: either it contains a mine (1) or it does not (0). For each of those options we now want to try filling the rest of the row.

Here’s an example in which we started with a mine:

+---+---+---+---+---+---+
| 1 | 2 | 1 | 1 | 0 | 0 |
+---+---+---+---+---+---+
| 1 |   |   |   |   |   |
+---+---+---+---+---+---+

Now look at the top left cell. This is telling us the sum of the first two cells in the second row (1). As we already know one of them, we can compute the other: 1-1 = 0.

+---+---+---+---+---+---+
| 1 | 2 | 1 | 1 | 0 | 0 |
+---+---+---+---+---+---+
| 1 | 0 |   |   |   |   |
+---+---+---+---+---+---+

And now we just continue in the same way. The first three cells in the second row should have sum 2. They are 1, 0, and what? That’s right, the next cell must be 1.

+---+---+---+---+---+---+
| 1 | 2 | 1 | 1 | 0 | 0 |
+---+---+---+---+---+---+
| 1 | 0 | 1 |   |   |   |
+---+---+---+---+---+---+

Now we can take the next cell in the top row and use it to compute the next cell in the bottom row, and we repeat this until the bottom row is full. Thus, once we decided what to put into the leftmost cell, the entire bottom row became forced. 

Hence, for each choice of the leftmost cell we will get at most one valid solution. The “at most” is there because sometimes the process can fail. How? Let’s take the same first row as before but let’s start with an empty cell. We can deduce the next two cells, leaving us in the following situation:

+---+---+---+---+---+---+
| 1 | 2 | 1 | 1 | 0 | 0 |
+---+---+---+---+---+---+
| 0 | 1 | 1 |   |   |   |
+---+---+---+---+---+---+

What happens next? In order to have sum=1 for the next cell and its two left neighbors, we would need to put a -1 into the cell – but that’s not possible, we cannot have a negative number of mines anywhere.

Thus, in general, we only have a valid solution if all the values we compute are zeros and ones only, and one more check passes: after we use the penultimate cell of the top row to compute the last cell in the bottom row, we still need to verify that the last cell in the top row contains the correct sum. (A common way to fail solving this problem is missing this check. For N=1 such a solution generates and returns both options without checking whether the number of mines actually matches the only given sum.)

The code shown below explicitly sorts the answers it constructs, but this is easy to avoid: if we try the answer starting with a mine first, we can be sure to generate the two answers in lexicographic order.

public String[] solve(int[] firstLine) {
    ArrayList<String> answers = new ArrayList<String>();

    int N = firstLine.length;
    int[] secondLine = new int[N];
    
    // try both possibilities for the leftmost cell
    for (secondLine[0]=0; secondLine[0]<2; ++secondLine[0]) {

        // reconstruct the rest of the row
        boolean allOk = true;
        for (int n=1; n<N; ++n) {
            secondLine[n] = firstLine[n-1];
            secondLine[n] -= secondLine[n-1];
            if (n >= 2) secondLine[n] -= secondLine[n-2];
            if (secondLine[n] < 0 || secondLine[n] > 1) allOk = false;
        }

        // verify whether the last sum matches too
        int lastSum = secondLine[N-1];
        if (N > 1) lastSum += secondLine[N-2];
        if (firstLine[N-1] != lastSum) allOk = false;

        // if we found a solution, construct and store the string
        if (allOk) {
            String answer = "";
            for (int n=0; n<N; ++n) answer += (secondLine[n] == 1 ? '*' : '-');
            answers.add( answer );
        }
    }

    Collections.sort(answers);

    String[] finalAnswers = new String[answers.size()];
    for (int n=0; n<answers.size(); ++n) finalAnswers[n] = answers.get(n);
    return finalAnswers;
}

Stringversions

Let’s start by asking the question: given the length L, what is the maximum number of inversions?

Lemma 1: If we already picked the collection of letters to use, clearly the way to produce the most inversions is to sort them in ‘z’ to ‘a’ order.

Proof: Consider any string S that isn’t sorted in non-ascending order. Find the smallest index i where the order breaks – that is, S[i] < S[i+1]. Then, swapping S[i] and S[i+1] increases the number of inversions by one, which means that the original S was not optimal.

Thus, the string with the most inversions will necessarily have the form z..zy..yx..x……c..cb..ba..a. All that remains is to determine the numbers of occurrences of individual letters.

Intuitively, we want to use the whole alphabet as regularly as possible: for example, up to L=26 it’s clearly optimal to use distinct letters so that each pair of indices forms a collision. So the expected answer is that in the optimal string the letters counts should be as similar to each other as possible. Below we will prove that this is really the case.

Now to the full solution. It’s possible to construct the desired string directly (e.g., starting from an empty string and repeatedly inserting a character that adds as many inversions as possible without exceeding the desired total), but the constraints are small enough for less efficient solutions to work too. We will describe an approach that is both obviously correct and easy to implement.

We will start by constructing the string with the given length and the maximum number of inversions. If that still isn’t enough, we answer that there is no solution. And if that number of inversions is too large, we will repeatedly decrease it by 1 until we get the exact right number of inversions.

How to decrease the number of inversions by 1? This is essentially the same process we used in Lemma 1, only in reverse: find a consecutive pair of characters that can be swapped. For L = 500 the maximum number of inversions is 120190, so we can afford to look for such a pair by brute force, each time iterating through the whole string.

char[] fill(int L) {
    // fill an array of length L with an uniform distribution of characters,
    // sorted in descending order
    int[] tmp = new int[L];
    for (int i=0; i<L; ++i) tmp[i] = i % 26;
    Arrays.sort(tmp);
    char[] answer = new char[L];
    for (int i=0; i<L; ++i) answer[i] = (char)('a' + (25-tmp[i]));
    return answer;
}

String toString(char[] data) {
    String answer = "";
    for (char x : data) answer += x;
    return answer;
}

int countInversions(String data) {
    int answer = 0;
    for (int i=0; i<data.length(); ++i) {
        for (int j=i+1; j<data.length(); ++j) {
            if (data.charAt(i) > data.charAt(j)) ++answer;
        }
    }
    return answer;
}

int maxInversions(int L) {
    return countInversions( toString( fill(L) ) );
}

public String create(int L, int N) {
    int currInversions = maxInversions(L);
    if (currInversions < N) return "";
    char[] data = fill(L);
    while (currInversions > N) {
        for (int i=0; i<L-1; ++i) if (data[i+1] < data[i]) {
            char tmp=data[i]; data[i]=data[i+1]; data[i+1]=tmp;
            --currInversions;
            break;
        }
    }
    return toString(data);
}

What follows is the proof that the as-uniform-as-possible distribution of characters produces the maximum number of inversions. 

There are L*(L-1)/2 pairs of indices into our string. Most of them are inversions. The remaining ones are the pairs in which both indices point to the same letter. If we want to have the most inversions, we want to have the smallest number of pairs of indices of the other type.

Let C[x] denote the number of occurrences of the letter x in our string. Then, there are C[x] * (C[x]-1) / 2 pairs of indices that both point to an x. We want to minimize the sum of these counts over all x.

We can now multiply the value we are minimizing by two and rewrite each term as C[x]*C[x] – C[x]. As the sum of all C[x] is simply L, we are minimizing sum(C[x]*C[x]) – L, which is the same as just minimizing the sum of C[x]*C[x]. That is, the optimal solution is the string with the smallest possible sum of squares of letter counts.

Lemma 2: In the optimal solution no two C values can differ by two or more.

Proof: Suppose C[x] >= C[y]+2 for some x and y. What happens when we remove one x from the string and add one y instead? The sum of squares will decrease by 2*C[x]-1 and it will increase by 2*C[y]+1. The total change is therefore negative – i.e., the sum of squares has decreased.

Hence, in the optimal solution max(C) – min(C) <= 1. 

And this is only satisfied if min(C) = floor(L/26) and max(C) = ceiling(L/26). Indeed:

• If L is a multiple of 26, all values in C must equal L/26: if you had a smaller one, you would have to have a larger one as well, and they would differ by at least two.
• For any C we know that max(C) is at least ceiling(L/26) and min(C) is at most floor(L/26). And if L isn’t a multiple of 26, ceiling(L/26) and floor(L/26) already differ by 1, so in order to have max(C) – min(C) <= 1 we must have equality in both cases.