I got a successful challenge this round, don’t know how long it has been since that last happened… 347th before systests, I managed to move up to 292nd afterwards.\u00a0 Quite a few failures in the second question, wish they had been in my room so I could have challenged them too… \ud83d\ude1b<\/p>\n
My TopCoder rating is now up to 1836, almost a personal best… (although still quite a ways short of where I want it…)<\/p>\n
This is the second time I’ve scored as well as was needed for a t-shirt in previous years (292nd is a virtual 342nd after you allow for the 50 already through – although I got a higher score today than 3 of the 11 who bothered to compete in the parallel round for advancers).\u00a0 If I make it 3 from 3 and don’t win a t-shirt I’ll be rather disappointed – and I didn’t even sneak a completely invalid solution past the system tests this time \ud83d\ude1b<\/p>\n
Q1) Given the numbers 1-N which are placed in some order where you only know where some of them are, what is the minimum number of picks of spots to guarantee you reach a target value. (Target value is large.)<\/strong><\/p>\n A1) I think this problem is relatively greedy.\u00a0 First up there are either 2 things you are going to do, pick the highest known value, or rotate through all the unknown values.\u00a0 It never helps to choose an unknown value over and over, because it could be the minimum of the unknowns.\u00a0 So I can see 3 strategies.\u00a0 1) You simply use the highest value forever. 2) You simply rotate through the unknowns forever, presuming you get the smallest of the unknowns on your last rotation.\u00a0 3) You rotate through the unknowns for as many full cycles as possible, then use the highest known value until finished, because the last cycle as partial, might have a lower worst case average than the highest known.<\/p>\n So try each of the 3 scenarios, and choose the best.\u00a0 Handling corner cases like no unknowns or all unknown.<\/p>\n Q2) Given items of known weight, and the following game, determine the outcome if both players play optimally.\u00a0 Each turn players can move a specific number of items from their pile to the opponents pile, these numbers are provided.\u00a0 If their pile doesn’t contain that many items, all items are moved.\u00a0 The first turn however is player 1 chooses which of the starting set of items (also provided) is placed into player 2’s pile.\u00a0 Assume that the aim of the game is to maximise the weight of your opponents pile minus the weight of yours, and in equal situations both players aim to maximise the total weight. Items have a large weight range.<\/strong><\/p>\n A2) I managed to solve this problem, but I didn’t get my implementation written in time.\u00a0 This was also the problem I managed to get a successful challenge on.<\/p>\n First up is to realise that the game is entirely greedy and easily determined after the first player chooses the initial items.\u00a0 At any point in the game you will always give your heaviest items to the opponent, there can be no benefit in giving the lighter ones.\u00a0 So you can take a list of indexes for a virtual sorted array and simulate the game to see which indexes end up in each players pile.\u00a0 Now player 1 has to maximise their score, and for equals maximise the total weight, by assigning individual items to these indexes in sorted order.<\/p>\n So start by sorting the provided items by weight- it is now a fairly standard DP on maximising a valuation of selecting an ordered subset.\u00a0 However there is a small complication that some\u00a0indexes cause negative value, and others positive.\u00a0 But it doesn’t actually change the DP structure, you just want to build a lookup table of index to whether it is positive or negative multiplier.<\/p>\n Small tip I got from one of the solutions in my room was to make the DP table member type a custom class indicating the piles and write a custom comparator to compare the difference, or sum if equal.\u00a0 This means you don’t have to reconstruct the piles from scratch after you have finished your DP like I was going to have to.<\/p>\n Q3) Given numbers of the form a*x+b from x=1 to x=n, concatenated in their minimal length binary representation, how many times does the sequence change from 1 to 0 or vice-versa. b and n are both huge, a, not quite so much.<\/strong><\/p>\n A3)\u00a0 This was only rated at 900 points, but I have no clue how that makes any sense…<\/p>\n The last digit is going to have a trivial sequence,\u00a0 so tracking how the concatenation affects the result isn’t too crazy, but tracking the internal changes is still going to be problematic.\u00a0 Definitely going to be some pattern, but it isn’t going to be trivial.<\/p>\n Looks like the correct approach is to process the multiples in sections of powers of 2, but from there it gets complicated and I definitely need some sleep.<\/p>\n","protected":false},"excerpt":{"rendered":" I got a successful challenge this round, don’t know how long it has been since that last happened… 347th before systests, I managed to move up to 292nd afterwards.\u00a0 Quite a few failures in the second question, wish they had been in my room so I could have challenged them too… \ud83d\ude1b My TopCoder rating … Continue reading TCO12 R2B<\/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-548","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\/548","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=548"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/548\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=548"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=548"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=548"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}