January 9, 2022 Single Round Match 821 Editorials

AssignPoints

We just need to execute the point allocation algorithm described in the statement.

Instead of sorting all contestants according to their time, we can also note that the range of possible times is pretty small, so we can instead iterate through all times: assign points to everyone who finished in 1 second, then everyone who finished in 2 seconds, and so on.

public int[] assign(int N, int[] results) {
    int[] points = new int[N];
    int nextScore = N;
    for (int t=1; t<=10_000; ++t) {
        int current = 0;
        for (int n=0; n<N; ++n) if (results[n] == t) {
            points[n] = nextScore;
            ++current;
        }
        nextScore -= current;
    }
    return points;
}

OneBattleship

Imagine that we color all cells in the grid red, green or blue based on the value (row+column) modulo 3.

Regardless of how we place the battleship, it will always contain one red, one green, and one blue cell.

Thus, we can count the number of ‘.’ cells of each color, choose the color with the smallest number of occurrences (which has to be at most one third of all unknown cells), and shoot at all ‘.’ cells of that color. We are guaranteed to hit the battleship.

public String[] hit(String[] grid) {
    int R = grid.length;
    int C = grid[0].length();
    
    int[] counts = new int[3];
    for (int r=0; r<R; ++r) for (int c=0; c<C; ++c) {
        if (grid[r].charAt(c) == '.') ++counts[ (r+c)%3 ];
    }

    int where = 0;
    for (int i=0; i<3; ++i) if (counts[i] < counts[where]) where = i;

    String[] answer = new String[R];
    for (int r=0; r<R; ++r) {
        answer[r] = "";
        for (int c=0; c<C; ++c) {
            if (grid[r].charAt(c) == 'W') { answer[r] += 'W'; continue; }
            if ((r+c)%3 == where) { answer[r] += '*'; continue; }
            answer[r] += '.';
        }
    }
    return answer;
}

ConnectTheWorld

We are given a forest: an acyclic undirected graph. The graph is guaranteed to have more than one connected component. Our task is to add edges to make the graph connected, without increasing the maximum degree of the graph.

If the current maximum degree is 0 (isolated vertices only), there is clearly no solution.

If the current maximum degree is 1, this means that we have at least three vertices: at least two that are already connected by an edge, and at least one in another component than those two. But then the connected graph that contains all of them must clearly contain a vertex of degree more than 1, and thus there is again no solution.

In all other cases (i.e., the given graph has maximum degree 2 or more) a solution exists. One way to show this (and also an algorithm to construct one) is as follows:

Initially, all connected components of our graph are trees. Each tree contains a vertex of degree at most 1. (If it didn’t, the sum of its degrees would be at least twice its number of vertices, which would imply that it has at least as many edges as vertices.) Thus, we can take two trees, find one such vertex in each of them, and connect those by an edge. This will decrease the number of connected components by 1. The new component is clearly again a tree. (The new edge could not have created any cycle.) Repeating this process will eventually connect the entire graph.

As the input graph is small, we can afford to use a somewhat inefficient implementation that is easier and with no special cases. We will proceed as follows:

• Use a hashmap to assign numbers 0 to N-1 to city names.
• Build an adjacency matrix for the current graph.
• Use Floyd-Warshall to construct its transitive closure (i.e., find connected components).
• Assign colors 0 to C-1 to the individual connected components of our graph.
• Compute degrees and check the maximum degree to see whether a solution exists.
• For each color x from 0 to C-2: connect components with colors x and C-1.

public String[] connect(String[] terminalA, 
                        String[] terminalB,
                        String[] isolated)
{
    int N = 0;
    HashMap<String, Integer> ID = new HashMap<String, Integer>();
    int M = terminalA.length;
    int[][] edges = new int[M][2];
    for (int m=0; m<M; ++m) {
        if (!ID.containsKey(terminalA[m])) { ID.put(terminalA[m],N); ++N; }
        if (!ID.containsKey(terminalB[m])) { ID.put(terminalB[m],N); ++N; }
        edges[m][0] = ID.get( terminalA[m] );
        edges[m][1] = ID.get( terminalB[m] );
    }
    for (String x : isolated) { ID.put(x,N); ++N; }

    int[] degree = new int[N];
    for (int m=0; m<M; ++m) {
        ++degree[ edges[m][0] ];
        ++degree[ edges[m][1] ];
    }

    int MAX = 0;
    for (int x : degree) MAX = Math.max( MAX, x );
    
    if (MAX <= 1) return new String[0]; // no solution
    
    boolean[][] reachable = new boolean[N][N];
    for (int n=0; n<N; ++n) reachable[n][n] = true;
    for (int m=0; m<M; ++m) reachable[edges[m][0]][edges[m][1]] = true;
    for (int m=0; m<M; ++m) reachable[edges[m][1]][edges[m][0]] = true;

    for (int k=0; k<N; ++k) for (int i=0; i<N; ++i) for (int j=0; j<N; ++j)
        if (reachable[i][k] && reachable[k][j]) reachable[i][j] = true;

    int[] color = new int[N];
    for (int n=0; n<N; ++n) color[n] = -1;
    int C = 0;

    for (int n=0; n<N; ++n) if (color[n] == -1) {
        for (int a=0; a<N; ++a) if (reachable[n][a]) color[a] = C;
        ++C;
    }

    String[] names = new String[N];
    for (String x : terminalA) names[ID.get(x)] = x;
    for (String x : terminalB) names[ID.get(x)] = x;
    for (String x : isolated) names[ID.get(x)] = x;

    String[] answer = new String[2*C-2];
    for (int c=0; c<C-1; ++c) {
        int x = 0; while (color[x] != c || degree[x] > 1) ++x;
        int y = 0; while (color[y] != C-1 || degree[y] > 1) ++y;
        answer[2*c] = names[x];
        answer[2*c+1] = names[y];
        ++degree[x];
        ++degree[y];
        for (int n=0; n<N; ++n) if (color[n] == c) color[n] = C-1;
    }
    return answer;
}

KnapsackTweak

The general idea should not be too complicated, but there are a few caveats:

• The solution of the original knapsack that is the closest one to the target is not necessarily the one we want to tweak.
• The total price of the solution we want to tweak may be bigger than target, and even bigger than 100,000, so we have to be careful with upper bounds in our solution.

When looking at a particular collection of items, we actually care about two parameters: not just their total price P but also their count C. Once we know those two values, we can compute the amount by which we need to tweak them in order to reach the target price T: we need to take the difference abs(P-T) and split it among the group, so some of the items in the group will need to be tweaked by ceiling( abs(P-T) / C ).

Armed with this observation we can solve our task as follows:

• We will use knapsack-style dynamic programming to determine the set of currently reachable prices for each number of items separately.
• For each number of items, we will take the reachable price that is closest to the target and we’ll compute the amount of tweaking we would need.

Let M be the maximum price of a single item. Consider any fixed count C of items. Consider the collection formed by the C items with the largest prices. We can now repeatedly take the most expensive item in the collection and replace it by the cheapest of the other items. Each such change will decrease the total price of the collection by less than M. Eventually, we will reach the cheapest possible collection. The key conclusion from this is that the set of reachable collection prices is “dense”, there are never gaps bigger than the largest item.

There are only three possibilities to consider:

• All collections of C items are cheaper than the target.
• Some are cheaper, some are not. In this case it follows from the above observation that the cheapest of those that have price >= T will have price less than T+M.
• All collections of C items have cost at least T. In that case the best collection of C items is simply the collection of C cheapest items.

This is the approach chosen in the reference solution: it does DP to construct all reachable prices for each number of items and each total price up to T+M, and it also tries greedily constructing the cheapest collection for each number of items. The optimal solution must be somewhere among these. The time complexity of this solution is O(N^2*(T+M)).

If we think about the problem some more, we can show that the greedy part can be avoided completely. This is because:

• For the smallest C such that the cheapest collection of C items already has price >= T, this price does not exceed T+M and thus our DP will catch it.
• Let A be the actual real amount by which we would have to decrease each item in order to hit exactly T in the above solution.
• The target is positive, so at least some items must have positive tweaked prices. In particular, the largest price Q in that collection has to be greater than A.
• As we now increment C, we will be adding extra items that each have price at least Q, and thus greater than A.
• Thus, for each bigger C, even if we subtract A from all items in the cheapest collection, their new sum will be greater than T, and thus we need to tweak them by more than A in order to reach T exactly. But that means that among these options we will never find a better solution.

Thus the problem was quite forgiving: if you forgot to consider this option, it did not come back to bite you 🙂

CrossPrimesOut

In this problem we are essentially given an open-data problem. We’ll need to deal with some large primes, but we can do much of the work in the comfort of our local workstation instead of just having to do it in the submitted solution during its runtime. Or, at the very least, we can do all the testing locally to make sure everything works.

The general idea of the solution is hinted at already in Example 0 where we, after several steps of simulating the infinite process, conclude the following: “At this point it’s easy to show that in the final sequence element 0 will be 68 and element 1 will be 5654600.”

Why/how can we show that? We just processed the prime 401 and all future primes will be bigger, so the token “68” is surely safe. What about “5654600”? Well, clearly all 3- or more-digit substrings of this string are composite numbers, so there will never be any prime crossed out from this token either.

One possible approach that works really well looks as follows:

• Construct a big enough prefix of the sequence of digits. D=400 digits turns out to be more than enough for all test cases. The prefix can be found via binary search: we are looking for the biggest number P such that (P / 10^D)^2 < X, in other words, P^2 < X * 10^(2D).
• Iterate over all primes up to 10^6 and cross those out. You can get to this point quickly.
• At this point you can verify that for each valid X you already have much more than 30 space-separated tokens. As the number of tokens can only increase, we can now be sure that we have enough digits.
• From this point on, we finish the construction as follows: we look at all tokens we have, take all their substrings of 7 or more digits and test them for primality. The primes found this way are the only candidates for moments when something interesting will happen in the future. All other primes won’t influence our prefix of the text.
• The previous step is the step where the open-data aspect comes into play. If your language of choice doesn’t have a good primality test, you can outsource it: iterate over all X, when doing the primality testing do what you can (e.g., just trial division up to some bound), and log the numbers for which you aren’t sure. Then simply use an external tool (e.g., “factor” in linux) and hard-wire the outputs into your solution (“these are primes, these aren’t”).
• Caveat: only actual primes of 7 or more digits should be considered as candidates. E.g., when the 7- character string “0000002” gives you the prime 2, you don’t want to process it again.
• For each candidate, in sorted order, we process it just like we processed the small primes earlier: we check whether it still has an occurrence, and if it does, we erase the first one. (Note that we cannot just erase all candidates. Some may overlap and then only the earlier one gets erased.)