The Missing Docs .Net

So round 1 looks like it is going to be a bit silly this year, 750 to advance per round, 3 rounds, 250 byes, but only 1371 people registered for R1A.  Unless a bunch of people forgot about R1A, everyone with a positive score in R1B will advance, let alone R1C…

I had a poorly written solution to Q1 and a decent solution to Q2, but ran out of time to really think through Q3.  Both my submitted solutions passed, regardless of how wrong my solution to Q1 was in theory…

In the end the positive score criterion came in to play, only 700 people advanced, the rest got 0 points or lower.  I was in 221st, not an amazing effort considering the 250 byes, but not bad.  My rating even went up a tiny bit, 1805.

Q1) Given an inclusive range, determine the greatest number of distinct common digits between any pair of numbers.

A1) I wrote a brute force solution, which I limited to running if the range was 200 in length or less, then for the rest I checked each number against single pair digit switches, if the resulting number was in the range that was a pair to consider, if not I presumed that it could be paired with one of its neighbours, to give distinct count of digits in itself – 1.  There are numerous flaws in this approach, but I couldn’t work out how to actually exploit any of them, as they only overestimated in scenarios where another valid option was better anyway, and seemingly never underestimated.

The better approach (far better) is to create a 10 bit mask out of each input, for the distinct digits present.  Then tabulate the masks.  Result is then the best bit count out of any mask with a count  > 1, or of the ‘&’ of any two bit masks both with counts > 0.

Q2) Given a directed graph  with exactly one edge leaving each node (which can return to self) determine the number of subsets of the graph which can follow there edges for up to K times without the new subset being any smaller.

A2) Two tricks here.  1) K can be huge, but the graph only has at most 50 nodes.  So it is fairly obvious that K > 2500 can just be considered as K = 2500 as any pair of nodes which might eventually map together will have a cycle length each of at most 50, and hence will either never meet, or meet in under 2500 steps.  Indeed this seems like a very conservative analysis, I think they either never meet or since they end up in the same cycle its at most 50 ‘pre-cycle’ links before they meet.  2) We just need to consider whether any pair of nodes eventually maps to the same place.  Once these pairs are found, they transitively form in to groups in which every pair collapses.

Together this means there are at most 2500 scenarios needing at most 2500 (or 50) steps of simulation, which will run quickly.

Once the groups are identified by simulation the the result is the product of the values of size of each group + 1.  This is because for each group either nothing is selected, or at most one element is selected.  Any node which doesn’t find a pair with any other node is in a group by itself, causing a multiple of 2, which leads to the worst case value of 2^50 as expected in the case where every node is independent.

Q3) Given a weighted bipartite graph, determine the minimum edge removal cost to ensure there is no perfect matching.

A3) So I’m still trying to understand the solutions I’ve read here, but basically it considers every non-empty subset of the one side of the graph, determines the cost to disconnect each node in the other side of the graph from that subset, and considers a possible minimum as disconnecting the cheapest x nodes, where x is the number of nodes in one side of the graph – the size of the subset + 1.  For the case of subset is everything, this corresponds to disconnecting one node entirely.  In the case the subset is a single node, it corresponds to disconnecting everything from that node.  In between it covers the other cases like if 2 nodes are disconnected from everything except 1, they can’t be perfectly matched due to pigeon hole principle.

Only thing I’m not clear on is the proof that every non-perfect matching scenario can be reduced to x nodes disconnected from n-x+1 nodes.  The reverse is obvious every such scenario is non-perfect matching, but the equivalence is not so much…

Last chance to get through to round 3 or get a t-shirt, but I was never really in the running for either this year it seems.  Final ranking of 420th with a fairly slow submission time for the first question, probably could have gotten into the top 300, but the trick to solving the second problem seems clearly out of my reach for 3am with 45 minutes.

Q1) Determine the range which if reversed produces the lexicographically smallest string.  If multiple equal results prefer smallest first index, then smallest second index to break ties.

A1) This question was rated for 300pt, so I thought there was going to be some real difficulty to it, so I ended up going slow and careful.

Pure brute force is O(N^3) which for length 2500 is too slow.  But it is pretty easy to get this down to O(N^2).   If there are 2 candidates for lexicographically smallest, unless the first change they make is at the same place, you can trivially choose the one with the earliest change.  This means that once you have identified a starting index which can be improved by swapping with something later, the question is reduced to which later index is best.  Finding the first index which can be improved can be done in O(N) time (because there are only 26 distinct possible values, otherwise O(N log N) would apply).  But given dealing with all the possible second indexes is going to generate O(N) scenarios with a cost each of O(N) to check if they are smaller than the current best, you might as well just brute force finding the first index, which is O(N^2).

There are a couple of corner cases that can come up.  If you actually construct the strings with segments reversed it is best to avoid gathering them all up and doing a sort, it might be too slow as O(N^2 log N) is pretty high.  However doing in-place comparison (like I did) requires care that you remember that the earlier of the possible last indexes will run out of reversed area first, and you need to compare the later reversed part of the larger range to some of the non-reversed part after the smaller range, and not accidentally compare with non-reversed part before the smaller range.

One corner case which I thought existed but seems does not is that if you have a range which when reversed gives the best lexicographical string its ranking could potentially be improved if the character before and after the range is identical, since reversing the larger range still gives the same result, but the first index is earlier.  I wrote code to handle this case, but for the final result, and as a tie-breaker when considering two possible last indexes.  However it cannot happen.  Presume that it did exist, for example that the best lexicographical ordering is …ej……ge… which the j to g range has been selected for reversal.  Immediately this can be shown as invalid as the j to e range produces a better result.  So lets try …ej…….ee… where the j to first e range has been selected for reversal.  Here we know that there is no letter earlier than e anywhere after that first e, because otherwise switching that letter and the first e would provide a better reversal.  This means that j to first e in the ending pair is a worse option that j to the second e in the ending pair, because the reversed sequence will have a longer sequence of e’s before something higher is encountered.

Q2) Given a undirected graph which is specified as clumps of vertexes which are fully connected (where the vertexes in each clump are not distinct from other clumps, indeed the graph is connected). Determine the sum of the all pairs shortest path distances.

A3) So all pairs shortest path distance sum can be calculated in O(VE) for an undirected connected graph with all edges of equal length using a simple BFS.  The problem is that with 2500 vertices, and potentially being fully connected, this is O(N^3) which is too slow.

I thought the trick here was to treat vertices which are only in one clump specially, but on a closer look the problem statement doesn’t actually restrict how many such vertexes there are, even to the potentially silly case where every vertex is listed in 2 identical clumps that are completely overlapped.  Even if subsets were disallowed, this would still have the all but 2 vertexes in common case which is still going to be O(N^3).

The actual solution appears to be to introduce more vertexes.  One which represents each clump.  Then rather than connecting nodes in a clump together, they are connected to their clump vertex.  This doesn’t change the connectedness of the graph, it only doubles the distance between everything.  Calculating the all pairs distance (excluding the clump nodes) is still a simple BFS, just with a conditional for when to add values based on whether you are at a fake vertex or not.  Then you just take the final result and divide it by 2.  This new graph has a number of edges equal to the sum of the number of clumps each vertex is in, which by the definition of the problem is limited to double the number of vertexes.  The number of clumps is also limited to be the number of vertexes, so O(VE) becomes O(N^2) with a reasonable constant.

Q3) Given a set of ranges of indices and the maximum value in each range, determine whether there exists a permutation of the numbers 1 to n which can satisfy all the defined constraints.

A3) With up to 50 constraints, considering how every subset interacts is going to be too slow. However it might be possible to just introduce each new constraint one at a time and check against implied constraints calculated from previous checked pairings.  Information can only be inferred over sections which start or stop at a constraint boundary, so there can be at most 2500 implied constraints.  Therefore the running time should be O(N^4) if constraint interactions need only be considered pairwise in O(1) time.  Point 4 below looks like the most problematic to this, but might be able to be addressed by sorting regions by their implied maximum or similar.

There are several things to consider at a minimum.

1. Two disjoint ranges cannot have the same maximum.
2. A subset cannot have a higher maximum.
3. A range cannot have a maximum value smaller than its width.
4. Multiple disjoint ranges cannot all have maximum values smaller than the sum of their widths.
5. Two ranges which overlap define a union range with the larger maximum.

Two ranges which overlap with equal maximum define an intersection region with the same maximum and the maximums of the non-overlaps are less than specified.

 

Two ranges which overlap with different maximums imply neither maximum is in the overlap.

But getting from there to a working solution is not obvious to me.

A couple of little mistakes on my behalf cost me several hundred placings in the final score board, but I don’t think I was ever going to get a t-shirt this round.  A really fast first problem was probably enough for a t-shirt this time round, with solving the second problem to make it safe.  Solving those 2 in a decently fast time was needed to advance, solving all 3 was only done by a few.

Q1) Given N steps of M conditions (true, false or don’t care), determine the minimum number of times true values have to be changed to false (in a batch) or vice versa to get past all N steps in order, starting from M values which are all false.

A1) This problem boils down to realizing that it can be solved using a lazy greedy.  If it wasn’t for the ‘don’t care’ states, the problem is trivial as every change is defined and you just don’t do any unneeded changes.  The lazy greedy approach is to pretend ‘don’t care’ means the condition of the next step that is something other than ‘don’t care’, but only if you were going to make a change from positive to negative or vice versa for other reasons.  This works because either it gets changed before you get there for free, or you avoid incurring the cost of doing it early when there was going to be a batch at the final step anyway.

So the simple way to do this is with an O(M*N^2) algorithm where at each step you determine what ‘has’ to be done to satisfy true and false conditionals, and also perform any changes of state for ‘don’t care’ conditionals where the future desired value can be put into a batch which is already going to be performed, by scanning ahead each time you see a question mark.  I wrote an O(NM) algorithm by pre-calculating the results of the scan ahead by working backwards through the steps.  This was my first mistake, as I missed a line of code in my pre-calculation loop, and so it contained garbage data, resulting in my wasting a bunch of time debugging.  The second mistake was I wrote a conditional of the form if (A and !B) B = true – which could have just been if (A) B = true.  Then I copy pasted that conditional and changed to B = false, but didn’t change !B to B.  I had to take a time penalty to resubmit because I only thought to double check my copy pastes after I pushed submit…

Q2) Calculate the sum of values which satisfy a criterion within a range.  The criterion is that they are not one more than a prime number, and that there exists exactly one pair of positive integers which sum to that number such that the product of that pair can be decomposed into 1 or more pairs that multiply to give that product, but the sums of which only have one value which is not 1 more than a prime. (Caveat that the value 2 does not satisfy the criterion either.)

A2) Believe it or not, the above description is actually a simplified version of the original description…  With the range being up to 5 million, O(N^3/2) is going to be too slow, so the algorithm needs to be O(N log N) or better basically.

A solution which passed in my room seemingly presumes that if the pairing of 1 and n-1 works, it is a distinct pairing, and no other scenario works.  It then creates a vector of the prime decomposition of n – 1 and uses a bit mask to create every pair that multiply to give n – 1 ( excluding 1 and n – 1), and if any of those pairs sum to give not 1 more than a prime, it fails.  Given the initial assumption, this matches the conditional because n – 1 is not prime by initial check, so 1 + n – 1 – 1 is not prime, so we already have 1 pair which is not 1 more than a prime, finding any more would be bad.  The weird bit however is that this algorithm is not obviously fast enough.  Non-primes are dense so the initial check doesn’t prune much and the bit mask loop means O(2^(log N)) operations worst case per number.  So you might be tempted to say this is O(N^2).  However the bit mask loop’s worst case is for powers of 2, which are not-dense.  The average number of prime factors is in fact O(log log N) which means that this algorithm does indeed kind of run in O(N log N) time after all (generating the prime factors is also a O(log N) component if you precompute a composites table with smallest prime factor – which can itself be done in O(N log log N) using the sieve).

What needs more thought is why the assumption that the distinct pair is always 1 and n – 1.  Why does 2 and n-2 always fail for instance.  We know that n-1 is not prime.   2 and n – 2 added together is n so it is 1 more than a not a prime.  All we need now is one more example.  1 and 2n-4 is 2n-3 which is one more than 2n-4 which is obviously not a prime as it has 2 as a factor.  Presto it fails.  More generally k and n-k.  Precondition of n-1 is not a prime, so the direct sum is 1 more than a prime.  1 and kn-k^2 is one more than kn-k^2 – which is k(n-k) which is not a prime if k >= 2 and again it fails.  The only case that could work is k=1.

Q3) Given a large range, determine how many numbers can be recursively mapped using the following function.  If x is not an integer, no mapping.  If x mod W is 0, no mapping, otherwise f(x) is x/(x mod W).

A3) The range is indeed huge, no way enumerating will work.  First off every positive number less than W is a recursive map to 1.  Every value x where x mod W is 1 is a recursive map to itself.  The number of these scenarios in the range can easily be calculated.

Beyond that is much more complicated.  x where x mod W is 2, where x is even and x/2 is mappable, is mappable, obviously.  2kW+2 works fully recursively because it maps down to kW+1.  But if W is even, W+2 works.  3W+2 is W+1+W/2, which looks like it won’t work…  So it looks like the factors of W need to be special cased in some fancy fashion which is non-obvious.  Maybe I’ll look at this more deeply another day – but not today.

As usual round 2 is pretty competitive, to advance required all 4 small inputs and the 2 easiest large problems, and even then time was a minor factor…  T-shirt was the 2 easiest large problems and one of the remaining small inputs, the harder one to not have to worry about time.

Q1) Given a set of containers of equal size and a list of item sizes and a maximum of 2 items per container, determine the minimum number of containers needed to pack all the items.

A1) This can be solved by a greedy approach.  Take the largest item, if there is another item which fits in the container with it, take it.  If you want you can choose to take the largest of such other possible items for the ‘most greedy’ approach.  But I am pretty sure you can just take the smallest and it makes no difference.  This later scenario makes the problem trivial, as you just walk inwards from the ends of a sorted version of the list of items, advancing when you can take them to count the items.  This works well for the large input since it is an O(N) approach (after the O(N log N) of sorting).  But even with 10^4 items the simple O(N^2) implementation of the ‘most greedy’ approach will run in time with a decent compiler.  Or it could be implemented with a sorted dictionary (specifically one with a ‘find value or prior’ method) for O(N log N), but in this case you have to be careful how you handle multiple items of the same size, since they will have the same key.

Q2) Determine the minimum number of neighbour swaps to make a sequence be sorted such that it has a single maximum, that is it is either all descending/ascending or ascending followed by descending.

A2) I had to go remind myself about minimum neighbour swaps to work out how to do this question.  Even the small input looked tough, brute forcing all possible swap locations and orderings was way way too slow.

So this question boils down to two parts.  Minimum neighbour swaps to make a specific permutation, and deciding which permutation takes the minimum neighbour swaps to satisfy the criteria.

Minimum neighbour swaps to make a permutation is pretty straight forward.  But it requires knowing things which aren’t exactly obvious.  For instance the bubble sort is optimal in the number of swaps, so for the small input you can just use the bubble sort to sort the items, relabelled by the desired index to move them to.  For large input you need to know that a merge sort can be used to count the number of swaps a bubble sort would have done, but with batches rather than 1 by 1, allowing it to run in O(N log N) even though the number of swaps is O(N^2).  Some Google searching found me the algorithm, which is not that complicated.  Every time an item in the merge is taken from the top half instead of the bottom half, you add the distance it would have had to move assuming the halves were joined in sequence rather than being merged into a destination array.

Deciding the permutation had me stumped for a while.  Obviously the largest value in the input is the pivot point, but which elements should be on its left, and which should be on the right?  In hindsight the small input brute force is obvious here, just try every combination of values other than the largest being assigned left, or right.  Once they are labelled, sort the lefts ascending, and the rights descending and that determines the desired permutation to calculate the minimum swaps for.  The large input on the other hand is I think far from obvious.  I think it can be done just by using a hill climb.  For each value see if the minimum swaps decreases by switching sides, repeat until you can’t make it any better.  I can’t prove this however…  This hill climb could be O(N^3 log N) (which is quite slow for N=1000) if switching sides made things better to switch back for others, but I think it is much closer to O(N^2 log N) in practice.

Looking at a solution on the other hand shows another option which is much simpler, and is intuitive, but not obvious.  The idea seems to be that you select the smallest value in the item and then swap it to the closest end.   Lock that one in, and repeat the process.  Can be made to run in O(N log N) although given the large input is still only at most 1000 items, the simpler O(N^2) option is fast enough.

Q3) Given a grid of squares determine the maximum flow from the bottom edge to the top edge, if each square has a capacity a flow limit of 1 and can flow through its edges, but some cells have 0 flow capacity.  All bottom edges are an input flow of 1, all top edges are accumulated for the maximum flow.

A3)  So if you have a maximum flow implementation at the ready, the small input here is probably not too crazy.  However with 100000 nodes in the graph and each node having 4 connections, and a potential maximum flow of 100 it will need to be the Ford Fulkerson algorithm with its O(E max(f)) running time as anything O(VE) or worse will run way way way too slow.

The large input however has a grid height of 10^8 which ensures the O(W^2 * H) Ford Fulkerson approach is implausible.  However there is a limit of 1000 blocked out areas, which means there is only at most 2000 different interesting positions in the height.  However even O(W^2 * count_interesting(H)) is pretty slow and determining how the flow graph looks even for that is tricky.  I am not clear on how horizontal elements can be safely coalesced to give edges with maximum flow greater than 1, because there is a limit to how fast a given flow can migrate left or right, and so you would have to ensure that everything that was coalesced can make it to the next area in time rather than just blindly coalescing everything which is horizontally connected.

To discuss the bit I think which is interesting (but probably not sufficient to solve) is how flows can migrate left or right across a distance.  If there are 4 adjacent flows entering an ‘open’ area, one of them can migrate to anywhere after one cell down as it can flow across all the empty spaces.  Then after the second cell down another can join it, then 3rd can move after 3 and so on.  These would probably be represented with cross links in the graph with a specific capacity dependent on the height difference between the current position and the next.  If there are 2 ‘streams’ coming down to an open area these links would be set up so that flow can’t go both directions.

Q4) Determine the worst case for the number elements in the tries created by splitting the input works in to k groups, then determine how many ways this worst case can be performed.

A4)  Small input is pretty easy here, only 4 groups and 8 items,  gives only 2^16 base scenarios to consider in a pure brute force.  From there eliminate the ones where any group has no elements, the build the tries and sum the counts and if worse reset counter to 1, if equal increment counter, otherwise ignore.

The first part of this question is actually quite easy, just count how many times each substring exists in each word, choose the smaller of that and the number of servers, sum all those values and that is the worst case.  Basically this just states that any given substring can always be distributed amongst the servers to potentially be counted a number of times equal to the number of servers.

The number of ways that it can be done is a much more difficult problem.  How many ways a given substring could be distributed amongst the servers such that it is spread out as much as possible is a fairly simple combinatorics question, but you can’t just multiply these together because they have correlations because the shorter substrings have to match the servers of their corresponding longer servers.

Trying to reverse engineer the logic from reading a solution is beyond me right now, so I think I will leave this question for another day…

So I barely managed 615th out of the 1439 people who registered out of the 2500 potential people.  My rating didn’t move down much as a result, but I was disappointed with my result all the same.  Getting the second problem out was good for a guaranteed t-shirt, and solving the 1000pt was a guaranteed advancement.  Advancement cut-off was 442 points.

Q1) Given 16 values arrange them into a 4×4 grid such that sum of all edge values + double the corners + the absolute difference between neighbour pairs is maximal.  Return the maximal sum.

A1) I am not a fan of this question.  I solved it quickly, but accidentally, with a poor solution which is not at all obviously correct.  I then spent far too long trying to convince myself as to whether I was missing something critical, getting a low score in the process.

So the trick to this question is to convince yourself that the values given do not matter, if you sort them and place them the same as you would place 1 through 16 optimally, you still get an optimal solution.  One such ordering is as follows:

16  3 15  8
 4 14  1 13
12  2 11  5
 7 10  6  9

The idea is that if you choose to have your largest 8 numbers in a checker board pattern the sum becomes 4 * sum of largest 8 – 4 * sum of the middle 2 (because they are surrounded) – 2 * sum of those on the edges (because their being on the edge offsets one of their 3 neighbours) – 0 * sum of those in the corners (because corner offsets both of the 2 neighbours).  So it smallest 2 numbers go in the middle, next 4 smallest on the edges, and the next 2 in the corners, and the rest are checker boarded is optimal for the checker board scenario.  A small inspection shows that the formula still holds if some of the smallest 8 are equal to some of the largest 8.  All that remains is to prove that there is no scenario where 2 elements of the largest 8 are neighbours produces a better result.  But I have no idea how to do that and the checker board pattern is somewhat ‘obviously’ good.

As a demonstration of why this problem was ‘broken’ – placing the numbers into the 4×4 square in sorted order (but not for all random orders) and them performing a greedy pairwise swap until no pairwise swaps improve the sum, would pass system tests, despite having practically no relation to the actual greedy arrangement.

Q2) Given a set of positions in a long narrow hallway, determine the minimum they have to move in order to get to a different set of positions, if they can only pass each other at either end of the hallway.

A2) This is where I am really disappointed with my self.  Even with all of the time wasting I did on the first problem I still had > 25minutes left after my submission.  However because I had become convinced that I was missing something with that first question, and no one else in the room had submitted the 500pt, and one person had skipped it in favour of the 1000pt, I decided it was a better investment in my time to try and come up with a killer test case to break my (and hopefully others) 250pt question.  Which was both a) futile since everyone else’s code passed system tests and b) unsuccessful, since my solution passed system tests…

So this problem really isn’t that difficult.  Sort by starting locations to get an ordered set of indexes, sort by ending locations to get another ordered set of indexes.  Now there are 2 basic scenarios.

First up, some sub-range of the starting indexes which all have the same destination indexes directly shifts to their destinations while everything to the left shifts via the left end, and everything right shifts via the right end.  This is only valid if every item to the left has a destination on the left, and every item on the right has a destination on the right.  This has O(N^2) scenarios each with an evaluation time of O(N) to give O(N^3).

The second is a bit more complicated and I might have gotten it wrong (if there wasn’t a practice question which would have picked it up).  In this case no elements move directly to their destination, everything moves either via the left or the right ends.  So for every possible partition point you can consider everything going left and right, and getting to their destinations via the corresponding end points.  However this doesn’t work if the set of destination indexes of the left and right sections aren’t also on the left and right.  The trick is that these scenarios can all work, just that some items have to visit both ends.

So having partitioned the starting indexes into left and right groups, you also have to partition the destination indexes into left and right groups, and if they change groups, you have to add the extra distance of having visited both ends.  This gives O(N^2) scenarios each with an evaluation time of O(N) to add an addition O(N^3).  Input constraints were at most 50 items, so the result is easily managed.

Q3) Given a tree with black disks on some (non-root) nodes and a red disk on the root node, determine which nodes the red disk can visit by sliding along edges, if disks cannot pass through each other, but are otherwise all free to move along edges.

A3) Only 6 people solved this successfully, and none of the solutions are trivial to read and understand.  General idea seems to be that you cache the number of black disks and the number of nodes for each sub-tree and then use that to determine whether the black disks can be shuffled out of the way to let the red disk to visit.  If a node has multiple children and can be visited by the red disk, and not all of those children are filled, the red disk can visit some of the children, and potentially the black disks in the other children can be shifted up and into available spaces else where on the tree, allowing the red disk to reach even more locations.  I think this logic gets applied repeatedly until no more red disk reach locations can be found.  Without the cache the solution would be too slow.

Top 1000 advanced which looks to be solving question 1 completely and question 2 small in < 1:50.  For safety add in the question 3 small input.  In fact you could drop question 1 large.  All 3 small inputs was sufficient to advance.

Q1) Given a fraction, determine if it can be created by repeated pairwise averaging of 2^40 values which are either 0 or 1.  If so, determine the best case depth of a value of 1 in that averaging. (Best case being closest to the final value.)

A1) Odd little question, but actually quite simple.  Difference between small and large input was that the large could involve 64 bit numbers, and you needed to implement a GCD to reduce the fraction to minimal components, but otherwise still quite simple.

The solution comes that because repeated pairwise averaging is identical to just averaging all the values at once, the fraction must be of the form n/2^40.  So if the base of the fraction is a power of 2, the fraction can be created.  This is where the GCD comes in for the large input, without reducing to the minimal form, the base could be a multiple of a power of 2, and also of some other number, which can be factored out of the numerator.

For calculating the depth, it is obvious that if you consider the n/2^40 form you have n 1’s at the top level.  To keep a 1 as long as possible you shift them all to one side.  Thus the depth will be 40 – the floor of log 2 of n.  Another way of looking at it is that if the fraction >= 1/2 a parent can be a 1, >= 1/4 a grand parent, and so on.  So the depth is equal to the number of times you can double the fraction before it is greater than or equal to 1.

Q2) Given sequences of characters, determine how many ways the sequences can be ordered such that the concatenation has every case of any given letter being in a single contiguous grouping.  Return result modulo 1 billion and 7.

A2) Small input there are 10! orderings to try, so it can just be brute forced.  Large input there are up to 100 sequences, so something smarter is needed.

The approach I would have gone with is categorizing the inputs.  If a sequence contains just the one character some number of times, we call that a ‘repeater’ (even if it is just a single character).  If a sequence starts with some number instances of a letter, we say it starts with that letter.  Similarly for ending.  Any characters between a start and end and the sequence also gets categorized as having those characters in the middle.

From there a bunch of impossible scenarios can be detected straight off the bat.  Only 1 sequence can start with any given letter, excluding repeaters.  Same for ending.  No 2 sequences can have the same characters in the middle, unless they are both repeaters.  A single sequence can’t have the same character in the middle multiple times, unless they are contiguous.  (I note now that the problem can be somewhat simplified by removing all contiguous duplications from the input sequences.  They don’t change the problem and just complicate detecting invalid scenarios.)

Next the inputs need to be grouped.  A starter and an ender of the same letter (and the repeaters) must be in the same group.  When gathering a group, you can follow the starter to an ender, and then to a starter, and to an ender and so on, and vice-versa, to get a full group.  However if you detect a cycle, this is also impossible.

The final part is to calculate the number of orderings.  If there are n groups, those groups can be selected to form n! orderings.  Each group has only one ordering, unless it has repeaters.  Each letter in a group which has k repeaters, contributes k! orderings.  All these factorials must be multiplied together, continually using the modulo 1 billion and 7 as required and use 64 bit integers to avoid overflow.

Q3) Given a NxM grid of points connected by horizontal and vertical lines, determine the minimum number of covered points required to enclose at least K locations.  Enclosing is defined by either being covered or being unable to connect to the edge of the grid without going through a covered point.

A3) The small input has N*M less than or equal to 20.  This actually limits a lot of the possible scenarios, but it does allow a brute force of whether each point is covered or not.

The large input has N*M <= 1000, which gives a lot greater possibilities for tricky corner cases, but does easily allow for a O(N*M*(N + M)) time algorithm.  (Examples of this can be found in the solutions to download.)

So this problem has a few things to it, which makes it a bit tricky.  First of all the problem is actually slightly simpler with an infinite grid.  In this scenario we can ask ‘what is the largest area that can be enclosed with n stones and not have to worry about whether the ideal shape runs into the edge of the grid or not.  So if n = 4k, the ideal shape is a diamond pattern.  Proving this may be non-trivial in practice, but it makes a lot of sense.  In such a shape any attempt to increase the area by moving a stone, forces all the other stones to move, just moving the shape.  If n = 4k+2 the ideal shape has 2 options, either a diamond with 2 longer opposite sides, or take the 4k ideal and duplicate 2 of its vertical or horizontal extremes, kind of making a blunted diamond.

 ## 
#  #
 ##

When I was first thinking about this problem I made the mistake of not considering 4k+1 and 4k+3 correctly.  Looking at the case of k=1 led me to conclude that these could only cover one extra position in terms of area compared to the one stone less case.  Instead the ideal scenarios look more like this:

  ##
 #  #
#    #
#     #
 #   #
  # #
   #

The general pattern that can be derived is that there are 4 diagonal lines, which either meet at a point or a blunted point.  4k is a perfect diamond shape, 4k+1 one diagonal line moves outwards, causing 2 blunts.  4k+2 moves out two diagonal lines, if they are adjacent then there are 2 blunts on opposite corners, if they are opposite it is all points, but the diamond is stretched.  4k+3 moves out 3 diagonal lines, resulting in 2 adjacent blunted points on a stretched diamond.

 ##
#  #
# #
 #

So, how does this interact with the the borders?  Well it turns out that so long as you choose adjacent case for 4k+2 (or maybe even if not?), simply truncating positions to fit inside the box is as good as you can do.  I don’t have a good proof, but once the shape is too big, the edges have to be connected, so you get runs across the edge, and minimizing stones becomes cutting diagonals across the corners, which ends up being the same as squishing the ideal shape into the available space.

So the O(N*M*(N+M)) solution is to try every area less than or equal to N*M, and cut off corners incrementally until they no longer touch the edge.  Since every area is tried, the ideal scenarios that don’t touch the edges of the full NxM grid are all tried because they are all touch the sides of some size rectangle.  Taking turns cutting the corners off one by one goes through the 4k, 4k-1, 4k-2, 4k-3, 4(k-1) sequence, pushing the diagonal lines inwards incrementally.  The best solution of all tried is returned.

A more interesting (but same running time solution) is to consider ‘can it be solved in n stones’ and then depending on the modulus the formula for the 4 boundary diagonal lines can be formulated, knowing the border will be a total of n stones, the area can then be calculated by walking over every point and checking whether it is inside the 4 diagonal lines.  The solution I saw using this approach tested cutting off corners in both orientations of the NxM grid, but I suspect that with a little thought it could be reduced to only testing one of those 2 orientations.

This approach leads to an O(N+M) solution.  Since the worst case answer is 2N+2M-4, you can walk upwards towards that value checking each n until one works.  If you can calculate the covered area in O(1) time, this is O(N+M).  This is much more complicated piece of code, but by calculating the intersection points of the 4 boundary lines with each other you can calculate a reduced area (if the shape isn’t already going to touch the edges) and then the number of empty points in the corners of this possibly reduced area can be calculated by k(k+1)/2 where k is the index (counting based on 0 from the corner) of the first filled in point along the edge, which is found by calculating the intersection of the diagonal line with the edge.  The sum of these 4 corner cut-offs is subtracted from the the total area to give the number of enclosed points.  There are 4 diagonal line pair intersections and then 4 diagonal line with a edge intersection calculations involved, all of which are simple formula solves (although the blunted corners result in the ‘intersection’ of the 2 lines being somewhere between points where you can place a stone, this is easily special cased) which can be done in O(1) time, for a total of O(1) time to calculate the covered area.

Special cases.  If the desired area is 4 or less, no need to do any work, the number of stones required equals the area.  This is also the case if the minimum of N and M is <= 2, since there is no way to surround a square in such a narrow space.  Also not obvious in the discussion above is when the desired area is >= N*M-3.  In this case the amount cut off a corner is 0 in some cases, which still works, it is just a bit unexpected considering all the use of diagonals in my description.

Another week, another round of a coding competition… or so it seems this time of year.

Top 1000 advancing to round 2.  The cut-off was fully solving question 2 and the small input of question 1 in 2:20.  All small inputs in a fast time came 1035th, which was interestingly close to advancing.  The score to get by without having to worry about time was achieved by all small inputs and the large of the first question.

Q1) Given a game where characters can be duplicated and consecutive duplicate characters can be collapsed back to a single character, determine if a set of strings can be made equal, and if so, the minimum number of moves to achieve this goal.

A1) Determining whether the goal can be achieved is easy, just replace all sequences of consecutive repeats with a single character, and determine if all the input strings are equal.  This produces a ‘canonical’ form that all must match.  For the minimum number of moves it isn’t really that much harder.  For the small input there are only 2 strings, so choose one of the strings and count how many moves it takes to make the other equal to it.  There is no advantage to trying to meet in the middle, so on a per canonical string character basis just take the absolute difference of the counts in each of the strings and sum them all for the result.

For the large input there are up to 100 strings, but because each string is only at most 100 characters, no letter can be repeated more than 100 times.  Therefore the ideal to converge upon will be no more than 100 repeats and no less than 1.  Since each character of the canonical form can be considered independently, all possibilities can be easily tested within the time limit.  Just try each value of 1 to 100 inclusive and calculate the sum of absolute differences, the smallest sum is the minimum number of moves for that canonical character.  Then just sum all of those minimums for the final result.

The most challenging part of this question is probably that the large input is considerably more ‘different’ to the small input, so a bug in the code could easily get past the small input only to fail on the large input, even though it would easily run in time.

For interest, an extension of this question where the maximum length of a given string is unbounded by the maximum length of the canonical form is short, the problem is still easily solved so long as the counts are provided rather than having to parse the unbounded length string.  The sum of a set of absolute difference functions all with equal slope has a minimum at the middle of the sorted list of 0 points of the individual functions.  For an even number of functions, either of the middle 2 will work because the the sum is flat in between.  Thus with a value selected the total of absolute differences can be calculated for a total run time proportional only to the number of strings and the number of characters in the canonical form.

Q2) How many pairs of 2 numbers selected from specific ranges when bitwise ‘and’d together have a result in a 3rd specific range.  All ranges start from 0.

A2) Easiest small input ever?  With range sizes of only at most 1000 each, nested loop over the input ranges and calculate the and and compare to the maximum value of the 3rd range.  If less increase counter.  Once loops are done, return counter.  6 trivial lines?

Large input however is much more challenging.  With ranges of up to 1 billion, such brute force is out of the question.  Given the bitwise and function and the large ranges, running time seems like it will need to be related to the logarithm of the input range maximums.

Determining whether 2 numbers ‘and’ to give a 3rd is trivial, which leads to the thought, is there some way to convert the ranges into batches which can be easily processed in parallel.  Perhaps using a ternary notation of 0, 1 and ‘don’t care’?

All numbers less than n can be grouped in a ternary notation by having a prefix which is equal to the start of n, followed by a 0 where there is a 1 in n, followed by ‘don’t care’ for all subsequent bits.  The number of such patterns needed is equal to the number of set bits in n, which is worst case proportional to the logarithm of n.

So the problem now boils down to, generate these ternary representations for the 2 input ranges and the output range, then for every way of selecting from those 3 lists, determine how many results it allows.  Sum those all up, and return.

So the core part of that is ‘determine how many results it allows’.  So inside the triple nested loop to select the 3 ternary representations being tested another loop over each bit is needed.  Each bit is independent in the bitwise and, so the number of ways of doing each bit can be considered a multiplier.  Multiplying them all together will give the number of solutions that are derived from this particular selection.

Handling each bit can be done with a large if statement selecting on the 3 different values which can be in each of the 2 inputs and the output.  For example ‘don’t care’, ‘don’t care’, ‘don’t care’ has 4 possible scenarios and ‘don’t care’, ‘don’t care’, 0 has 3 possible scenarios.  Such an if statement is quite large and convoluted, so some more nested loops might be simpler.  Loop over each possibility for the 2 inputs, skipping if it doesn’t match the actual input values.  Then calculate the and of the 2 input bits and compare it to the expected output value incrementing the counter if it matches.  The simple match function for ‘bit vs ternary value’ is handled much more easily than the huge if statement.

One catch is that the 3 ranges originally specified 2 are exclusive and one is inclusive of the maximum, so applying the above approach the inclusive bound needs to be incremented to make it an exclusive bound first.  Alternatively all numbers less or equal to n can be considered by using the same set of patterns above and adding the exact pattern of n as well.  This is equivalent to setting the bit one past the end of the number to 0 and so can be treated as one extra loop, with appropriate special case handling.

Q3) Given a set of locations with distinct ‘values’ and a list of connections between locations (all locations are connected), determine a order of visiting which doesn’t arrive at any node more than once, but can backtrack as much as you like, which visits every node such that the sequence of first visits is ‘smallest’.  Smallest is defined by comparing the first elements of two sequences, then the second elements, and so on until one is smaller than the other.

A3)  The small input only had 8 nodes, so brute force was plausible.  Just had to make sure you don’t infinite loop.

First thing to realise is that the values of the locations do not matter, so first step is to renumber the graph so that the smallest value is node 0, the second smallest is node 1, and so on.  Then the walk of the graph desired is one which prefers smaller node indexes.

The solution seems to be a greedy approach.  First thing to realise is that node 0 (in the renumbered scenario) is always the correct place to start – since you can start from anywhere, and it is always possible to walk to every node of a connected graph, starting from any given node even with the additional restrictions specified by the problem.

From that first location you will always walk to the smallest index connected to node 0.  But after that it becomes slightly more tricky.  More generally the problem becomes deciding what to do when you have visited a set of nodes V and have a current path from node 0 to current node N.  For each of the nodes on the path, you can go to any of the nodes not in V that are connected to the node in the path.  This leads to a set of scenarios which need to be prioritized for the greedy approach.  The obvious priority is the index of the destination.  It is always preferable to go to a smaller index if possible.  However we need to break ties as the graph can be fully connected, in which case it is possible to reach every node from every node.  Here the idea is that deeper in the path is better.  Every time you backtrack you lose the possibility of going from that node in future, so it is kind of an opportunity cost.

So that seems pretty simple – but just choosing the best value from the set of scenarios, doesn’t always work.  The problem is that it may cause you to back track to take a link to a low index node, but there might be nodes that can only be reached through the node you backtracked from, and there is no way to get back to that node any more.  Therefore before taking any option in the priority order of options, you must perform a reachability check. A recursive walk from each node in the potential future path, out in to the world not visiting anywhere already visited, do you visit every node not already visited?  If the reachability check fails, that option must be discarded and the next highest priority considered.

The running time of this algorithm is a bit complicated, but an easy upper bound can be found.  There are O(N) steps.  Worst of these steps has O(N) nodes on the current path.  This results in O(N^2) possible scenarios to consider.  Each of which could require a reachability analysis which takes O(E) or O(N^2).  Thus an easy upper bound is O(N^5) which with 50 nodes is fine.  In practice the cases with high number of scenarios at a given step also tend to pass reachability easily, so the code runs within time with ease.

So, again I didn’t need to compete, which was good because my weekend was already very very busy…  2 easy questions this week, with 750th place scoring almost 628 points.  This time about 230 people got all 3 problems out in time.

Q1) Remove duplicate letters from a string, leaving the first instance.

A1) Even with the length limit of up to 1000 letters only the really silly O(N^3) solution  would run too slow.  Simple boolean array for seen and add characters to a list if they haven’t been seen yet then convert character list to string for return.  O(N) – very simple.

Q2) Count the number of multiples of 3 (but not 15) and 5 (but not 15) and 15 in a large range.

A2) There is always 1 multiple of 15 and 4 of 3 but not 15 and 2 of 5 but not 15 in the range n=15k to n=15k+14.  Thus take the modulus of the start and end in order to move them up and down to a 15k and 15m-1 value respectively, then hand code the start/end sections and add the results to m-k, 4(m-k) and 2(m-k).

Q3) Given a random walk of length n, what is the expectation value for the number of distinct locations it steps on, including the starting location.

A3) So with n up to 500, there are 2^500 different random walks possible, so brute force isn’t going to work.  The best of my initial guesses was to do this as a recursion on the average width after k more steps with current location x and a to b already painted, averaging on either the walk left or right.  This gives O(N^4) which is too slow and way too much memory, but the actual location x doesn’t matter, instead a and b can be normalized as distance to left edge and distance to right edge.  This gives O(N^3), which is feasible for run time, but the memoization table would exceed memory limits.  Even using some symmetry like if distance to left is greater than right we can flip them without loss of generality, I am pretty sure memory usage cannot be made to fit.

But this does give me another idea.  If we could get rid of one of left and right, O(N^2) space would be easy to fit.  This leads to the idea that memoize over remaining steps and current width where the current location is at one edge.  In this scenario the recursion would have 2 possibilities.  50% chance of growing width by one and reducing remaining step count by 1 and some other chance of not changing the width, but reducing the step count by k.  This requires the computation of the number of ways to choose a random walk which stays strictly in a given width starting from the edge of that use up all remaining steps, or lesser steps which end up at one of the edges of the width.  Using precomputed combinatorics tables, I think this can be calculated in O(N) time, giving the result needed, but the details are more complicated than I think I could have worked out in competition.

Turns out that I really got lost on this one, because there is a much simpler solution if I had of stuck on back where I started.  The simple O(N^3) space and time solution can be made to work by using a dynamic programming approach instead of recursion with memoization.  In this case you can use two O(N^2) size arrays and switch between them to calculate each number of steps remaining, since the recursion always decrements steps remaining by exactly one.  The final generated table contains the answer needed.

Looks like it was pretty competitive to qualify in this round.  With two questions that were not that difficult and one which was quite unusual and challenging the top 1000 were defined by getting both of the first 2 questions completely in under 2:15.  The third question was unusual because it was based on randomness to the point that there was a chance you would get it wrong even if your code was as good as it could be.

Q1) Given a set (no duplicates) of binary representations of equal length, determine if there exists a bit flip pattern which can be applied to all of them such that they become set equal to a second set (no duplicates) of binary representations of same size and length.

A1) The actual wording of this question was quite involved and I suspect would hide how easy this question is to many.  The small input was limited to up to 10 bits in length, so a brute force of the 2^10 bit flip patterns could be tried.  Large input however went to 40 bits to ensure such an approach wouldn’t work.

Looking at the other constraint however, the number of elements in each set, that is limited to 150, so a O(N^2) is clearly feasible.  Since every element in the original set has to map to an element of the target set, obviously at least one element in the original has to map to an element of the target set.  So take one element of the original set and determine the bit flip pattern which will work for each member of the target set.  Then for each of these up to 150 patterns (rather than potentially 2^40) the set equality can be tested.

For a nice compact solution code, the bit patterns on input can be parsed into 64 bit integers.  Then the bit flip pattern can be represented as another 64 bit integer, which will be applied using xor.  In this version generating the (up to) 150 patterns is as simple as calculating the xor of one element of the first set with each element of the second.  Each element of the target set can be placed into a set object, and the set equality (since we already know that they have the same number of elements and that xor with a pattern is a bijection, so there won’t be any duplicates generated) is as simple as checking that every value in the original set xor’d with the pattern value is a member of that target set.

Q2) Given a connected acyclic undirected graph, determine the minimum number of nodes to remove to be able to make it into full binary tree (where every node other than a leaf has 2 children for some choice of root).

A2)  Again the small input invites brute force with only up to 15 nodes.  The large input of up to 1000 nodes is more interesting.

With a limit of 1000 nodes O(N^2) is acceptable, and this is not too difficult to obtain.  Choosing each of the nodes in turn as a possible root node, a recursive solution taking two parameters, current node index and previous, can traverse the tree in O(N) time.  Specifically the recursion is the maximum nodes which can be kept – the final answer then being the best of each possible root subtracted away from the total number of nodes in the original graph.

The recursion is to consider every edge of the current node which doesn’t connect to the previous node.  Recursion down those edges will return a set of values.  If the set is 2 or greater, choose the largest two and return the sum, plus one for the current node.  Otherwise just return 1, since only this node can be kept.  For each recursion run from a root this obviously linear in the number of edges. Each edge is only considered twice, once on the way out and again to be excluded at the next level down in the recursion.  Since there are no cycles in the graph, the recursion trivially terminates when it gets to a node with no connections other than to the previous node.  Since the graph is acyclic and connected the number of edges equals N – 1 and so the total running time over all recursions is O(N^2).

Of interest to me here was whether the problem can be solved in O(N). The recursion itself invites a memoization over previous and current, which has O(N) states, but a simple star type graph, shows the total time in this case is still O(N^2) because the centre node of the star can be arrived from each of the leaves and has O(N) exiting edges which must be considered.  Even with the trivial optimization of not calling the recursion if there is only 1 candidate which fixes the basic star case, slightly more complicated star type graphs are still O(N^2).

I think I have a solution, which unfortunately complicates the algorithm a bit.  The idea is for each node to gather the (up to) 3 highest values of the recursion which have it as the previous node.  So we start by performing the standard set of recursions, but rather than simply taking the best 2, and memoizing the sum we take a slightly different set of rules.  First check if a memoization value for current node exists.  If not, recurse as normal, but store the 3 highest values and the previous index in the memoization for the current node, rather than memoizing against the sum against the current/previous pair.  If a value does exist in the memoization table but the table entry also contains a valid previous index which is not the same as the current one, call the recursion specifically for that edge, and replace the smallest value in the memoization table if appropriate, and mark the previous index in the memoization table as invalid.  Now there are up to 3 largest values in the table, and we can select the 2 largest of those are not for the previous index.

So, the memoization table contains O(N) entries, each of which get updated at most twice.  Since it is clear that the recursive calls made are only a subset of those made by the original algorithm, it will terminate.  The claim that it is has a total run time of O(N) is slightly trickier.  The first time a specific value in the memoization table is calculated, it could involve O(N) calls to recursion, but because the memoization is stored keyed by nodes instead of by previous/current pairs it won’t potentially be rerun for multiple different previous nodes, which is what caused the O(N^2) logic in the previous version. Basically each node may be visited once for every edge it has, but the total work performed over those visits is proportional to the number of edges it has.  Since each edge connects 2 nodes, each edge in the graph might be considered twice, but not repeatedly as in the original algorithm.  This makes the total run time proportional to the number of edges and hence total run time is O(N).

Q3) Given 120 examples of permutations of the numbers 0 through 999 where each one was generated either by a correct, or incorrect random shuffle with a 50% chance, correctly identify at least 109 of them.  Initial state before shuffle is ascending order and the incorrect random shuffle performs one random swap for each index in order from first index to last, with a randomly selected index which is selected amongst all indexes. (As opposed to correct which only selects from current or higher indexes.)

A3) Since the incorrect shuffle has as a subset of its possible swaps all of the possible swaps performed by the correct shuffle, there is no pattern which is ‘obviously’ only the output of the correct shuffle.  Also since every permutation is a possible output of the correct shuffle there are none which are obviously only the output of the incorrect shuffle.  Therefore the best you can do is come up with a heuristic which tells you something about the probability of a permutation being from the incorrect shuffle and hope that it can managed to identify 109 out of 120 a decent percentage of the time.

I think the key component of this problem is actually writing a program to perform the incorrect shuffles so you can look at the probability distributions.  One aspect of a correct random shuffle is the probability of index i being k should be equal for all valid k and i.  If you were to run 1 million shuffles for instance, there should be approximately 1000 cases of any given index i being equal to a specific value k.  Running 1 million incorrect shuffles, takes a while, but not so long as to rule out doing it once for every time you submit the problem set.  Indeed this naturally leads to an approach of generating this table, and then for each input looking up the index and value for the 1000 elements, and calculating a product of the ratio of the value in the table to 1000 (to avoid over/underflowing double) for each lookup.  The higher the result the more likely it is from the incorrect shuffle.  It might seem at first glance that a threshold of one is appropriate but the calculations are more complicated than that and they are effectively overlapping distributions where you want to choose a threshold to minimize false positives and false negatives. Potentially better luck can be had by taking into account the fact that things are generated with equal probability of correct or wrong and instead sorting the scores and giving out the highest half scores as being incorrect and the lower half as being from the correct sort method.

I found this approach to be somewhat cumbersome, and 1 million incorrect shuffles is 1 billion random number and swap operations, which is a lot of CPU time to be chewing up every submission.  So I had a look at the generated tables and tried to come up with a formula which approximated their outcome with minimal computation cost.  I came up with if value <= index return 1.0, otherwise linearly interpolate 1.3 to 0.7 for values between index + 1 and 999.  Using this and some sample testing I ran on my machine with a bunch of randomly generated problem sets I was managing to get a >93% success rate at identifying individual permutations correctly with an appropriately selected threshold.  This may only be 112 out of 120, but it does provide a pretty decent chance of getting past on any given submission.

Since I got through last round, I didn’t have to stay up all night this weekend – which was good since I was pretty tired already!

43 people solved all 3 problems – >300 2 and the 750th cut off was 196 points, so at first glance the problems look like they might have been more difficult than last week.  The number of people with a point score in the >190 range was almost 1400 – so a small time difference on the first problem was a big difference in placement.  At first glance I thought 196 points was a pretty low score, but it turns out Q1 was only worth 200 points this time, so it truly was a race to qualify if you were unable to solve either of the larger questions.

Q1) Given a sequence of ‘good’ and ‘bad’ and a value for each, determine whether the running sum is ever negative (‘bad’ value is subtracted, ‘good’ is added).

A1)  Such a very very straightforward question here, I can see where the rush came from. 4 trivial lines of code will get this done…

Q2) Given a rectangular grid of cells, determine the minimum number of horizontal or vertical lines (which extend the full width/height each) which will ensure all ‘wolf’ containing cells are separated from all ‘sheep’ containing cells.

A2) A big step up in difficulty here, reflected by the 600 point score I guess.

A simple starting point is every wolf adjacent to a sheep implies a line.  With a 16×16 grid brute force is just out of reach with there being up to 30 lines.  However the limit of only 16 is suggestive when if the problem was was an easy polynomial DP type solution it would probably allow up to 50×50 grids.

So, one approach is to try all 2^15 options for one dimension and then ‘as required’ add lines in the other dimension.  This ‘greedy’ approach of putting off adding lines as long as possible, seems reasonable when there is only one dimension of consideration.  Alternatively if that seems too risky there should be a simple DP of minimum number of lines needed for the first k columns with the last line at column x, however the running time is starting to get a bit risky at 2^15 * 16^3 (requiring some pre-computing to get it down to that low even I think…).  The as need approach (looking at someone else’s solution which passed) seems like it can be done in 2^15 * 16^2 operations which is much safer, this still requires some care to avoid accidentally getting an extra factor of 16.

Q3) Given a tree of n nodes where each node other than the first specifies its parent, determine probability that the kth ‘bird’ can land on the tree if they random walk down from the root to avoid having more than 1 birds on a node and fly away if the final child they arrive at is occupied.

A3) So my first thoughts about this problem was that it was a simple ‘calculate probability of kth bird landing on each spot using probability that each spot is filled as of k -1th bird’, and accumulating up from the no birds scenario, but this doesn’t work – because of correlation effects, there are cases a simple method like this will count that can’t actually happen.  The probability of landing depends strongly on the number of birds that have passed through a given child.

Instead you need to calculate the probability the kth bird will land if k-1 birds have already passed through a given node.  Boundary conditions are If k = 1, then 100 %.  If the node has no children, then 0%.  Otherwise binomial coefficients are involved for each child and the subset of k – 1 which went down that child, plus 1 for the current bird.  Basically given the c children, what is the probability of n out of k – 1 birds go down any specific child is multiplied by the chance n+1th bird will land if n birds have already gone through that child.  This is then averaged over the children.

I suspect I wouldn’t have solved this problem in time, the strong dependence in the probability on the number of birds is a bit deeper into probability theory than I grasp intuitively.