January 26, 2019 Single Round Match 748 Editorials

The round was held on 26th Jan, 2019. Thanks to misof for the problems and the editorials.

CopyingHomework

In open-ended problems like this one, the best course of action is usually choosing the solution that’s the easiest to implement. In this case, probably the easiest solution is to pick five fixed changes that sum to zero, such as (-1,-1,-1,-1,+4).

def solve(friendsHomework):
    a, b, c, d, e = friendsHomework
    return ( a+1, b+1, c+1, d+1, e-4 )

Yllion

This problem is also educational in that it introduces you to a little-known but very nice system to name those intermediately large numbers (by which I mean numbers huge to a layperson and still tiny to a mathematician who works with large numbers). Knuth’s system is really easy to use, and our implementation of the solution will illustrate that nicely. The only special case in the whole system is the prefix “one” that is used whenever “ten” isn’t. Other than that, everything is very logical.
Each of the strings corresponds to some exponent of 10, and the exponent for the whole number is simply the sum of all those exponents. For example, if “myllion” is 10^8 and “tryllion” is 10^32, “myllion tryllion” is 10^(8+32). Thus, in order to convert a string to the exponent, we simply split the string into words and sum the exponents associated with those words.
And the other conversion (exponent back to string) is just the same thing in reverse. The exponents themselves are powers of two, so we simply look at those. For example, if we want to express 10^40 as a string, we need to write 40 in binary and see which powers of two are present. In our case, 40 = 32 + 8, so the two words we’ll use are “myllion” and “tryllion”. All that remains is to concatenate them in the right order (largest last).
In my implementation (shown below) I’m using a regular expression to check which of the strings “ten”, “myriad”, etc. are present in the string. This is just me being lazy. Another possible implementation is to split() the input string into pieces and then use standard string comparison manually, or a map that directly assigns the right exponent to each of the given strings.

static String[] names = {"ten", "hundred", "myriad", "myllion", "byllion",
    "tryllion", "quadryllion", "quintyllion", "sextyllion", "septyllion",
    "octyllion", "nonyllion", "decyllion"};
public int getExponent(String a) {
    int answer = 0;
    for (int d=0; d<names.length; ++d) {
        if (a.matches(".*\\b" + names[d] + "\\b.*")) answer += 1 << d;
    }
    return answer;
}
public String makeNumber(int exponent) {
    String answer = "";
    for (int d=1; d<names.length; ++d) {
        if ((exponent & 1<<d) != 0) answer = answer + " " + names[d];
    }
    if (exponent % 2 == 0) return "one"+answer; else return "ten"+answer;
}
public String getPower(String a, String b) {
    return makeNumber( getExponent(a) + getExponent(b) );
}

EraseToGCD

This problem is an easy exercise in dynamic programming. Imagine that you are walking along the given sequence and taking decisions which numbers to keep and which ones to erase. At any moment, your state can be described by two variables: how many elements you already processed, and if you kept any, what is their GCD.
(Note that the reason why we can do this is that GCD is associative. Namely, if

 GCD(a[0],...,a[k-1]) = g, then GCD(a[0],...,a[k]) = GCD(g,a[k]).)

For each of the states described above we compute the number of ways in which it can be reached. Then, the answer is the number of ways to reach the state (I’m at the end of the whole sequence, I kept some numbers with GCD=goal.)

public int countWays(int[] S, int goal) {
    int[] oldc = new int[1001];
    for (int d=1; d<=1000; ++d) oldc[d] = 0;
    for (int s : S) {
        int[] newc = new int[1001];
        // count ways if we erase this element
        for (int d=1; d<=1000; ++d) newc[d] = oldc[d];
        // count ways if we append this element to a preexisting sequence
        for (int d=1; d<=1000; ++d) { int g = gcd(d,s); newc[g] += oldc[d]; if (newc[g] >= 1_000_000_007) newc[g] -= 1_000_000_007;
        }
        // count the sequence that starts here
        ++newc[s];
        if (newc[s] >= 1_000_000_007) newc[s] -= 1_000_000_007;
        oldc = newc;
    }
    return oldc[goal];
}

UnreliableRover

How to deal with the question marks in the input? An obvious solution would be to try all possibilities for each of them. If there are q question marks, this would give us 4^q possibilities to try. Sadly, that is too much for the constraints in this problem. The key observation is that we can be a bit smarter and try only 2^q possibilities: for each ‘?’ we will only choose whether the movement was horizontal or vertical.
Why can we do that? Why doesn’t the exact direction matter?
First of all, note that the movements are commutative and associative. In human words, their order does not matter. If we rearrange the order of some movements, the rover will end up in the same spot. (Each movement is a vector, and the result is always the sum of those vectors.) Thus, we can rearrange the input to move all ‘?’ movements to the end.
Now, let’s solve the task if there are no ‘?’s. First, clearly the two dimensions are independent. We can consider all ‘N’+’S’ movements to find where we can be in one direction and separately we can look at ‘E’+’W’ movements for the other direction. Then, any combination of those will be possible. Thus, the answer is (the number of possible x coordinates) times (the number of possible y coordinates).
And it’s even simpler than that: in each coordinate, the reachable cells after each movement will be contiguous. This is easy to show by induction. In the beginning, there is only one cell where you can be. And if you can be exactly in any one of the cells in [x1,x2] and you are told to move by a number of steps that is in [a,b] to the right, you can end anywhere in [x1+a,x2+b]. (Same goes for moves to the left.) Also note that the length of the range grew by exactly |b-a|.
Thus, we can now process all “NEWS” commands and calculate the dimensions of the rectangle that contains the rover after the last of those commands. Note that we don’t care about its exact location, only the dimensions matter.
Now we get back to the ‘?’ commands. Suppose instead of those we have some ‘H’ commands (move horizontally) and some ‘V’ commands (move vertically). Thanks to the fact that for these commands minSteps=0 we can continue in the same way. If you can be anywhere in the range [x1,x2] and you get a command “move by at most d in either direction”, you will then be able to end exactly anywhere in the range [x1-d,x2+d]. Thus, the final area will always be a rectangle. Additionally, for the ‘H’ and ‘V’ commands the center of that area always remains in the same spot.
In order to get the total area, we need to try all 2^q possibilities for which ‘?’ commands are ‘H’ commands and which are ‘V’ commands, and we need to compute the union of these rectangles. This is very simple (i.e., we don’t need general rectangle union) because 1. these rectangles all share the same center, and 2. if we sort them by width they are also sorted by height in the other direction, because the total length of all ‘?’ commands is always the same, so the more we assign to ‘H’, the less remains for ‘V’ and vice versa. Thus, essentially all we need to do is to generate 2^q points and sort them.

Rectoggle

In order to tackle this problem, you need at least some basics of combinatorial game theory – in particular, you should already be familiar with the Sprague-Grundy values of positons. If you aren’t familiar with this concept, you probably won’t be able to follow the explanation.
So, we have a game in which we toggle some lights. The first observation is that this game is finite. This is because of the rule that whenever you toggle some lights, the one that is on the bottom right must go off. (Let’s assign weights to cells in such a way that the weight of a cell (r,c) is 1 + the sum of all other cells in the rectangle from (0,0) to (r,c). Then, each move decreases the total weight of lit cells.)
The second, and much more important observation is that the lit cells can be considered independent subgames. This is not obvious at all — after all, some moves toggle multiple lit cells, right? The key observation here is as follows: Imagine that instead of toggling lights the cells of the grid are boxes. In the beginning, the lit cells turn into boxes that contain a marble. The rule for this new game: “Pick any valid rectangle such that its bottom right corner has a marble. Remove that marble and put a marble into each other cell in that rectangle.”
The two games are almost identical. The similarity is that the parity of marbles in the new game = the state of the light in the original game. And we can use this similarity to argue that the winning strategies for both games are essentially the same. Whoever would win from a position in the LED game, wins from the position in the marble game by playing the same moves. Whenever there are two marbles in a cell, these don’t influence the outcome because they represent two identical and independent games. The player who would be winning if the two marbles weren’t there will also win if they are there. All they need to do in addition to their original strategy is to mirror their opponent’s turns that play one of these two independent games.
Thus, we can solve the Rectoggle game in the standard way: by assigning the Sprague-Grundy value to each lit cell and then checking whether the bitwise xor of those values is zero or not.
Of course, assigning those values isn’t trivial: we have 10^10 possible cells. The author’s solution works for larger dimensions as well, but constraints were kept low to prevent overflows and to make it easier to get accepted with a solution that is based on guessing and successfully precomputing the patterns in SG values.
As I already mentioned patterns, this was indeed one way to go. In order to find out how the game behaves, it is almost always a good idea to implement the standard solution (i.e., memoized recursion that computes the SG value of a state by trying all possible first moves from that state) and to print and examine the values for small positions.
To some surprise, one thing we can experimentally discover is that maxrows and maxcols don’t really influence the game as much as we would expect. For example, the game plays exactly the same for maxrows=4 and maxrows=7. (What that means is that even if we allow some additional moves, the winning player doesn’t need them and for some reason they don’t help the losing player not lose.)
A more general version of the pattern that can be observed is as follows: the game doesn’t change if we lower maxrows and maxcols to the largest power of two that’s less than or equal to their original values. Then, the pattern of SG values is a periodically repeating maxrows*maxcols rectangle. Additionally, in that rectangle we can make two more observations: First, the values in its first row/column are powers of two (more precisely, it’s always the largest power of two that divides (index+1)), and second, the other values are uniquely determined by the first values in their row and column. That is, each row that starts “1” looks exactly the same, and so on.
If we assume that these observations are true, it is possible to precompute and store all the 17*17 different SG values we might need: essentially, just do the standard solution but only for the cells you don’t “know” yet.
Of course, there is a nicer way to solve the task completely without relying on unproved assumptions. The key concepts here are “NIM multiplication” and the “Tartan theorem”. Much as the SG values can be used to argue about sums of independent games, there is also a known way to handle “products of games” in some specific sense.
Consider the one-dimensional version of the game: you have a line of LEDs and only one constraint maxcols. For this version, we can easily prove by induction that the SG values match what we saw in the first line of the 2D matrix we printed above. Then, we can note that our two-dimensional game is the product of two such one-dimensional games: whenever we flip a set of cells in the 2D version, it is the carthesian product of a set we could flip in one one-dimensional game and a set we could flip in the other, and vice versa. The Tartan theorem shows that all such products of games can be solved in the same way: the SG value of a position in the 2D game is the nim-product of the SG value of the row position in the row game and of the SG value of the column position in the column game. Here, the nim-product is a specific multiplication-like function that is the same for all such games, regardless of the specific rules of the 1D games that were multiplied.
For this particular solution, a full implementation of the nim-product wasn’t necessary, because all our 1D SG values are powers of two and those are easy to nim-multiply.