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.