Another past SRM.<\/p>\n
Q1) Given a list of n spots, where each spot is one of 3 types, and k markers, which are initially randomly placed such that no 2 markers are on the same spot, follow the rules where markers in the left most spot are moved right, markers in the right 2 most spots are moved left, otherwise markers on type 0 are moved left, type 1 move right, and type 2 moves left on the first move, but otherwise moves back to where they came from in the previous turn.\u00a0 At the end of each turn the right most spot is removed from play, and any spot with 2 markers is cleared.\u00a0 Determine the ‘expectation value’ for the number of markers left when there is only 2 spots left. n is up to 17 as is k.<\/strong><\/p>\n A1) This is a question of details.\u00a0 The important realisation is that determining the expectation value can be done by performing every possible starting scenario.\u00a0 Worst case is n of 17 and k of 9 which has 24thousand possible starting points.\u00a0 Each simulation is O(n^2).\u00a0 After that it is a matter of implementing the simulation correctly.\u00a0 Type 2 moves would be tricky, but the requirement to remove all cases with 2 markers on the same spot means a simple bool array ‘camefromright’ (initialised to false) is sufficient to make that work.<\/p>\n Q2) You start with 1 pair of an animal which is 1 year old. At age 2 the animals can breed to produce a new pair which will be age 0.\u00a0 All pairs which are age 2 or higher will breed.\u00a0 In some years after breeding half of the entire population of pairs will ‘leave’ never to be considered in the problem again.\u00a0 If the number of pairs in the population is odd, the number of pairs which leave is half rounding upwards.\u00a0 The specific years are provided in a list which has maximum length 50.\u00a0 How many pairs of animals will there be after breeding (and possibly leaving) for n years?\u00a0 n is up to 10 million so the numbers may be very large and the results should be returned modulo 1 billion and 9.<\/strong><\/p>\n A2) This is the Fibonacci sequence with a twist.\u00a0 The leaving years are the tricky part.\u00a0 With a maximum of 10 million, you don’t even have to implement accelerated Fibonacci using matrix powering.\u00a0 Leaving years aren’t too tricky – they remove all of the old population and half of the 1 year olds, leaving all the babies.\u00a0 The halving can be done modulo 1 billion and 9 by multiplying by 500 million and 5.\u00a0 The problem is the case where the number of pairs is odd.\u00a0 Because of the modulo 1 billion and 9 (which is odd) you don’t know which numbers are odd or even once they overflow.\u00a0 So the real trick to the problem is knowing when something is odd.\u00a0 First thought is we can perform the same set of actions, also modulo 2.\u00a0 However there is no inverse of a number which is not co-prime with the modulus.\u00a0 So when we divide by 2, our modulo 2 is broken.<\/p>\n So it would seem we are at an impasse.\u00a0 I certainly would have been.\u00a0 However there is a trick (which I learnt from reading solutions :P), if you use modulo 4, you can perform a literal divide by 2 and only the high bit of the modulo will be broken. The low bit will still be accurate.\u00a0 With up to 50 leaving years, modulo 2^51 would be sufficient to allow us 50 divide by 2’s and still have an accurate low bit.\u00a0 Nice trick.<\/p>\n You can take that trick one step further, in programming languages where integer overflow is defined to wrap (which is not necessarily true in c++), addition and subtraction are implicitly modulo 2^(the number of bits in the number) so you can skip the whole modulo thing entirely and just use 64bit numbers for working out whether the numbers are even or odd.<\/p>\n Q3) There are up to 50 people, who answer up to 50 questions.\u00a0 Each question has a point value, and some questions have been marked and others have not.\u00a0 For questions which have been marked we know whether each person is correct or not, otherwise we only know if they answered the question or not.\u00a0 We are going to select k people from the top n scores once we finish marking.\u00a0 Equal scores are broken by order of person in the input.\u00a0 Looking forward from this intermediate stage, how many different possible groups of k people are there?<\/strong><\/p>\n A3) I didn’t get far on this question before giving up and reading solutions.\u00a0 My favourite approach is to start off by caching choose function for up to 50×50.\u00a0 Then resolve the problem by rephrasing it as ‘how many different groups of k people are there where person ‘i’ has the lowest maximum possible score’, and summing for each possible ‘i’.\u00a0 These sub problems can be resolved by considering that people with a higher minimum score than the lowest maximum possible score ‘must’ be in the top n scores, and people with lower maximum possible scores cannot be (due to the requirement that ‘i’ is the lowest maximum possible score), the rest are entirely optional, we can toggle them in and out in any combination.\u00a0 Then so long as we don’t have more than n-1 ‘must be in’ and we don’t have less than n-1 must and optionals, we can consider each partition between musts and optionals to make the group of k up until we choose so many optionals than the top n criterion would be overflown.\u00a0 This is the sum of the product of the 2 choose functions, 1 for choosing from the optionals, and the other to choose from the ‘musts’.<\/p>\n In case the above is not convincing enough, a few pointers to make it clearer why it works.\u00a0 Firstly ‘i’ being the lowest maximum possible score ensures there is no overlap between considered scenarios.\u00a0 Then the fact that optionals can be independently toggled in and out means we aren’t counting cases which are impossible in the simple product of choose functions.<\/p>\n","protected":false},"excerpt":{"rendered":" Another past SRM. Q1) Given a list of n spots, where each spot is one of 3 types, and k markers, which are initially randomly placed such that no 2 markers are on the same spot, follow the rules where markers in the left most spot are moved right, markers in the right 2 most … Continue reading TC SRM 475<\/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-215","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\/215","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=215"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/215\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=215"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=215"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=215"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}