August 27, 2019 2019 TCO Algorithm WildCard Round

FilmSort

This problem gives a nice twist to the very standard “sort an array using swaps” in that we also need to reverse the elements appropriately.

Two of the simplest approaches that work:

1. Find out how to get the last element, appropriately rotated, into the last position of the array. In the worst case (if film n-1 starts on reel n-1, but reversed) this requires five moves.
   Repeat for films n-1 downto 2. Place film 1 into its correct place if you can.
   Total: at most 5*(n-2) + 1 moves.
2. Start by placing the films onto their correct reels, ignoring direction. (If you have something that belongs onto the empty reel, put it there. Otherwise, take any film that’s not on its reel and rewind it onto the currently empty reel 0.)
   Then, repeatedly take two films that are reversed and use the empty reel to fix both (in six moves).
   Total: at most 1.5n moves for the first phase, at most 3n for the second phase.

In either approach, you can get stuck in a situation when everything is in place except for one film that is still reversed. We claim that in that situation no solution exists. Why is this the case? Because each move of a film does two things:

• changes the parity of the number of reversed films
• changes the parity of the permutation of film numbers (i.e., of absolute values in the array you have)

Thus, the sum of those two is invariant.

Diophantine

The number 2 is the only even prime, hence the number q[0] is the only even element of the q sequence.

In the equation V+W+X+Y = Z, the right-hand side number cannot be q[0], hence it is odd.

In order for the left-hand side to be odd, we need to use q[0] either exactly once, or exactly three times. The possibility “exactly three times” is easy to process in O(n) expected time. Once we do that, we can set V=q[0] and avoid using q[0] for the other variables.

This leaves us with one fewer variables: q[0]+W+X+Y = Z.

For this equation, we can count all solutions by using the meet-in-the-middle approach: rewrite the equation as (constant + W + X) = (Z – Y), generate and remember all possible left-hand sides, and then generate all possible right-hand sides and for each of them look up the number of matching left-hand sides.

One final step is that the above solution counts each triple (W,X,Y) with distinct W, X, Y three times, but triples of the form (W,W,X) and (W,X,X) are only counted twice and triples of the form (W,W,W) are only counted once. This is easy to fix without increasing the time complexity of the solution simply by iterating over all W and X.

If we use hashsets, the implementation of this solution runs in O(n^2) expected time.

RookAttacks

The board can be divided horizontally into at most n rows that contain a rook, and at most n+1 blocks of empty rows. We will process these <=2n+1 blocks of rows one at a time, from top to bottom.

Let’s deal with the blocks of empty rows first. Within such a block of rows, almost all columns look the same, except for those at-most-n columns that contain one or more rooks. For each such column there cells in the current block of rows are attacked by at most one rook from above and at most one rook from below. Knowing the number of columns of each type would be sufficient, as we can then compute the number of “ordinary” columns by subtracting all those counts from the chessboard dimension D.

Rows with rooks are a bit trickier, but not by much. The rooks within a row split the row into several blocks of columns that do not contain a rook — i.e., subproblems identical to the one above. All we need is an efficient way to tell us how many special columns of each type are there within such a block of columns.

Thus, one possible efficient solution looks as follows:

• Sort the given rooks by columns, and for each rook precompute and store the color of the rook immediately below (if any). To make the implementation simpler, here and everywhere else “no color” can be represented as color 2.
• Compress the coordinates for columns of the chessboard. (In my solution, for each column c that contains a rook I kept the columns c-1, c, and c+1 if they were present on the board. This pays off later.)
• Create 9 Fenwick trees T[x][y] for x, y in {0,1,2}. In Fenwick tree T[x][y] store the (new, compressed) columns that have a rook of color x above them and a rook of color y below them.
  (The tree T[0][0] can be left alone, as this information is computed easier by subtracting the other counts from the total length of a range of columns, as explained above.)
• Whenever processing a block of empty rows, just query each tree for a sum of the whole interval to get the number of columns of each type you have.
• When processing a row with rooks, for each part of the row query each Fenwick tree and then add the colors of the left and right rook to each of those possibilities. Then, for each rook, update Fenwick trees for the column that contained the rook.

(In my implementation, I added two sentinel rooks in rows -1 and D, and then I simply processed the rooks one at a time instead of explicitly constructing the blocks. For each rook: 1. if there are empty rows between the previous and this rook, process them; 2. process the segment to the left of this rook; 3. if this is the last rook in its row, process the segment to its right.)

This gives us a full solution that runs in O(n log n) time.