This SRM was cancelled due to some issues, but the questions are still there, so here I go…<\/p>\n
Q1) Determine the largest prime less than or equal to n, which when divided by 2 (each time rounding down) D-1 times, results in D primes being generated. Limits: n is up to 10million and D is up to 10.<\/strong><\/p>\n A1) Generating all primes less than or equal to n is easy, the only thing to be careful is that if your programming language of choice stores bool in 4 bytes, you’ll exceed the memory limit.\u00a0 So use byte, or bitarray, if needed.\u00a0 Once primes are acquired, start from n and keep walking down, when you find a prime check the dividing sequence, if it works return the current prime you started with.\u00a0 If you get to less than 2^D, break and return -1.<\/p>\n Q2) Given a directed graph with edges which each have a positive length if they exist (but the reverse edge may not have the same length as its matching forward edge), determine the shortest path (if one exists) which gets from vertex 0 to vertex n-1 where no sum of consecutive edges is 0 mod 13. Limits: n is up to 25. A2) This is a dp over the graph, shortest path to get to vertex i where the current modulus for the sum of each of the last k edges is represented as a bitset.\u00a0 From each value you generate more by considering each edge away from vertex i which itself does not have a length of 0 mod 13.\u00a0 The new bitset for the destination is the current bitset rotated by the edge length mod 13, unioned with the bit indicating the edge length mod 13.\u00a0 If the rotation causes the 0th bit to be set, do not add the new destination to the set. If we do add it,we minimize length between the new length total of current state + edge length, and any existing path found to the new vertex with the new bitset.<\/p>\n Because before the rotate bit 0 is not set, and after the rotate bit 0 is now in bit edge length mod 13), every step adds a new bit.\u00a0 This means that the depth of search is at most 13.\u00a0 It also means that the appropriate dp order is by number of set bits. By using the dp, we ensure we ensure that rather than worst case ~24^13 it is at most 2^13*24, which is much more reasonable.\u00a0 Once the dp is generated, we walk all bitsets for the destination node and choose the smallest.<\/p>\n As an aside, since all cases where the 0th bit is set are discarded, you can alternatively use a 12 bit bitset, but you get added shifts since the rotate operation needs to occur on a 13bit representation.<\/p>\n Q3) Given up to 50 line segments which have integer dx\/dy\/dz, what is the maximum distance (squared so answer is an integer)\u00a0 between the start and end you can achieve by joining them end to end such that the created line does not self-intersect.<\/strong><\/p>\n A3) <\/strong>I managed to get some ideas for this but wasn’t sure if I was on the right track, so I took a look at some solutions.\u00a0 Probably the most important bit which I did get was that the self-intersect restriction is irrelevant, any self-intersecting arrangement can be made non-self intersecting and at the same time larger, by fairly simple rearrangement of the connections.\u00a0 The other important point is that the order of the edges is irrelevant, it only matters which end you choose to connect on to the current line.\u00a0 (Still with up to 2^50 combinations, you don’t want to try them all…) Most of the solutions I saw were along the lines of ‘choose a random direction, and choose to connect each edge such that it has a positive or 0 dot product with that direction.’\u00a0 Repeat while clock says less than 1.8 seconds past, and hope the best one found is the winner.\u00a0 The solution in my head before I started looking at solutions was similar, only rather than random directions, it was try each edge direction, I gather that this would have not been sufficient as some other solutions were like that,but then threw in extra random trials, or tried directions perpendicular to pairs of edges, and added some random trials as well.\u00a0 I found 2 solutions which did not use a random number generator, but I haven’t actually copy pasted them and run them through system check to ensure they are right…<\/p>\n Option 1, Firstly, join all parallel edge to make them into a single edge with length equal to sum of the components.\u00a0 Then for every pair of edges, calculate the cross product.\u00a0 Use dot product to select order in the direction of the cross product.\u00a0 However, some edges will have a 0 dot product.\u00a0 Try to maximise these in 4 different directions (using dot product), each of the positive and negative cross products of the incoming cross product and one of the first two edges.\u00a0 One of these maximisation attempts will be largest, return it.<\/p>\n Option 2, Consider each pair of edges, and calculate the cross product.\u00a0 Perform straight dot product optimisation like before, but don’t bother trying to optimise the 0 dot product cases.\u00a0 For edges, also try the ‘jittering’ the endpoints +\/- 1 in each direction, to create 26 variants, and repeat considering each pair of edges including these jittered versions.\u00a0 This jittering tilts the created cross products, sort of simulating the different secondary optimisations which were applied to the 0 dot product cases.\u00a0 Seems kind of dodgy to me, but then so does option 1.<\/p>\n The only bit that I didn’t really get was using cross products to choose the direction of primary maximisation.\u00a0 The only thing I can see for sure is that it results in a lot more directions being tried. But you would think that trying each pair-wise sum would achieve the same goal.\u00a0 Not sure on this.\u00a0 With the SRM being cancelled, I guess there probably isn’t an official write up either for me to check on.\u00a0 If every line segment was in the same plane, the cross product approach is completely useless since it actually only results in 1 direction, and every line has a 0 dot product with that direction.<\/p>\n","protected":false},"excerpt":{"rendered":" This SRM was cancelled due to some issues, but the questions are still there, so here I go… Q1) Determine the largest prime less than or equal to n, which when divided by 2 (each time rounding down) D-1 times, results in D primes being generated. Limits: n is up to 10million and D is … Continue reading TC SRM 471<\/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":[3,6],"tags":[],"class_list":["post-227","post","type-post","status-publish","format-standard","hentry","category-code-competitions","category-random-musings"],"_links":{"self":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/227","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=227"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/227\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=227"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=227"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=227"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\n<\/strong><\/p>\n