So I didn’t go in this single round match, but as part of my lead up to my being knocked out in round 4 I am going to write up 1 or maybe 2 past SRM’s a day as a bit of practice.
Q1) Given fixed and variable cost for each element where variable cost is proportional to the number of elements selected, what is the maximum number of elements which can be selected with a limit to maximum total cost. Up to 50 elements to select from.
A1) I was a bit disappointed at the time it took me to work out the solution to this, it was at least a minute… With only up to 50 elements to select from there are only a maximum of 50 answers, so you can check to see whether each answer is possible. Can even binary search to find the switch point between possible and not-possible if you were wanted extra efficiency… which is completely unnecessary. To check whether an answer is possible, calculate the total cost for each element assuming that there are n elements selected, and sum the smallest n costs to check if that is less than the maximum cost.
Q2) Given a directed graph connecting n nodes, what is the probability you can visit all nodes connected from node 0, starting at node 0, if when you arrive at any given node a random subset of size k of the available exiting edges is available for selection and you only visit nodes which are connected to from node 0 and never visit a node twice. Assume you know the entire graph and when presented with multiple options you select the one which will maximise your chance of success. n is up to 36, k is up to n, and a textual space separated list of the outgoing destinations for each node is up to 36 characters long.
A2) I had to look up the answer to this because I was stumped. However it turned out that the solution was one that I had considered and thrown away, because I mistakenly read the condition for the list of destinations from each node as being up to 36 entries, not up to 36 characters. This was the killer point, because 36 characters can only hold at most 15 distinct numbers space separated when 1 is the minimum number. With only at most 16 destinations 2^15 * 16 is an easily manageable state space, and another factor of 15 on top of that is an easily manageable running time. What I am describing is a memotized recursion calculating the probability of success given having visited some of the required nodes, and currently being on a specific node. Using the probability returned from recursion for each possible destination choice, you choose the highest probability. However this has to be modulated by the chance of being able to select that choice, add in the second highest probability modulated by the chance of not being able to select the first choice, the third by chance of not the first 2, etc, until all choices are accounted for or probability of not being able to choose from the top n is 0. Chances can be calculated using basic combinatorics… and assuming some caching up front, should be O(1).
Q3) Given a bi-directed graph (each directed edge always has its opposite edge present) with at most 1 cycle (when considered as an undirected graph) where each edge has a non-zero capacity, determine the minimum total capacity increase to ensure that a capacity n flow exists to node 0, regardless of the arrangement of sources (for total of n flow) feeding in to nodes other than 0. Maximum number of vertexes is 50, n is up to 100000. Maximum number of edges is also 100 (50 pairs).
A3) I actually think I stood a better chance with this question than question 2. I am pretty certain that the arrangement of sources can be ignored, we just have to ensure the graph can handle a flow of n from any single node to node 0. At that point I would think I would implement a maximum flow algorithm, then find ‘least number of constrictor’ paths and augment them until the number of constrictors increases, then re find. Of course you can bail out as soon as you reach your target. Least number of constrictor paths is like a shortest path search where edges with spare capacity have weight 0 and those that don’t have weight 1. The low number of edges makes this fast. Also since there is only at most 1 cycle there is a maximum of 2 paths between any 2 nodes, so implementing a proper maximum flow algorithm is overkill. The 2 paths may have common sections, but other than that limitation, the maximum flow is the sum of the maximum flow for the 2 arcs of the cycle. Even the least constrictor thing can probably be optimised due to the limit of a single cycle. You can even reused the modified graph as you move on to each other potential starting node, many of them will then pass straight after the maximum flow test. I think running time is worst case of about O(V * E^2) in an ideal implementation.