August 18, 2020 2020 TCO Round 3B Editorials

VisitALot

The last example shows a simple zigzag pattern that visits all cells in an empty grid: just traverse row 0 left to right, then row 1 right to left, then row 2 left to right, and so on.

We can easily adapt this pattern to grids with obstacles: whenever we encounter a row that contains an obstacle, we’ll simply stay on the same side. Here’s an example path that avoids three obstacles:

********
...X...*
********
********
********
*X......
*..X....
********

If we have a grid with at least six rows, this pattern is guaranteed to visit at least half of the grid: we have at most three rows with one cell visited and at least three rows completely visited.

The same pattern transposed solves all grids with at least six columns.

Finally, we can easily verify that for any grid that is at most 5×5 going around the boundary of the grid solves the problem. (E.g., the 5×5 grid has 16 empty cells on its boundary and only 9 possibly-blocked cells on its inside.)

ShortBugPaths

For small N we could easily solve the problem using dynamic programming: Let dp[x][r] be the number of valid paths that start at (r,c) and have length x. Then, dp[x+1][r] is the sum of dp[x][nr][nc] over all (nr,nc) reachable in one step from (r,c).

The full solution will simply speed up this solution by making an observation about equivalence and using it to reduce N to a manageable size.

Remember that both the maximum jump length L and the number of jumps J is small.

Imagine a board where N is huge, and imagine a bug that starts its journey at (3, some column around the middle). Clearly, the exact column number does not matter. Regardless of what it is, the bug’s world looks exactly the same: there is more than enough space to the left, right, and down, and there is a seemingly infinite world boundary that limits it from going more than three steps upwards.

Similarly, all points that are more than L*J steps from each side are equivalent: a bug that starts here is completely unrestrained.

Now, instead of special-casing the calculations for the corners, sides and middle of a huge grid we can make the following observation: Let M = 2*L*J + 1. Suppose we do the basic dynamic programming for an M times M grid. Then, any N times N grid with N > M can be constructed from the M times M grid by inserting additional copies of the middle row and then additional copies of the middle column of the grid — all the extra cells in the bigger grid will contain values equal to those we already computed.

This gives us an easy formula for the final answer: instead of explicitly constructing the huge grid, we just add the sum of the inserted cells to the result.

If we neglect the cases with small N, the time complexity of this solution is O(L^2 * J^3).

HorseTicket

We can start by applying a standard technique that can be used whenever we are supposed to construct an x-th string in lexicographic order: we will construct the string from left to right, and we’ll use some counting to do the search efficiently. For example, suppose we are looking for a string with id=47 among some strings of lowercase letters. The search can look as follows:

• We have the empty string at the beginning, so we are looking for an object with id=46 in the rest of the list.
• Then we have all strings that begin with ‘a’. Suppose we can count that there are 25 of those. In the new list (after we got rid of the empty string) these must have ids 0 to 24, and the important observation is that we do not care which is which – they are not the object we are looking for, so we can discard them as a block. We are now looking for an object with id=46 – 25 = 21 in the rest of the list.
• We have 10 strings that begin with ‘b’. We discard the whole block and we are looking for an object with id=11 in the rest of the list.
• We have 50 strings that begin with ‘c’. Thus, the one we are looking for is among them.
• The string “c” has id=0 in the current list. We discard it and now we want id=10.
• Now we would look at prefixes “ca”, “cb”, “cc”, …, until we find the block that contains the correct second letter, then we would move to the third letter, and so on.

The time complexity of the solution that follows this pattern is O(alphabet size * maximum answer length * maximum time needed for the counting). In order to apply this solution, we need an efficient way to count the valid objects with a given prefix.

In our problem, if we have a prefix of the ticket, it determines a subset of races from which we already picked a horse, and thus its complement: the races that are still available. Thus, the counting problem we need to solve is the question “given these races, how many valid tickets are there?”

If the number of races were small, we could do exponential dynamic programming: for each subset of races, determine the number of valid tickets that only use horses from these races. However, this would be too inefficient for the given constraints, so we need to come up with a smarter way of counting.

One efficient way of counting is to group the tickets by length. Given the set of races, for each x we will ask the question: in how many ways can one select a set of x horses from x different races? If we denote this count as c[x], the total number of tickets is then simply the sum of c[x]*x! over all x.

And the values c[x] can indeed be computed using dynamic programming: If we have no races at all, we have c[0]=1 and c[x]=0 for x > 0. If we already know the c[] values for some set of races and a new race with h horses appears, the new c[x] will be the old c[x] plus h times the old c[x-1], because we can take any old set of x-1 horses and add any one of the new h horses to form a new valid set of x horses.

The last bit that needs mentioning is that we need to be careful about overflows. The counts of options can be huge and we do not have the luxury of being able to count modulo something, we need the exact counts. Or, more precisely, we need the exact counts as long as they are small. Let MAX=10^15 be the maximum index we can be interested in. One simple trick to do in order to avoid overflows is to implement helper functions for addition and multiplication that return MAX+1 whenever the exact result exceeds MAX: once any set of options is larger than MAX, we don’t need its exact size, we know that it is large enough to contain the option we are looking for.

If there are R races, the time complexity of counting the number of valid tickets with a given prefix is O(R^2). The maximum ticket length is R. If we use H to denote the alphabet size (the number of distinct horses), we know that the solution runs in O(HR^3), and as R <= H, it runs in O(H^4).