For A there is a clean exponential solution (mine solution is some shit tho). In C there is not that much casework. However the solution idea I have is rather tedious to code even though I really like geometry. Not super bad though.

A:

N is odd: simple greedy

N is even: Run backtracking. If the prefixes aren’t equal then greedy works (we know which number is greater, so it has to be as small as possible). If the prefixes are equal then consider all possible choices, but make sure that the digits in the equal prefixes are somehow sorted (in nonincreasing order for example).

Odd length is simple. For even length, we will check all possible prefixes that will be shared for our numbers. For their first different digits, brute force all pairs that minimize the difference. The remaining suffix can be constructed greedily.

The official analysis provides a $$$O(2^{N/2})$$$ but for the worst case where each digits from 1 to 9 has 4 occurrences, we can further improve it to $$$3^9$$$ cases (choosing 0, 1 or 2 pairs for each digit).

N is odd: trivial.

N is even: I sorted the digits, and used a recursion. In any recursion where we are trying to minimise difference, the leading digits must be adjacent in the sorted list. Try each adjacent pair, taking care not to use 0s in the first case. If the adjacent pair are the same, you repeat the recursion on the remaining digits. If the adjacent pair are different, you are then finding the smallest and largest possible numbers from the remaining set.

I used memoization just to be sure but I probably didn't need to.

It works. Proof: let's consider filling rows one by one. Suppose that for some row $$$i_1$$$, we put mark into column $$$j_1$$$ and don't into $$$j_2$$$, where in column $$$j_2$$$ we need to put strictly more than into $$$j_1$$$. Then in some of the next rows (say, $$$i_2$$$), we will have to put mark into column $$$j_2$$$ and not into $$$j_1$$$. Then we can instead put marks in $$$(i_1, j_2)$$$ and $$$(i_2, j_1)$$$ instead of $$$(i_1, j_1)$$$, $$$(i_2, j_2)$$$

I also did this. Used priority queues to construct the initial grid row by row: if at any stage you run out, IMPOSSIBLE, otherwise you have a starting grid.

Then my approach was similar except that I moved all /\ pairs to the ends of rows and columns and all \/ pairs to the start, and then repeated that 20 times to iteratively move any newly created problems leftwards/upwards until finally there were no problems left.

They have mentioned this approach in "Flip Flop" section of the Analysis and show that it's finite and the asymptotics are enough. They didn't however mention greedy which makes this task even easier (since flows are only helpful if you solve the task the intended way I feel).

This is the reason why I personally disliked this task since it clearly has two ways two go about it with one significantly easier than the other one. From reading the analysis I got the impression that they realized that there exists this alternative solution quite late in the problemsetting, and I'm not sure why the task was kept after that or not swapped with the first one.