August 5, 2019 2019 Topcoder Open Algorithm Round 4

Easy

To start, we can try all one-digit and two-digit numbers to be sure to get rid of all special cases. (There aren’t really any special cases other than n=10 with product 0, but why not be extra safe.)

If a bigger number is the optimal answer, then clearly:

• it does not contain the digit 0 (product 0 was already obtained for n=10)
• its digits are sorted in nondecreasing order (because rearranging digits leaves the same product but makes the number bigger)

The count of such numbers is very small and we can generate and test all of them.

More precise math: if you are generating 18-digit numbers with non-decreasing digits from [1-9], the count is binomial(18+8,8) = about 1.5 million, because each number corresponds to some sequence of 18 “print” and 8 “inc” commands.

If you want to go beyond the task, a nice exercise is to look for as many ways to speed up the search as you can. To list some: After n=11 you don’t need the digit 1, as it does not change the product. The number will never contain combinations of digits like 22 or 23 (can be replaced by 4 or 6). Combinations like 25 will give you n=0 in two steps, so they are also useless for bigger goals.

The most fun is that there are still open problems related to this simple task. In particular, we do not know whether the sequences are actually infinite. For base = all zeros, the last term we know is actually the last one you found while solving the task. We know that if there are other terms, they have at least tens of thousands of digits, and it is conjectured that the sequence is actually finite. See http://oeis.org/A003001 for more.

Medium

The biggest part of solving this task is in finding a general construction that is reasonably easy to implement.

Below is a sample figure showing the construction used by the reference solution. Essentially, I always use some points on the current line that are just to the right of the input to “eat” the empty space on the line above that one. This way I’m sure I won’t get any accidental grid points into the polygon: there aren’t any between two consecutive rows.

The checker for this problem was also fun to write. I used winding number for the point-in-polygon check, and Pick’s theorem as an easy way to check whether your polygon doesn’t contain any other grid points on the inside.

Hard

The key observation is that the number of Hamiltonian cycles has to be small. Why?

If we only have one root + (N-1) leaves, we have N distinct Hamiltonian cycles starting at the root and going “to the right”. More precisely, once we choose the edge along which the cycle leaves the root, the only option is to do N-1 jumps and then to use the neighboring edge to return to the root. (The tiniest tree is a special case, as both choices produce the same cycle. This was shown in the examples and it was easy to handle.)

If we have a deeper tree, observe a deepest leaf Y. It has a parent X that is not the root, and a sibling Z that is also a leaf. We have a triangle XYZ in our graph, and there are only three other outgoing edges: from Y to the previous leaf, from Z to the next leaf, and from X to its parent. Thus, the Hamiltonian cycle has to pass through this triangle exactly once, and the previous and next vertex on the cycle will uniquely determine the order in which it visits X, Y, and Z. Hence, we can imagine that we contract XYZ into a single new node. Any Hamiltonian cycle in the new graph will correspond to exactly one cycle in the old graph and vice versa.

The previous argument can be repeated until we get a tree that is just root + leaves.

Thus, the total number of cycles is just 2 (directions of traversal) * N (starting points) * degree of the root <= 2 * 250 * 249.

In order to generate all cycles, probably the easiest implementation is using three recursive functions: “traverseLeafLeaf”, “traverseLeafRoot”, and “traverseRootLeaf” that return the unique path that traverses an entire subtree from leftmost leaf or root to rightmost leaf or root.

Then, we just sort everything, check whether the index is small enough, and output the corresponding sequence.