GCJ16 R1C

So, I’ve been a bit busy, so I didn’t get around to writing this up earlier.

Quite a tricky third problem with two problems that were reasonably easy left the cut-off being quite a fast time on the first two, or at least solving the small of the third.

I was amused to read the name of the person who came 1005th. ‘i.will.get.a.t-shirt’ missed out on getting to round 2 by 15 seconds…

Q1) Determine how to reduce a set of counts so that no specific member has a majority at any point, up to 2 can be removed at any point.

A1) This problem has two parts, the concept that avoiding a majority comes by reducing the largest count, and the realization that if there are only 2 non-zero counts they must be equal, and hence you have to remove one from each or a majority is formed.  From there its straight forward.

Q2) Given a set of nodes, create a directed acyclic graph which has exactly M paths between 2 specific nodes.

A2) For me this problem was pretty easy, but I could see it would be easy to get stuck thinking about it when you should be investigating to discover the trick.

My initial thought was recalling that its possible to number the nodes in a directed acyclic graph such that every node strictly points to nodes with a larger value.  The scenario with maximum number of paths would therefore be the one which maximizes the number of edges while satisfying that all edges are forwards.  So node 1 connects to 2 through N, node 2 connects to 3 through N, etc.

The number of paths in such a graph can be calculated easily enough – set 1 to node 1, then for each node in ascending order, sum all the values associated with nodes that connects to it, which is all of them seen so far.  This gives the sequence 1, 1, 2, 4, 8, 16, …

At this point the trick is to realize that the final node is connected to all the previous nodes in this fully connected graph, hence why its value is 2^(N-2), if we were to break one of those links, its value would be reduced by the corresponding value of the node it was linked too.  Obviously if M = 2^(N-2) we need all of them , but otherwise we’ve got all the smaller powers of two and we just need to connect them based on the bit pattern of M.  Or, just start from the largest and if its smaller than M, connect it, and reduce M, otherwise don’t connect it.

The final result is a triangle matrix, excluding the connects to the last node, which is either all of them, or a 1 shifted copy of the bit pattern of M.

Q3) Determine how to repeatedly choose from 3 separate piles of distinct items such that you never choose the same the same set of three more than once, and that you never choose the same subset of two more than K times.

A3) Its very tempting to just greedily choose the next possible combination while it doesn’t violate the conditions – but it can easily get stuck.  This explains the large number of failing attempts on the small input, or so I think anyway.

To try and understand this problem I implemented the brute-force for the small input.  Despite what it suggests in the contest analysis, it is possible to (with some care) write a brute-force solver which runs in time.  You do have to be sure not to allocate any memory in the loop…

I didn’t really find my understanding of the problem significantly improved by being able to compare the basic greedy to the correct brute-force, but it did manage to reinforce my thought that greedy was the right technique, I just needed to tweak it to avoid getting stuck.  So, I tried selecting from the third pile in reverse, alternating reverse every second time, and finally (I thought somewhat at random) by using a rotating offset driven by the selection of the first two piles.

This final option worked, much to my surprise – although now I’ve read the contest analysis it makes much more sense – the rotation clearly ensures it won’t get stuck.

 

Leave a Reply

Your email address will not be published. Required fields are marked *