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

Q1) Given a sequence of step, turn left and turn right commands, which are repeated infinitely, determine whether you will stay in a constrained (but not specified) area, or drift off in to the distance.\u00a0 Maximum command sequence length is 50.<\/strong><\/p>\n

A1) There are 4 scenarios.\u00a0 1. You come back to where you started. 2. You end up facing the opposite way you started, and so the second run you end up back where you started. 3. You end up facing 90 degrees to where you started, in which case after 4 runs you trace a ‘square’ and end up where you started. 4. You end up facing the same direction as where you started, but not where you started, in this case you drift away.\u00a0 In any case, simulate 4 runs and if you are back where you started, you don’t drift.\u00a0 Case 1 will hit the same place 4 times, case 2 will come back twice, case 3 will come back once, but all 3 will be at the starting position after 4 runs.<\/p>\n

Q2) Given n points equally distributed around the edge of a circle, and a ‘pseudo randomly’ generated subset k of those points which are marked, determine how many right angled triangles can be created using only the marked points. n is up to 1 million but k is limited to 100 thousand.\u00a0 Also the input is guaranteed not to result in an answer greater than 2^64.<\/strong><\/p>\n

A2) Seems kind of tough for a second question at first glance.\u00a0 First we need to identify how to create right triangles.\u00a0 If n is even, this is easy, possible pair of edges corresponds to a mirror pair, and either of those mirror pair will make a right triangle.\u00a0 If n is odd, no right triangles can be created… (A right angled triangle has its hypotenuse as a diameter of a circle, and 2 different circles can only have at most 2 crossing points, not 3.) However even with O(1) dictionary lookup and considering every pair of marked points to determine if either of the matching mirror locations is way too much.\u00a0 So we need a solution which comes from considering the points one at a time.\u00a0 The trick is in the logic we used to get rid of all the cases where n is odd.\u00a0 The hypotenuse must be a diameter, so from each marked point we can determine immediately the location across the diameter and verify that it is a marked point.\u00a0 If it is a marked point we then have a second trick, every single other marked point other than the 2 consumed will make a valid right triangle with the diameter.\u00a0 So for every marked point in one half of the circle, if there exists the matching point then add k-2 to the sum.\u00a0 Not so hard after all… (Although implementing the pseudo randomness itself had risks…)<\/p>\n

Q3) Given a n x m board and k varieties of pieces each with its own count, determine how many ways exist to layout the pieces such that every row and column has at most 1 variety. n and m have a maximum of 30 and k has a maximum of 10. Return result modulo 1 billion and 9.
\n<\/strong><\/p>\n

A3) Hmm, as usual Q3 seems beyond me. Even just trying to generate canonical arrangements which can then be boosted to the actual answer applying combinatorial multipliers, seems difficult.\u00a0 After thinking about it for a while I gave up.\u00a0\u00a0 Turns out canonical arrangement approach is no good, you need to boost as you go along.<\/p>\n

From a solution.\u00a0 Define dynamic program over number of ways to populate the board using i rows and j columns to contain the first l varieties.\u00a0 This is equal to the number of ways to populate the board with l-1 varieties in i-di rows and j-dj columns, times n-i-di choose di, times m-j-dj choose dj times the number of ways to arrange count of l in di rows and dj columns.\u00a0 That second arrangement can be done using dynamic programming up front, or memotized, since it will be repeated a lot.\u00a0 Firstly l has to fit into the area of di*dj, and must be greater than or equal to both di and dj in order for there to be an arrangement. I would have thought x*y choose c would have been the answer at this point but I would have been wrong, as it doesn’t consider the case where a row or column is left entirely empty. So we subtract off the number of ways to arrange c in to each possible scenario of less rows or columns, each multiplied by the number of ways to arrange the rows or columns into the full x and y size.<\/p>\n

Not as bad as I first thought, but still pretty tricky.<\/p>\n","protected":false},"excerpt":{"rendered":"

Q1) Given a sequence of step, turn left and turn right commands, which are repeated infinitely, determine whether you will stay in a constrained (but not specified) area, or drift off in to the distance.\u00a0 Maximum command sequence length is 50. A1) There are 4 scenarios.\u00a0 1. You come back to where you started. 2. … Continue reading TC SRM 473<\/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-220","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\/220","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=220"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/220\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=220"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=220"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=220"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}