Selection sort using the following procedure. Identify the thinnest book. Move all books that are on top of it to the right pile, using your left hand. Pick up the thinnest book in your right hand. Move the books you moved to right pile back to the left pile (using left hand). Put the thinnest book on the right pile. Repeat for the second-thinnest book, and so on. You now have the books reverse-sorted on the right-hand pile, so can move them all to the left pile.

Insert all the words for both players into a trie. As the trie is built, mark each node to indicate whether it is a valid prefix for each of the players. Then recursively (bottom-up) determine whether each state is a winning state for each player. It is a winning state if there is a child node which is a valid prefix for the player and which is a losing state for the other player.

Sort all possible rotations of all rows, using the standard suffix array technique. This allows every rotated row to be assigned a rank. Now for each column we can create a new string, where the symbols are the ranks of the rows if that column should be moved to the front. We again use a suffix array to identify the optimal rotation of each column, and pick the best across all columns.

Running time O(n log n) (although my suffix array implementation is actually O(n log² n)). I had to do a bit of micro-optimisation to make it fast enough.

We solve it by DP, deciding how to handle each cell in turn, left to right then top to bottom. The state is whether each bottom-most handled cell has vertical tape in it, and whether the previous cell has horizontal tape it in it, for $$$2^{m+1}$$$ states (it could be reduced slightly, since the last cell can't have both horizontal and vertical tape). We then consider each possible way to handle the next cell (new horizontal or vertical tape, or extend existing tape).

Running time $$$O(2^m nm)$$$.

This one gave me the most trouble. Build the tree bottom-up, a row at a time. Maintain a persistent segment tree with an item per entry in the bottom row, which is 1 if the entry is the left-most child of some element of the current top row, or 0 otherwise. Adding a new row involves setting one value from 1 to 0. Because it is persistent, we can do the following queries:

1. Given any element in the bottom row, determine its ancestor on the kth row.
2. Given any element in the tree, determine its left-most descendant in the bottom row.

The LCA of two nodes is either the higher of the two (if one is an ancestor of the other), or it is the LCA of their left-most descendants. We can find those descendants, then use binary search with the first query type to find the level containing the LCA.

This is O(n log² n). I believe it could be improved to O(n log n), by first constructing a compressed tree containing the bottom row and all the a[i]'s, and then using standard LCA algorithms on that tree.