TCO16 R1A

So, I forgot this was happening so soon… hello 3am.

750 to advance, but < 1100 registered in time.  Looked like it could be positive scores advance, but then the problem set turned out to be more like what I remember division 2 being.

I was ~250th before challenge phase having solved the first 2 problems.  ~230th after challenge phase as a number of people had their solution to the 1000pt successfully challenged.  Finally 216th, safely advancing, so no more top coder for me until May 12th.  Advance cut-off was a pretty slow time on the 250pt problem.

The top 38 people solved all 3 problems.  I was making some decent progress on the 1000pt, but I had missed a key insight regarding how simple the problem really was, so was making my life too difficult for myself as usual.

Q1) Given a time in HH:MM form where HH is 1-12 and MM is 00-55 in 5 minute steps, return HH:MM format for a ‘clock hand switch’ where the hour hand is assumed to only show integers (by flooring) rather than the usual intermediary positions.

A1) This was mostly a question of whether you could format/parse do some simple modulo math.  Split/int.Parse the input, format {0:00} for output to get correct 0 padding.  Output HH is input MM divided by 5, then if 0 use 12 instead. (This can be done by (x+11)%12+1 – but an if statement seems simpler.)  Output MM is input HH % 12 * 5.

Q2) Given a set of numbers, determine the smallest maximum difference that can be used to create P pairs.

A2) I was a bit slow writing up the code for this.  The approach I and many others used is a pretty straight forward binary search on the maximum difference required.  The test to see if it is possible takes the sorted set of values and greedily pairs subject to the current maximum difference under test where possible taking from the smallest first.  If number of pairs made is greater or equal to P, pass, else fail.

Q3) Given a tree, determine if it is possible to visit every node once starting from the root, by only jumping between nodes which are ancestor/descendent (regardless of distance) of each other.  If so return the lexicographically smallest ordering for the walk, else return empty array.

A3) So I’m pretty sure I had the first part solved, I just needed to extend my solution to determine the smallest of the many possible solutions.

I think its possible to do this problem in O(N^3) or better, but here is an O(N^4) solution which is simple and I saw pass in time.

First take the input (which is list of node parents) and construct a child list for each node and a reachability matrix.

Loop N times, for the first node you can jump to from the current node (by checking the reachability matrix) and still result in a solvable graph, add that node to solution and mark it as the current node.  (Initial current node is 0.)

Graph is still solvable if there is a walk which doesn’t visit any nodes in the existing solution.  A walk can be found by marking all nodes in existing solution as visited, then while still possible, either jump to the deepest non-visited node if available or the shallowest non-visited parent if not.  If you visit every node, success, else fail.

Where I got stuck was I wrote an O(N) check for solvable (rather than the O(N^2) check described above) but it didn’t easily extend to starting from an arbitrary location with several nodes already marked as visited.  N was 100, so an O(N^4) solution sounds risky, but the constant ends up being quite good in practice.