June 7, 2022 Single Round Match 830 Editorials

AssignLabels

We have been given a task with two separate parts: first we need to produce a set of distinct labels, and then we need to assign them to the objects in correct order.

One way to produce a set of labels is to copy an arbitrarily long text. You can sort its words, discard duplicates, take the first 200 and embed them into your code as a constant.

Another option is to generate the labels directly from IDs. There are 26 letters, so there are 26^2 distinct two-letter strings. This is more than 200, so we have enough distinct labels, and we can generate them really easily. (In the code shown below we generate the label directly from its ordinal number, but you can also generate all 26^2 into an array using two nested cycles, and then index into the array.)

To finish our work, we now look at the given order. We assign the label “aa” to the object order[0], then “ab” to order[1], and so on.

String label(int id) {
    String answer = "";
    answer += (char)('a' + (id/26));
    answer += (char)('a' + (id%26));
    return answer;
}

public String[] assign(int N, int[] order) {
    String[] answer = new String[N];
    for (int n=0; n<N; ++n) answer[ order[n] ] = label(n);
    return answer;
}

In retrospect, apologies for not having stronger examples that would catch the issue that caused many participants to fail: a solution that produced an “inverse permutation” of labels passed the examples. This was not intended – we certainly weren’t trying to trick you into misreading the statement. We didn’t realize that the current examples are not sufficient to catch solutions that have this issue. If we had noticed this, we would have included one more example.

The issue here is that for example for the input order = {1, 2, 3, 4, 0} a correct output, as defined by the statement, would be { “ee”, “aa”, “bb”, “cc”, “dd” }. Note that the statement said that the elements of order are the IDs of the objects, ordered from the object with the smallest label to the object with the largest label. So for example object with ID 0 should have the largest number, because 0 is the last element of order. Many solvers misunderstood this part and instead returned a sequence of labels equivalent to {“bb”, “cc”, “dd”, “ee”, “aa”} – as if order[x] told us the order of element x.

MaxDiffBetweenCards

The easiest way to solve this problem is to use brute force for small N, we can easily discover and generalize the pattern (“Given N, I should choose these N digits, and then this is the largest and this is the smallest possible number formed out of those digits and this is their difference.”)

The optimal collection of digits is (N div 2)x ‘9’, one ‘1’, and the rest are ‘0’s. The largest number is 99…9100…0, the smallest number is 100…099…9, and the answer is their difference.

Below we will show how to derive the above result exactly.

Let’s start with a simple observation. If we already have a set of digits written on the cards, we can:

• produce the largest possible number by sorting the digits largest to smallest
• produce the smallest possible number by putting the smallest non-zero digit first and then placing all remaining digits smallest to largest.

Thus, the two numbers are almost – but not entirely – reverses of each other.

(The above observation makes it really easy to brute force everything up to N = 8. We can simply iterate over all N-digit numbers and for each of them we construct the largest number with the same digits and compute the difference.)

If we only have a single digit (N = 1), the answer is clearly zero. Below, assume N >= 2.

The key observation is that we can choose the digits greedily, going left to right (i.e., starting with the most significant digits). This is because once you make a smaller difference at a more significant place, it doesn’t matter what you do next, the final difference will still be smaller.

The leading digits will be 9 and 1 in the largest and smallest number, respectively. Then, we get some pairs (9, 0) until we get to the half of the number. If N is even, everything is now fixed: e.g., for N=8 the largest number starts 9999 and the smallest starts 1000, which means that the largest number is 99991000 and the smallest one is 10009999.

If N is odd, we still have one more digit to choose, but there it’s already easy to check all options we have and pick the best one: another 0 would get paired with the 1 we already have, while anything else would get paired with itself. Thus, for example the best numbers for N=9 are 999910000 and 100009999. (If we had a 3 instead of the final 0, we would have 999931000 and 100039999, with a smaller difference.)

Jetpack

This is clearly some shortest path problem, we just need to discover how to adapt some standard shortest path algorithm to solve it. Doing it in a too naive way (i.e., having a state where the charges of the jetpack are a part of the state) will probably be too slow – and we would still need to spend some time thinking about an upper bound for the number of simultaneous charges we might need. Let’s come up with a better way.

The first observation we can make is that in the optimal solution stepping on a pit will cost us exactly T+1 seconds: one for the actual move and T for charging the jetpack at some earlier point in time.

The second observation is that we can do all the charging we’ll need at the very first charging station we encounter during our travels: any other solution can be modified into one that does this without changing how long it takes.

This already gives us a full solution that’s fast enough. Consider a graph in which the vertices are triples (integer, integer, boolean): coordinates where we are, and a flag whether we already saw a charging station. In the states that haven’t seen it we are not allowed to enter pits. In the states that did we can enter pits and it costs T+1 seconds, as described above. The shortest path from (coordinates of A, false) to (coordinates of B, anything) in this graph is the optimal way of reaching B from A.

Alternately, we can implement the solution by doing two searches in the original graph: one from A and one from B. For the search from B entering a pit costs T+1. For the search from A it costs 100,007 (i.e., more than any path that never uses a jetpack).

In this solution, we use the search from A to determine the best way of reaching B without flying, and also the set of reachable charging stations. Then, the optimal solution is either the best route without flying, or the best route that reaches some charging station without flying and then goes from there to B, flying if needed.

int R, C;
char[][] maze;

long record(int dist, int r, int c) {
    long answer = dist;
    answer *= 107; answer += r; answer *= 107; answer += c;
    return answer;
}

int[][] dijkstra(int sr, int sc, int T) {
    int[] DR = new int[] {-1, 1, 0, 0};
    int[] DC = new int[] {0, 0, -1, 1};

    int[][] distances = new int[R][C];
    for (int r=0; r<R; ++r) for (int c=0; c<C; ++c) distances[r][c] = 987654321;
    distances[sr][sc] = 0;
    TreeSet<Long> Q = new TreeSet<Long>();
    Q.add( record(0,sr,sc) );
    while (!Q.isEmpty()) {
        long curr = Q.first();
        Q.remove(curr);
        int cc = (int)(curr % 107);
        curr /= 107;
        int cr = (int)(curr % 107);

        for (int d=0; d<4; ++d) {
            int nr = cr + DR[d], nc = cc + DC[d];
            if (maze[nr][nc] == '#') continue;
            int cl = (maze[nr][nc] == '_' ? T+1 : 1);
            if (distances[nr][nc] <= distances[cr][cc] + cl) continue;
            Q.remove( record( distances[nr][nc], nr, nc ) );
            distances[nr][nc] = distances[cr][cc] + cl;
            Q.add( record( distances[nr][nc], nr, nc ) );
        }
    }
    return distances;
}

public int travel(String[] _maze, int T) {
    R = _maze.length + 2;
    C = _maze[0].length() + 2;
    maze = new char[R][C];
    for (int r=0; r<R; ++r) for (int c=0; c<C; ++c) maze[r][c] = '#';
    for (int r=0; r<R-2; ++r) for (int c=0; c<C-2; ++c)
        maze[r+1][c+1] = _maze[r].charAt(c);

    int sr = -1, sc = -1, tr = -1, tc = -1;
    for (int r=0; r<R; ++r) for (int c=0; c<C; ++c) {
        if (maze[r][c] == 'A') { sr=r; sc=c; maze[r][c] = '.'; }
        if (maze[r][c] == 'B') { tr=r; tc=c; maze[r][c] = '.'; }
    }

    int[][] distances1 = dijkstra(sr, sc, 100_000);
    int[][] distances2 = dijkstra(tr, tc, T );
    int answer = 987654321;
    if (distances1[tr][tc] < 100_000) {
        answer = distances1[tr][tc];
    }
    for (int r=0; r<R; ++r) for (int c=0; c<C; ++c) if (maze[r][c] == 'C') {
        if (distances1[r][c] >= 100_000) continue;
        answer = Math.min( answer, distances1[r][c]+distances2[r][c] );
    }
    if (answer == 987654321) return -1;
    return answer;
}

MorseCodeCorrector

In my opinion, the main issue to tackle in this problem is that the code can easily get quite ugly. Below I’ll try describing a solution that should be pretty straightforward to implement and not too ugly.

We will approach the problem via automata theory: we’ll build a deterministic finite automaton that recognizes the set of all valid messages, and then we will use dynamic programming to find the best way to get the automaton to accept our string.

Morse codes for letters can be represented as a rooted tree (more precisely, a trie) as shown below. The left branch is always a dot, the right branch is a dash.

             start
         _____/ \_____
        /             \
     __E__           __T__
    /     \         /     \
   I       A       N       M
  / \     / \     / \     / \
 S   U   R   W   D   K   G   O
/ \ /   /   / \ / \ / \ / \
H V F   L   P J B X C Y Z Q

We can now build an automaton with 30 states: State 0 is the start state (we will be here only for the empty string.) States 1-26 are the letters in alphabetical order. The edges labelled ‘.’ and ‘-’ are taken from the Morse tree.

From each letter, there is an edge labelled ‘|’ (separator) to state 27 (“end of letter”), from that state there is an edge labelled ‘|’ to state 28 (“end of word”). Both from state 27 and state 28, a dot gets us to state “E” (state 5) and a dash gets us to state “T” (state 20). All other edges of the DFA lead to state 29 (“garbage”). States 1-26 (letters) are accepting states.

We can easily build this entire DFA in memory from the textual representation of codes we were given in the statement.

As promised, now we want to use dynamic programming to find the best set of edits. We will do so as follows: for each i and j we are looking at the prefix of length i and we are asking the question: “What is the smallest number of edits needed if I want to finish in state j after this prefix of length i is processed?”

The easiest way of doing this is by iterating over all i in increasing order, and each time processing all states. In the beginning we know that for i=0 we can be in state 0 for free and we cannot be in any other state. Now, if we know the costs for some i, the costs for i+1 are computed as follows: for each state j we look at the optimal cost C[i][j] of reaching it in i steps, and then:

• we can process the next character of the message to reach the state automaton[ j ][ next_char ] with exactly C[i][j] edits
• or we can change the next character of the message to some other character y, which will bring us to the state automaton[ j ][ y ] in exactly C[i][j] + 1 edits.

int getIndex(String[] CODES, String code) {
    for (int i=0; i<CODES.length; ++i) if (CODES[i].equals(code)) return i;
    return 29;
}

int[][] buildAutomaton() {
    String[] CODES = new String[] { "", ".-", "-...", "-.-.", "-..", ".",
        "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--", "-.",
        "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--",
        "-..-", "-.--", "--.." };

    int[][] automaton = new int[30][3];
    for (int a=0; a<30; ++a) for (int b=0; b<3; ++b) automaton[a][b] = 29;
    for (int a=0; a<27; ++a) for (int b=0; b<2; ++b) {
        String newCode = CODES[a] + ".-".charAt(b);
        automaton[a][b] = getIndex( CODES, newCode );
    }
    for (int a=1; a<27; ++a) automaton[a][2] = 27;
    automaton[27][2] = 28;
    automaton[27][0] = automaton[28][0] = getIndex( CODES, "." );
    automaton[27][1] = automaton[28][1] = getIndex( CODES, "-" );
    return automaton;
}

public String fix(String message) {
    int[][] automaton = buildAutomaton();
    int S = automaton.length;

    int N = message.length();
    int[] msg = new int[N];
    for (int n=0; n<N; ++n) msg[n] = ".-|".indexOf( message.charAt(n) );

    int[][] dp = new int[N+1][S];
    for (int n=0; n<=N; ++n) for (int s=0; s<S; ++s) dp[n][s] = 987654321;
    dp[0][0] = 0;

    for (int n=0; n<N; ++n) for (int s=0; s<S; ++s) {
        if (dp[n][s] == 987654321) continue;
        int ns;
        ns = automaton[s][msg[n]];
        dp[n+1][ns] = Math.min( dp[n+1][ns], dp[n][s] );
        for (int b=0; b<3; ++b) {
            ns = automaton[s][b];
            dp[n+1][ns] = Math.min( dp[n+1][ns], 1 + dp[n][s] );
        }
    }

    int best = N+47, bestn = N, bests = -1;
    for (int s=1; s<=26; ++s) {
        if (dp[N][s] < best) { best = dp[N][s]; bests = s; }
    }

    int[] fixmsg = new int[N];
    while (bestn > 0) {
        int founds = -1, foundx = -1;
        for (int ps=0; ps<S; ++ps) {
            int ns;
            ns = automaton[ps][msg[bestn-1]];
            if (ns == bests && dp[bestn][bests] == dp[bestn-1][ps]) {
                founds = ps; foundx = msg[bestn-1];
            }
            for (int b=0; b<3; ++b) {
                ns = automaton[ps][b];
                if (ns == bests && dp[bestn][bests] == 1 + dp[bestn-1][ps]) {
                    founds = ps; foundx = b; 
                }
            }
            if (founds != -1) break;
        }
        fixmsg[bestn-1] = foundx;
        bests = founds;
        --bestn;
    }

    String answer = "";
    for (int x : fixmsg) answer += ".-|".charAt(x);
    return answer;
}

RedAndBlueShades

Today, both divisions got a problem where brute force and discovering patterns is a viable strategy. In div2 it was the medium, in div1 it’s the hard problem – and the brute force solution was considerably more complicated and the pattern probably harder to recognize.

Below we’ll do the math and derive the full solution without having to guess it from a pattern.

We’ll start with blue marbles only. We have B blue marbles and we want to count all valid processes. For B=1 and B=2 the answer is clearly 1. Now let’s have a larger value B. Let’s pick one specific marble and set it aside. Imagine that we generated all possible processes for the other B-1 marbles. We can now generate all possible processes for all B marbles as follows: we can start from any process for B-1 marbles and we can decide when exactly our final marble got placed into its own bag and from where. Each such decision will give us one valid process for all B marbles.

For example, we can see that in our current process for B-1 marbles we had a bag {A,B,C,D} at some moment in time. If we pick this as our moment, this bag will now contain marbles {A,B,C,D,X}, the next step will split it into {A,B,C,D} and {X}, and from this point on we continue the original steps we did with {A,B,C,D}.

All the processes for B marbles we just created are clearly distinct: we cannot get the same one from two distinct processes for B-1 marbles.

And no processes for B marbles are missing from this collection – this is because we can take any valid process for B marbles and “undo the above” to get a valid process for B-1 marbles. (We remove the action when the last marble got its own bag and then we pretend it does not exist.)

Thus, the total number of processes for B marbles can be computed by looking at each process for B-1 marbles, finding the number of ways to add the B-th marble, and summing all those numbers of ways.

Regardless of which schedule for B-1 marbles we take, there are always exactly 2B-3 ways to add the last marble. This is because in the whole process we’ll always encounter exactly that many distinct bags of marbles. (We start with all B-1 marbles in the same bag. Each split increases the number of non-empty bags by 1, and we end with B-1 one-marble bags. Thus, there are exactly B-2 splits, and therefore exactly B-2 distinct bags being split.)

And that gives us a surprisingly simple conclusion: the number of ways for B marbles is simply the number of ways for B-1 marbles, multiplied by 2B-3.

Hence, the counts for blue marbles are the so-called “double factorials” – like factorials but you only multiply odd numbers. E.g., for B=5 the answer is 1*3*5*7.

Now let’s add red marbles. Again, we’ll do so one at a time (after all the blue marbles have already been added), and again we can do the same reasoning as above, with just one small change. When we already have a process for N other marbles and we are adding a new red marble, we can only choose one of the N-1 bags with two or more marbles as the exact moment when the red marble got its own bag.

Thus, the number of ways to add the red marbles is a simple product of consecutive integers: if there are B >= 2 blue and R red marbles, we have (B-1)*B*…*(B+R-2) ways to add the red marbles into any valid process for the blue marbles.

If B or R is too large, the answer is zero because the product will contain the value 10^9 + 7 somewhere. We just need to compute factorials and double factorials until they hit that moment. This would be slightly slow if we just did it naively, but we can easily speed it up by e.g. precomputing and storing every 10^6-th factorial. 

(We can do the same for double-factorials but we don’t have to. We can use the observations that 1*3*5*7 = 8! / (2*4*6*8), and that 2*4*6*8 = 4! * 2^4.

// omitted parts of code:
// - classes Fact and DFact that compute factorials and double-facts quickly
// - modular exponentiation and modular inverse

long singleBag(long red, long blue) {
    if (red + blue == 1) return 1;
    if (blue <= 1) return 0;
    long answer = DF.double_factorial(blue-1);
    if (answer == 0) return 0; // we already know we have too many blues

    if (blue+red-2 >= 1_000_000_007) return 0;

    answer *= F.factorial(blue+red-2);
    answer %= 1_000_000_007;
    answer *= inverse( F.factorial(blue-2) );
    answer %= 1_000_000_007;
    return answer;
}

public int count(long[] R, long[] B) {
    F = new Fact();
    DF = new DFact();

    long answer = 1;
    for (int i=0; i<R.length; ++i) {
        answer *= singleBag( R[i], B[i] );
        answer %= 1_000_000_007;
    }
    return (int)answer;
}