Q1) Given a dictionary and a mapping of numbers to sets of letters, and an input sequence consisting of numbers, ‘try alternate’ button pushes and ‘spaces’, determine the output. Assume dictionary is processed in alphabetical order.
A1) Easy enough, make a dictionary of number sequences to list of words that match, sort each list, then process input to produce output…
Q2) Given a graph with a line of nodes each connecting from one to the next, determine the minimum time to get from the first node to the last. Subject to some special conditions. Each edge has two time options for its travel. The first is always available, but the second can only be used if there are less than k contiguous sections where second option has already been used, or you used the second option for the last edge. The number of nodes n is up to 400thousand, and k is up to n or 40, whichever is lower. The first and second times for each travel option are generated using a pseudo-random number generator with specified parameters.
A2) While writing my question text above I may have made this question even easier due to my phraseology. Its a DP problem, 3 parameters, number of contiguous sections of second option so far, boolean if last was second option and how many nodes passed already. Very easy, only problem is that it requires 64meg ram in the default dp table. Luckily every entry only depends on the ones at one less nodes passed. Lucky because that means we can get rid of the memory problem, and also because if it depended on all of them the processing time would have been excessive.
Q3) Given a k-partite graph where each ‘layer’ only connects to its neighbours (arranging the k layers in a circle), determine the maximum independent set. Limits: Maximum vertices is 100, k between 10 and 50.
A3) When I first saw this problem I was shocked, a question 3 which maybe I can actually do. (The original question isn’t phrased as given, but still it was obvious this was the real question.) I unfortunately pretty quickly came to the realisation that the graph itself didn’t have any limitations which guaranteed it was bipartite. If k was even, I was good to go, but when k is odd, I had a problem. I thought about it for quite a while, and along the way I had the idea that I could try all the possibilities for one of the layers, and do the rest pretending it was a bipartite graph. Unfortunately I threw this thought away because I didn’t remember that k was at least 10, and so I decided that worst case would be 33 vertices as the smallest layer and 2^33 scenarios is too many to consider. With k at least 10 (or we might as well say 11 since 10 is trivial and a maximum vertices of 100, the worst case scenario is when the 100 vertices are distributed in layers of 10 or 9. Select one of the rows with only 9 in it, and try all 2^9 scenarios. For a given layer if we are trialling a vertex as being in the independent set, we can remove it, and any immediate neighbour vertexes. If not we just remove it. This removes the entire layer, leaving us with a bipartite graph which we can solve via the dual maximum matching problem using simple maxflow on a graph with capacities which are all 1. Add in the number of ‘independent’ vertexes in the current trial and choose maximum over all trials and done. Probably one of the easier question 3’s I’ve seen recently.