Contest analysis is already posted – 27170 positive scores and 1710 perfect scores. \u00a0Not mentioned was the cut-off, 22154 people are currently eligible for competing in Round 1.<\/p>\n
The success rates for large were quite high for both of the first two problems, but quite a bit lower for the third and fourth. \u00a0I expected a low pass rate for the large input on the fourth as I’ll discuss later, but the third is less obvious.<\/p>\n
Q1) Consider multiples of N, what is the end of the sequence which contains every digit in base 10 at least once at some point during the sequence.<\/strong><\/p>\n A1) As mentioned in the contest analysis, it can be proved that other than 0 the maximum sequence length has an upper bound of 90, and the specific case of 125 gets close at 72. \u00a0Therefore the largest number to consider will be less than 90 million, so there is no risk of overflow. \u00a0So this problem boils down to can you correctly break a number down into its base 10 digits. \u00a0This is a pretty common operation in coding competitions for some reason or another, but one which is missing from TMD.Algo – I think I’ll fix that.<\/p>\n Q2) Given a sequence of – and + characters, determine the minimum number of operations to turn them all into +, if the only operation you can perform is to reverse the first k characters and also invert them all so – becomes + and vice versa.<\/strong><\/p>\n A2) The key to this problem is that a change between – and + in the sequence will always remain a change during any operation unless the operation only includes one of those characters and the first element of the sequence is equal to the kth element of the sequence. \u00a0Therefore the number of changes, plus potentially one more because you end up with all -, is a trivial lower bound. \u00a0And simply repeatedly fixing the first change in the sequence is the solution because the prefix is always all the same character. \u00a0My preferred solution is to append a + on the end then just count where character not equal its next.<\/p>\n Q3) Generate a set of sequences of 1’s and 0’s that start and end with 1 and have a specific length, and when interpreted in each base 2 through 10, are always non-prime.<\/strong><\/p>\n A3) \u00a0This was an unusual problem in that the entire test set was in the problem statement, there was nothing unexpected. \u00a0And despite that the large input only had a 70% pass rate. \u00a0This suggests a lot of people tried to be tricky like the contest analysis proposed, rather than just brute forcing with an arbitrary precision type. \u00a0Or didn’t realize that a 32 digit base 10 number is too large for 64 bit integers – I hope there wasn’t too many in that group, given to pass the small they would have already realized a 16 digit base 10 number is too large for 32 bit.<\/p>\n Anyway I just brute forced this problem using BigInteger and checking for trivial composites with factors less than 9. \u00a0Interestingly I found that just checking for composites using just 3 and 7 or 5 and 7 was effective, but not using just 3 and 5 or 2 and 7. \u00a0I’m not clear on why this is the case though, the contest analysis talks about a 3,2,7 being very popular so I guess 3,7 works for a significant fraction of those?? \u00a0Really I’ve not done enough investigation to be sure.<\/p>\n Like the first problem, this problem involved digits, specifically for the brute force, interpreting them as values in different bases. \u00a0This is a pretty simple piece of code to write, but also one that shows up in programming competitions a bit, so it feels a bit of a deficit in TMD.Algo which I should fix.<\/p>\n Q4) Assuming that a K^C element sequence of L and G is generated by repeatedly applying a\u00a0rule that starting with a length K (but otherwise unknown) base pattern of L and G a derived pattern is created by replacing each L with the original base pattern and G with an equal length sequence of G’s, determine S locations to check which will prove whether the are any G’s in the full sequence.<\/strong><\/p>\n A4) \u00a0So this problem had a very trivial small input. \u00a0Regardless of the base pattern the first K characters are either base pattern, or all G. \u00a0If any of them are G then obviously the pattern contains a G. \u00a0If not then the base pattern is all L’s, which obviously means the entire sequence is L. \u00a0So when S = K you just return the numbers 1 through K.<\/p>\n The problem is that this approach tells you nothing about the large input. \u00a0Unless you actually understand the problem fully, you could come up with ways to do better than S = K, which will pass the small input, but then you’ll fail the large. \u00a0I think a second small input set where S could be anything, but K^C was limited to a much smaller number could have caught the first order failure to fully understand the problem without clearly giving away the full depth.<\/p>\n Anyway, I like this problem because of the subtle connection back to problem 1 and 3. \u00a0This is actually a problem about digits. \u00a0Given a zero-based trial location the zero-based positions in the original base sequence which could affect the trial locations value are the same as the digits of the trial location when written in base K. \u00a0More specifically, if any of those locations are G then the trial will return G. \u00a0So the ideal search is a set of C digit base K numbers where there is no unnecessarily repeated digits. \u00a0If any of the base pattern contains G, one of the search locations will be a G, otherwise the entire sequence is L’s since the base pattern is all L’s. \u00a0Once I have some nice digit sequence logic in TMD.Algo, I think the implementation for this solution will only be a couple of lines.<\/p>\n","protected":false},"excerpt":{"rendered":" Contest analysis is already posted – 27170 positive scores and 1710 perfect scores. \u00a0Not mentioned was the cut-off, 22154 people are currently eligible for competing in Round 1. The success rates for large were quite high for both of the first two problems, but quite a bit lower for the third and fourth. \u00a0I expected … Continue reading GCJ16 Qualification Round<\/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],"tags":[],"class_list":["post-818","post","type-post","status-publish","format-standard","hentry","category-code-competitions"],"_links":{"self":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/818","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=818"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/818\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=818"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=818"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=818"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}