{"id":223,"date":"2010-07-20T13:39:37","date_gmt":"2010-07-20T13:39:37","guid":{"rendered":"http:\/\/www.themissingdocs.net\/wordpress\/?p=223"},"modified":"2010-07-20T13:39:37","modified_gmt":"2010-07-20T13:39:37","slug":"tc-srm-472","status":"publish","type":"post","link":"https:\/\/www.themissingdocs.net\/?p=223","title":{"rendered":"TC SRM 472"},"content":{"rendered":"

Q1) 2 people take turns to remove powers of 4 from a number which starts with n. Where each player tries to be the last person to remove a number determine who succeeds.\u00a0 n is up to 1 billion.<\/strong><\/p>\n

A1) This problem seems to be one of ‘solve by inspection’. Simulate the first few thousand values of n using dp and you’ll quickly see that the results form a regular pattern.\u00a0 2 out of every 5 return player 2, the rest return player 1.\u00a0 Mathematical induction can be used to prove that the pattern continues by noticing that all powers of 4 are either 1 or 4 mod 5.\u00a0 In the end the code boils down to k = n mod 5; return (k == 2 || k == 0) ? “player 2” : “player 1”;<\/p>\n

Q2) Given n cards which each have a number on the front and back such that numbers 1 to n each occur exactly once on the front and exactly once on the back, determine the number of different lists of n numbers which can be formed by reordering the cards in any order, with any face up. n is up to 50 and the answer should be returned modulo 1 billion and 7.<\/strong><\/p>\n

A2) This seemed a tricky question, and inspection of round statistics showed I was not alone in finding it hard.\u00a0 The most important trick is to realise that if each card is consider as a link between the number on the front and the back, and each case of the same number is linked together, the full set of cards can be divided into cycles which each are independent of the others.\u00a0 If the cycle consists of a single card, it has no options, only possible locations in the final list.\u00a0 If it is longer, it both has a number of options which is dependent on the cycle length, and the number of ways that cycle can be interspersed into overall list.\u00a0 The answer becomes the product of the number of ways each cycle length can be chosen from n reduced by the length of cycles already considered times the number of ways a pattern can be made in the cycle itself.<\/p>\n

The number of ways a pattern can be made in a cycle can be calculated a number of ways, dp is one option, although it seems a little tricky.\u00a0 An analytical approach is easier.\u00a0 Each number on the front of the cards which are in a cycle can either be present 1 2 or 0 times.\u00a0 Each 2 implies a 0, so it seems helpful to consider each case of the number of 2’s separately.\u00a0 The number of ways to select which numbers are available to use with k doubles is the tricky bit, once you have that can boost that to get the full answer by multiplying by the number of orderings, which is n!\/2^k if there are k 2’s.\u00a0 While each 2 implies a 0, it doesn’t imply exactly where that 0 is, other than it is somewhere before the next 2…\u00a0 So we need to reserve 2k spots for the 2’s and 0’s and then we need to alternate 2’s and 0’s, which gives 2 options.\u00a0 So mathematically it is C(n, 2k)*2.\u00a0 However in the case of k=0 there is only 1 option, so we need to get rid of the multiplication by 2. Which gives C(n, 2k)*(k==0 ? 1 : 2).<\/p>\n

And that’s all the components, all that remains is to sum things up and multiply it all out and perform a lot of modulo operations everywhere.\u00a0 (Pre-calculate the choose function using DP as usual.)<\/p>\n

Q3) Consider a h x w rectangle of tiles where each tile is coloured with one of 4 colours.\u00a0 Determine the number of ways to make every tile a different colour from its (up to 8) neighbours, while only changing at most k tiles. Limits: h and w up to 50, k up to h*w.<\/strong><\/p>\n

A3) After problem 2, I’m surprised there was even 12 correct solutions to this one.\u00a0 First up there are a couple of special cases.\u00a0 If height or width is 1, simple dynamic programming provides the solution.\u00a0 In fact the rest of the approach used to solve the problem requires height and width greater than 2, so it we have to solve that first.<\/p>\n

For height and width greater than 2 consider each possible set of 4 colours for the top left corner.\u00a0 Playing around with the possibilities which satisfy the different colour to neighbours requirement you discover that every second row is identical or every second column is identical, or both. So assume the rows are identical, each column after the first 2 has 2 choices for patterns.\u00a0 Then assume the columns are identical, each row after the first 2 has 2 choices for patterns.\u00a0 This gives us 2 DP (very similar, in fact you can do a diagonal flip of the input and use the same DP for each).\u00a0 In each DP you have number of ways to make the first n rows work (columns) using j changes.\u00a0 Then sum all values of j from 0 to k for the all h row case, and presto you have the number of ways for column (row) alternation for a given 2×2 top left starting point.\u00a0 Sum column and row together and … wait a second.\u00a0 As mentioned earlier there is a case where both rows and columns alternate.\u00a0 For a given 2×2 starting point, there is only one such case, but if it can be achieved in k changes or less, we’ve counted it twice.\u00a0 So check that quickly and subtract it off.\u00a0 Sum over all 2×2 starting points and presto you are done.\u00a0 Not an easy problem, but I almost wonder if it was actually easier than question 2.<\/p>\n","protected":false},"excerpt":{"rendered":"

Q1) 2 people take turns to remove powers of 4 from a number which starts with n. Where each player tries to be the last person to remove a number determine who succeeds.\u00a0 n is up to 1 billion. A1) This problem seems to be one of ‘solve by inspection’. Simulate the first few thousand … Continue reading TC SRM 472<\/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-223","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\/223","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=223"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/223\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=223"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=223"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=223"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}