May 11, 2021 Single Round Match 805 Editorials

GalleryIllumination

The gallery is small enough so we can afford to use brute force: iterate through the whole area, and each time you find a light, traverse its row and column to mark the cells it illuminates.

In order to avoid unnecessary mistakes when copying and pasting, a good way of implementing the iteration in four directions is to enter those directions as constants. Then we can avoid code duplication and those mistakes that come with it. See the sample implementation below.

In the implementation we start at the light and walk in each of the four directions until we hit either the edge of the warehouse, a wall, or another light. Note that we DON’T stop upon encountering an empty lit cell, as that cell could have been lit from another direction.

(We can stop at another light instead of continuing on, because the following cells in that direction will be illuminated by that other light anyway. Doing so actually improves the time complexity of our solution: if we only stop at walls, the solution needs O(N^3) steps for an NxN warehouse but if we also stop at other lights the time complexity improves to O(N^2) because now each cell is illuminated from each direction at most once.)

    public int countDarkCells(int R, int C, String[] floorPlan) {
        int[] DR = {-1, 1, 0, 0};
        int[] DC = {0, 0, -1, 1};
        boolean[][] lit = new boolean[R][C];
        for (int r=0; r<R; ++r) for (int c=0; c<C; ++c) {
            if (floorPlan[r].charAt(c) == 'O') {
                for (int d=0; d<4; ++d) {
                    for (int i=1; i<50; ++i) {
                        int nr = r + i*DR[d], nc = c + i*DC[d];
                        if (nr < 0 || nr >= R || nc < 0 || nc >= C) break;
                        if (floorPlan[nr].charAt(nc) != '.') break;
                        lit[nr][nc] = true;
                    }
                }
            }
        }
        int answer = 0;
        for (int r=0; r<R; ++r) for (int c=0; c<C; ++c) {
            if (floorPlan[r].charAt(c) == '.' && !lit[r][c]) ++answer;
        }
        return answer;
    }

CubeTower

Cube volumes look as follows: 1, 8, 27, 64, 125, 216, …

If we look at the differences between the volumes of consecutive cubes, we see the following sequence: 7, 19, 37, 65, 91, … (E.g., the 91 is 216 minus 125.)

This sequence is obviously increasing. The formula is easy to derive: the difference between (x+1)^3 and x^3 is 3x^2 + 3x + 1, which is clearly an increasing function.

Suppose that in our tower we have two cubes: a small cube with side x and a big cube with side y >= x+2. What happens if we take cubes with sides x+1 and y-1 instead? The total height of the tower will remain the same and the total volume will decrease. The height is the same because (x+1)+(y-1) is the same as x+y. The volume decreased because the amount added by going from x to x+1 is smaller than the amount removed by going from y to y-1. (Here we are using the observation from the previous paragraph. The amount of volume we added is earlier in that sequence than the amount of volume we removed.)

If you show me any tower, I will look at the smallest and the largest cube in your tower. If their sizes differ by two or more, I will show you how to make a tower with a smaller volume: do the change mentioned in the previous paragraph. Thus, your tower could not have been optimal.

So, now we know that in the tower with the smallest total volume the cubes must be as uniform as possible: the smallest cube and the largest cube must differ by at most one. And luckily for us, there is always only one collection of cube sizes that has this property. If the number of cubes N divides the tower height H, all cubes have the same side length A = H/N. If H divided by N is A with a remainder of R, we will take N cubes of size A each and then we’ll add 1 to R of them.

Now let’s look at the tower with the largest possible volume.

Let’s look at what’s essentially the inverse change to the one we did above. Suppose we have two cubes: a smaller-or-equal cube with side x > 1 and a bigger-or-equal cube with side y >= x. What happens if we take cubes with sides x-1 and y+1 instead? Again, the total height will not change. But this time we made one cube smaller by some amount of volume and the other cube bigger by some strictly larger amount of volume, so the total volume of the tower is now bigger.

Thus, as long as we have at least two cubes with side > 1 in our tower, we can make the volume bigger by swapping some two cubes as shown above. And therefore in the tower with the largest possible volume we must have N-1 cubes with side=1 and one cube with side=H-(N-1).

All that remains is to calculate the volume for each of the two collections of cubes we found and to output their difference.

ThreeDChessRooks

Each move changes exactly one coordinate of a rook. 

Thus, Boris’s rook can capture Wanda’s rook if and only if they have (before Boris’s move) exactly two coordinates in common.

Now let’s look at the situation before Wanda’s move:

If the cells with rooks differ in all three coordinates, the interaction cannot happen. (After Wanda’s move her rook will still have at least two coordinates different from Boris’s rook.)

If the two rooks start in cells that have exactly one coordinate equal, the interaction can always happen. Without loss of generality, suppose Wanda starts at (x, y1, z1) and Boris starts at (x, y2, z2) with y1 != y2 and z1 != z2. Then there are exactly two ways in which the interaction can happen: Wanda can move her rook either to (x, y2, z1) or to (x, y1, z2), and Boris will then move his rook to the same cell.

If the two rooks start in cells that have exactly two coordinates equal, the interaction can usually happen. One key part of this problem is to understand why the previous sentence said “usually” and not “always”.

The case when the rooks start with two matching coordinates is essentially one-dimensional. Why? Without loss of generality, suppose Wanda starts at (x, y, z1) and Boris starts at (x, y, z2) with z1 != z2. If Wanda’s move changes the x or y coordinate of her rook, the rooks now differ in two coordinates and Boris cannot capture. Thus, in order for the interaction to happen Wanda must change the z-coordinate of her rook, so both her rook and Boris’s rook will have to move along the same line.

This is usually possible, as shown in the three examples below.

W..B...  <- Wanda’s rook has two valid ways to move (right by 1 or right by 2)

.W.B...  <- Wanda’s rook has two valid ways to move (left by 1 or right by 1)

WB.....  <- Wanda’s rook has zero valid ways to move

The cases when Wanda cannot move are the cases when Boris’s rook blocks her off completely within the row. This happens when she is at one of the ends of the row and Boris’s rook is immediately next to her. Thus, the bad cases are precisely the cases in which EITHER Wanda starts at (x, y, 0) and Boris starts at (x, y, 1), OR Wanda starts at (x, y, C-1) and Boris at (x, y, C-2).

(Before the round, an expected common source of implementation mistakes was that some people will implement a solution that just counts all pairs with 1 or 2 coordinates in common, notice that it fails the last example with C=2 and then special-case C=2 instead of thinking about why exactly the answer for that example is 0 and not 2. The challenge phase may be eventful.)

Thus, the final answer is (the number of pairs of points that share exactly one coordinate) + (the number of pairs of points that share exactly two coordinates) – (the number of bad pairs of points as described above).

The number of bad pairs is easy to compute in expected O(N) time: use a hashmap to store the number of times each cell occurs in our collection, and then iterate over all cells and each time you see a coordinate that is 0 or C-1 look how many other cells in our collection have that coordinate 1 or C-2 and the matching other two coordinates.

From the above hashmap we can also calculate the number of pairs of points in our collection that share all three coordinates. For each pile of points we look at its size x and calculate that on this pile we have x*(x-1) ordered pairs of points that share all three coordinates.

Now suppose we place all our points onto different piles where on each pile the points have the same x and y coordinate. Again, we can look at the size x of each pile and add the x*(x-1) ordered pairs to our running total. This way we can count ordered pairs of points that share at least the coordinates x and y. We can do the same with (x,z) and (y,z) coordinates and we will have counted the total number of ordered pairs of points that share at least two coordinates.

(Again, we use a hashmap for the counting. The key is the pair of coordinates we are currently looking at, the value assigned to the key is the size of the corresponding pile. For each point we compute the corresponding key and increment its pile size.)

The only problem with the above way of counting is that we counted each pair that share exactly two coordinates once, but we also counted each pair that shares all three coordinates three times. Luckily, we already know the count of those pairs, so we can subtract it three times and get the number of pairs that share exactly two coordinates.

The number of pairs with exactly one coordinate in common is calculated in the same way, only this time we make piles based only on the value of a single coordinate. Again, we have counted not just the pairs we want but also the pairs we counted previously, so we make the appropriate subtractions.

This way of counting is essentially a very simple application of the principle of inclusion and exclusion.

In the implementation I had a function countPairs(wx,wy,wz) that divided all N points onto piles (i.e., inserted them into a hashmap) based on the triple (wx*X[i], wy*Y[i], wz*Z[i]). This way you can then reuse this functions for all types of counting: e.g., countPairs(1,1,1) only counts pairs that share all three coordinates while countPairs(1,0,0) + countPairs(0,1,0) + countPairs(0,0,1) counts all pairs that share at least one coordinate (and overcounts the pairs that share more than one).

SubmultiplesOfN

Suppose we want to check whether a string X is a subsequence of a string Y. This can be done greedily: start with the first character of X being active, read Y, and each time you see the active character take it and move the active character to the next character of X, if any. If you finish X, return true, if you finish Y, return false.

For each X that does occur in Y the letters of Y you took while looking for X will give you one specific occurrence of X in Y. We will call it the canonical occurrence. (Note that if we look at the sequence of indices into Y where we took a letter, this sequence is the lexicographically smallest among all such sequences for occurrences of X in Y.)

The main trick of problems like this one is that we can make sure we count each subsequence only once by only counting the canonical subsequences. 

Now consider all possible paths that look as follows: we start before the beginning of the given string. We then repeat several times: choose a character and jump to the first occurrence of that character that is to the right of your current position. We can stop whenever we want.

Clearly, each such path gives us some canonical occurrence of a substring and vice versa. Thus, our task can now be rephrased as “count those ways of jumping that produce multiples of N”.

One final observation is that when we have already jumped on digits of some number X and now we jump to another digit d, the new number we have is (10X + d). The remainder this number gives modulo N is the same as the remainder given by 10*(X mod N) + d. Thus, the new remainder modulo N depends only on the old remainder modulo N.

And this gives us the dynamic programming formulation we were looking for. We will compute the values dp[x][y] = the number of ways in which we can end our jumping at index x in such a way that the number we jumped on had the remainder y. The answer is then the sum of all dp[x][0].

The implementation below does this by forward propagation. This is a less standard way of doing DP but it matches more closely the explanation given above.

One final detail: in order to jump efficiently we can precompute, for each start of the jump and each digit, the destination of the jump. This can be done in linear time by going back through B, but doing it in quadratic time and caching the result (as opposed to recomputing each of them N times) might also be fast enough.

    int MOD = 1_000_000_007;

    public int count(String B, int N) {
        int L = B.length();
        int[] D = new int[L];
        for (int i=0; i<L; ++i) D[i] = B.charAt(i) - '0';

        // precompute jump destinations
        int[][] nxt = new int[L+1][10];
        for (int d=0; d<10; ++d) nxt[L][d] = L;
        for (int i=L-1; i>=0; --i) {
            for (int d=0; d<10; ++d) nxt[i][d] = nxt[i+1][d];
            nxt[i][D[i]] = i;
        }

        // compute the dynamic programming
        int[][] dp = new int[L+1][N];
        for (int d=1; d<10; ++d) dp[ nxt[0][d] ][ d%N ] = 1;
        for (int i=0; i<L; ++i) for (int n=0; n<N; ++n) {
            for (int d=0; d<10; ++d) {
                int j = nxt[i+1][d];
                int z = (10*n + d) % N;
                dp[j][z] += dp[i][n];
                if (dp[j][z] >= MOD) dp[j][z] -= MOD;
            }
        }
        int answer = 0;
        for (int i=0; i<L; ++i) {
            answer += dp[i][0];
            if (answer >= MOD) answer -= MOD;
        }
        return answer;
    }

TwoGalaxies

The center of each galaxy is clearly either one of the given points or the midpoint for two of the given points. This gives us C = O(N^2) candidates for the galaxy centers. (At the beginning we’ll multiply the coordinates of each point by 2. Once we do so, all candidates will have integer coordinates.)

Once we have the candidates, we can iterate over all pairs of points and assign each pair to the candidate that is at its center. (We will include pairs in which both points are the same.) This will tell us the size of the largest possible galaxy for each of the candidates. Note that each of the N*(N+1)/2 edges is only assigned to one candidate. 

We will call a candidate “large” if its maximum galaxy has at least N/2 points and “small” otherwise. Clearly, in each valid solution at least one of the two centers must be large. As each large candidate must get at least N/4 edges, there can only be O(N) large candidates and thus there are only O(N^3) pairs of candidates in which at least one candidate is large.

Given two candidates for the galaxy centers, how do we verify whether we can actually have a valid solution?

First, if either or both candidates are among our N points, we need to decide between two cases: either the point is its own mirror image in the galaxy with itself as a center, or it belongs to the other galaxy where it has a pair. We will try each of these (at most four) options separately. Once we made the choices, we know that all the remaining points must form disjoint pairs, each assigned to one of the galaxies.

(This is a place where it is easy to make a mistake: it is not correct to assume that if we have a candidate X and one of the points at X, we should assign that point to X. Consider ten points on a line at coordinates 0, 997, 998, 999, 1000, 1003, 1006, 1007, 1008, and 2000. The only solution is to have galaxy centers at 1000 and 1003. But if we assign the points at 1000 and 1003 to their respective galaxies, we will have nothing to pair with 1006. The only valid solution is to assign {0,997,1003,2000} to the galaxy centered at 1000 and {998,999,1000,1006,1007,1008} to the galaxy centered at 1003.)

Consider the graph formed by our N vertices minus those we already covered as singletons. Suppose we have red edges connecting the pairs that can belong to one galaxy and blue edges connecting the pairs for the other galaxy. Clearly, each point has at most one red and at most one blue edge. Thus, all we can have are isolated points, even-length alternating cycles and alternating paths. As we want to divide all points into pairs, we are looking for a perfect matching. Our hand is more-or-less forced. If there is an alternating path with an odd number of vertices (including the special case of just a single isolated vertex), there is clearly no solution. For each alternating path with an even number of vertices and for each cycle (can there really be one?) we take every second edge.

One thing that remains is to make sure we weren’t forced to assign all points to the same galaxy, keeping the other one empty. If that is not the case, we have found a viable pair of candidates.

As the above check can easily be implemented in O(N) time, even without a finer analysis of possible point locations and candidate sizes we have an upper bound of O(N^4) running time for our solution.