So looking through some of the stats it appears that round 1B was easier than 1A and a quick look at the questions would have me agreeing.
Q1 – a very simple question from a problem solving point of view, what made it different was that reading the input involved some real parsing. Also the format of the question lends itself to a tree data structure which most people would have to roll their own. Only performance optimisation I can see is ensuring to put the animal attributes into a dictionary for fast lookup – looking at the constraints of the large data set, I’m not sure that is even needed but it probably wouldn’t hurt. As well as solving the next problem, almost everyone who got through solved at least the small for this problem.
Q2 – This looks very easy, as excepting the case where the number is currently entirely in non-ascending order (starting from the left) (in which case the answer is reverse, push all 0’s to be after the first-non-zero digit and insert a 0 after the first digit), the next number can always be found by finding the first descending digit (starting from the right) and swapping it with the next highest digit to its right, and sorting the rest of the digits to the right into non-descending order (starting from the left). given this is n log n operation the large data set constraints are trivial. Basically everyone who got through solved this problem.
Q3 – This appears to be the only algorithmically complicated problem in the set, and the real differentiator between those who got through and those who did well. Just solving the small data set here (in addition to the first 2 questions) was enough to get 130th place. My initial analysis of this question appears to be the correct solution after looking at a couple of the top answers, the problem however does take a bit of skill to implement correctly given the amount of time you likely have left after doing the first 2. The correct approach is basically to perform a breadth first search starting at each node, recording the minimum depth to get a certain number ending (or starting) at a specific location. The input data set can be transformed into two independent directed graphs, but you might as well just treat it as one. The trick with the breadth first search is only that you need to terminate each branch of the search if it discovers a possible number at the same or greater depth at the same location (same depth needs to be considered for answer ordering though). In order to satisfy the ordering constraints and not perform an exponential backtrack to create the solution, the easiest way is to store the best string for each possible number in a separate dictionary and to store the best strings for each location and number as well. This apparently performs okay under the constraints and I suspect would likely have been where I failed on this question if I was competing in practice. I would likely not have considered the scenario of an entire grid of 1’s and + signs and being asked to find the answer for 250. Backtracking the breadth first search in this case would result in the code never finishing as at each location it wouldn’t know which branch has the better sort order and so would have to try each one.
It is probably also possible to avoid constructing the strings and instead solve the second half of the problem as a separate problem. I suspect it is probably also algorithmically superior.