TC SRM 477

As is usual with SRM I didn’t do this one.  However, I figure I might keep writing up blogs until next years TCO.

Q1) Given a boolean rectangular array which maps to a hexagonal grid by shifting every second row half an entry to the right, determine the number of edges between true and false exist.

A1) This is easy enough, its a simple case of walking each cell and checking its 6 ‘neighbours’ and incrementing a counter if its not the same.  Once complete divide answer by 2.  The only difficulty is making sure you don’t screw up the determination of the 6 neighbours, which is different depending on whether the current cell is in an odd or even row.

Q2) Given a list of numbers, determine the greatest number of distinct pairs which can be selected such that all such pairs are the shorter sides of a integer sided right triangle and have a gcd of 1.  Numbers are all less than 1 million and worst case there might be 1250 numbers (less if they aren’t all single digit – maximum of 350 6 digit numbers).

A2) The constraints on the pairs are pretty significant, and could easily rule out most of the numbers entirely.  However 600 3s and 600 4s are a real possibility.  We can easily go through each pair of numbers and work out if they are compatible.  We can turn this into a graph with counts available for each number.  Not certain whether the graph can contain cycles.  If the graph can’t contain cycles, it is bipartite and we can perform a max flow to determine the answer.  If it can contain cycles we have a problem…

So I checked out some answers – and yes it does seem max matching is now considered a question 2 level algorithm, not question 3 as I thought it used to be.  However, whether there are cycles or not is not relevant, as 2 odd numbers apparently cannot satisfy the requirements (since the sum of their squares will be 2 mod 4), and 2 even numbers is ruled out by the gcd(a, b) == 1 requirement.  Hence the pairs are bipartite based on even or odd.

Q3) Given a weighted tree with up to 200 nodes, determine the minimum weight sum of a tour which starts and ends at node 0, visits every edge at least once, and can teleport for cost L up to K times.

A3) If K is 0, the answer is 2 times the sum of the edge weights as every edge will be traversed twice.  If K is 1, we can subtract the longest path and add L, and choose which is best. That is to say if the depth of the deepest node from any other node is > L we will teleport between those nodes.  However once K is > 1, it becomes a lot trickier…

Again looking at solutions.  The problem is a dynamic programming problem.  Recurse over the minimum tour length within a subtree if there are i teleport endpoints in that subtree.  This can be determined by considering that if a subtree has an even number of teleport endpoints, it will be both exited and entered, otherwise it will only be exited or entered, not both.  So there are n nodes, and up to 2k teleport endpoints, so the DP has O(nk) states.  Determining each recursion requires considering how to distribute the i teleport endpoints between a nodes children.  Considering every combination is too much, so we need to switch up the DP a bit.  If instead of thinking about each node, we consider each edge, we realise we only need to consider each possibility for i down a given edge, not in combinations with other edges out of a given node.  So we can instead either recurse to the left most child and all its outgoing edges, or to the ‘set of edges to the right of the left most child’  Since the number of edges equals number of nodes -1 in a tree, the DP states is still O(nk).  Number of possibilities to try for each case is O(k) giving O(nk^2) running time to populate the DP table.  Once the table is populated all we have to do is check for root of the tree, each even number of end points, modified by the cost of teleporting, and determine the best result.

The real trick here is disassociating the end points, realising the problem can be solved without caring about specific locations teleporting to specific others.

This is the second time I’ve seen the ‘dfs edge walk on a tree’ DP problem.  I should probably write up a solution to practice it.