Having passed through already I didn’t compete in this round, but I was interested to see how the turn out was without a Google Code Jam happening at the same time.\u00a0 Only 1023 people registered, which after allowing for the 700 advancers last time is only ~400 new people (assuming everyone who competed last time and didn’t advance, competed again) that became available without the code jam running.\u00a0 Looks like round 2 will probably be quite short of its 2500 target if this keeps up.<\/p>\n
Positive score criterion appears to have been the cut-off again, only 591 advancers.<\/p>\n
Q1) Find the size of the largest sub range of an array where at least half of the numbers have a common divisor other than 1.<\/strong><\/p>\n A1) With the array size limited to 50, and the size of the values limited to 1000, this seems a trivial brute force.\u00a0 There are 1250 sub arrays of average length 25 and (obviously) less than 1000 prime numbers to test for divisibility.\u00a0 There apparently 168 prime numbers less than 1000, so its not a huge win, but it does help a little if you happen to be working with a particularly slow programming language I guess.<\/p>\n Q2) Determine the expectation count of objects found if each object has a probability of being found on its own, and if found a list of other objects that will definitely be found (which expands transitively).<\/strong><\/p>\n A2) Up to 50 objects, so a brute force of every combination of basic find on its own chance is out of the question.<\/p>\n Each object can be expanded out transitively easily, but the question is how to combine the probabilities is not obvious.\u00a0 If an object is in isolation, nothing connects to it, the probability is simple.\u00a0 If the object is part of a cycle which has no external connections, the probability is 1 – product(probability of each member of cycle not being selected).\u00a0 Its the external connections which are trickier.<\/p>\n I think all cycles can be collapsed to be replaced with a single node with a ‘base’ probability as described above.\u00a0 Once the cycles are removed, the graph is now a directed acyclic forest.\u00a0 The roots are obvious they have their base probability and that’s it.\u00a0 Children then have probability of being chosen of 1 – product(base probability of not being chosen, and total probability of not being chosen for each parent) – remembering that each node can have multiple parents and we have to have calculated the total probability for each parent before we can start.<\/p>\n Apparently I’ve made the problem more complicated than required though – in effect the probability of an item being found is 1 – product(base probability of not being chosen) for every node that is transitively connected to the item in question.\u00a0 I can see how the math works out to be the same, but it wasn’t an obvious starting point.<\/p>\n Q3) Given a tree determine the number of distinct subsets of 7 vertices which are connected to such that the second is has the first as a parent\/grandparent, the 3rd 4th and 5th has the second, and 6th and 7th has the 5th.\u00a0 Subsets are distinct only if they have different members, order doesn’t matter.<\/strong><\/p>\n A3) Number of vertices in the tree is up to 2000, so brute force is trivially out of the question.\u00a0 It would seem a multiple pass dynamic program is in question.<\/p>\n First pass is number of transitive children for each vertex.\u00a0 Second pass is number of ways to select 2 children of a given vertex.\u00a0 Third pass is sum of products of the second pass for each child and the number of ways to choose 2 other children which are not the selected child or its descendants.\u00a0 Fourth pass is sum of the 3rd pass for each child.\u00a0 Final answer is the total of all values in the 4th pass.<\/p>\n The 3rd and 4th pass enumerate all transitive children for each vertex, this will only perform acceptably if you store the children as an adjacency list rather than checking for every potential vertex as a child in an adjacency matrix.\u00a0 Additionally the number of ways to select 2 children needs to be done as N*(N-1)\/2 – not by enumerating.\u00a0 Calculating N in the second pass is trivial from first pass, N in the 3rd pass is first pass value minus the first pass value for the currently selected child minus 1 more for the currently selected child itself.<\/p>\n","protected":false},"excerpt":{"rendered":" Having passed through already I didn’t compete in this round, but I was interested to see how the turn out was without a Google Code Jam happening at the same time.\u00a0 Only 1023 people registered, which after allowing for the 700 advancers last time is only ~400 new people (assuming everyone who competed last time … Continue reading TCO15 R1B<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6],"tags":[],"class_list":["post-785","post","type-post","status-publish","format-standard","hentry","category-random-musings"],"_links":{"self":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/785","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=785"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/785\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=785"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=785"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=785"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}