Last round 1 for this years topcoder, 750 to advance, but only 615 registered. \u00a0So positive scores to advance. \u00a0In the end 500 people managed to get a positive score.<\/p>\n
Q1) Determine if a set of integers is closed under addition.<\/strong><\/p>\n A1) This is a very simple problem with an optimization which I think I might have tried, but screwed up. \u00a0Lucky I already got through in round 1A. \u00a0Just try all pairs, add and check for membership. \u00a0Even the O(N^3) solution is fast enough.<\/p>\n With all the inputs between +\/-50 its a trivial O(N) to perform a distinct count, then return false if there are more than 3 distinct values. \u00a0If any non-zero number has more than 1, return false. \u00a0Otherwise check all pairs on the 3 values.<\/p>\n Q2) Determine if a sequence of C’s B’s and A’s can be reordered so that no B’s are adjacent and no C’s are within 2 of each other.<\/strong><\/p>\n A2) So I think there should be some kind of pseudo-greedy approach to solve this, but all the solutions I’ve seen are dynamic programming. \u00a0The state is the number of A’s remaining, number of B’s remaining, number of C’s remaining and whether the last letter is a B or which of the last 2 letters is a C. \u00a0So for each possible state if there is an A remaining you can reduce the A count by force last letter to not be B and shift which of the last 2 letters is a C back one. \u00a0If there is a B remaining and last letter is not B, decrement B, mark last as B and shift which of the last 2 letters is a C back one. \u00a0Similarly for the C. \u00a0If the destination state already has a string assigned to it, skip, else use the current string and append the new letter and assign it to the new state – put it on a queue to consider.<\/p>\n If you ever get to a state of no more A, B, or C – return the string associated with the state. \u00a0Number of states is O(N^3) and each state has a string creation cost. \u00a0Total O(N^4) is fast enough. \u00a0Can be done in O(N^3) by not actually constructing full strings, just storing pointers to the come-from state.<\/p>\n Q3) Determine the number of integers between 1 and X when represented in binary for which the largest non-empty subset of at most length – K digits is less than Y.<\/strong><\/p>\n A3) X and Y can be huge – so this problem is challenging. \u00a0I’ve not groked any solution yet. \u00a0Obviously all numbers less than Y are trivially a pass, but that is where it stops being easy.<\/p>\n","protected":false},"excerpt":{"rendered":" Last round 1 for this years topcoder, 750 to advance, but only 615 registered. \u00a0So positive scores to advance. \u00a0In the end 500 people managed to get a positive score. Q1) Determine if a set of integers is closed under addition. A1) This is a very simple problem with an optimization which I think I … Continue reading TCO16 R1C<\/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-829","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\/829","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=829"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/829\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=829"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=829"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=829"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}