I got to see 2 am twice staying up for this round, since it was scheduled for the hour when DST ended…<\/p>\n
Positive scores advanced, only about 1000 people registered. \u00a0Only 17 people got all 3 questions out. \u00a0I think I was close on solving all 3, just ran out of time on the fiddly implementation for Q3, but given how many submissions for Q3 failed system tests, maybe I wasn’t as close as I thought…<\/p>\n
Q1) For a table tennis tournament with people with distinct skill levels where greater skill always wins and only one table at which everyone queues, and after n consecutive wins the winner joins the end of the queue after the loser. \u00a0Determine who wins\/loses in the Kth round.<\/strong><\/p>\n A1) K was only at most 1000, so this was a simple simulation, even if you don’t have a queue data structure handy it’ll trivially run in time. \u00a0Just need some care tracking how many wins the players have had and be sure to add the retiring winner to the queue after that rounds loser. \u00a0I guess maybe input sizes of 2 and 3 would also present a potential corner case to some implementations.<\/p>\n Q2) Determine the maximum sum of products of the longer 2 dimensions of rectangular prisms which are made from an original rectangular prism of integer dimensions A,B,C by slicing parallel to a face to create 2 rectangular prisms of integer dimensions, where the pieces have to have a minimum dimension of each S in order to count.<\/strong><\/p>\n A2) A,B,C could all be up to 100, and S could be 1, so the number of ways to break it down rules out brute force. \u00a0Instinct suggested a greedy solution was the way forward. \u00a0Options to consider are slicing in half, or slicing off a slice of size S. \u00a0Slicing in half gives you two smaller problems, but you can clearly see that you get less slices than slicing off S at a time if you repeatedly try to slice in half. \u00a0Once you decide to slice off S at a time, you could switch to dynamic programming – state space is at worst size 100^3, with 3 options to check from each state, that will easy run in time.<\/p>\n However I still liked this problem for greedy, so with a little bit of math, you can show that slicing from the smallest dimension is strictly better than slicing from a larger dimension. \u00a0But if the smallest dimension is less than 2*S, slicing on that dimension has no gain, and slicing in a the next longest\u00a0dimension is actually a win. \u00a0Again once the two smallest dimensions are less than 2*S, you slice the longest dimension instead. \u00a0So first loop summing the product of the longest two dimensions until you get the shortest to less than 2*S, then repeat for until the second shortest is also less than 2*S, then again for the final dimension, and then finally add the product of the two longest remaining dimensions.<\/p>\n Simple mistake that could be made here is that when you are slicing the second or third longest dimensions to get them down to less than 2*S, you may end up with your 3 dimensions changing sort orders. \u00a0If you don’t resort your array after each run of slicing, you might end up start summing the product of the shortest and longest sides, rather than the two longest sides. \u00a0I sorted every time I changed the value, just to be safe, sorting 3 values is cheap \ud83d\ude1b<\/p>\n Q3) Given a strictly convex polygon with the maximum and minimum y valued coordinates on the y axis, determine the volume of revolution around the y axis.<\/strong><\/p>\n A3) This question was quite unclear, since given the polygon in most cases crosses the y axis, a full 360 degree rotation will cause the shape to sweep over itself. \u00a0So I did for a moment wonder if they meant the volume of 180 degree rotation – but the first example created a full cylinder out of a square with one edge on the y axis. \u00a0So I presume that the answer is the union volume from the 360 degree sweep. \u00a0I think I might have seen an answer which calculated volume of each half, doubled and added together and subtracted the intersection volume – so I think I was right about that.<\/p>\n So the final shape will be a stack of truncated cones, and the formula for volume of a truncated code is pretty simple. \u00a0The trick becomes determining the coordinates where each truncated code outside edge starts and stops. \u00a0Since its a union shape we’re trying to determine the volume of, take each segment on the left of the y-axis and reflect it to the right, and then we need to determine the outside edge of the combined set of segments. \u00a0Walking the segments in pairs advancing the segment which ends first, there are 3 possibilities for the overlap y range of the two segments. \u00a0Either one or the other is completely to the left or right of the other, or they could cross. \u00a0Turn each segment in to a line equation, allows the substitution of the y range min and max to check the maximum x-coordinates for the top and bottom of the range, if they belong to different segments do a segment intersection calculation to find the cross point. \u00a0Then you get 2 truncated cones instead of one by adding the cross point in between the 2 calculated maximum x coordinates for the start and end of the range..<\/p>\n Corner case – horizontal segments. \u00a0There can be up to 2 horizontal segments which are at the top and bottom since its convex. \u00a0These two segments can be ignored, and should be since otherwise you can have both horizontal and vertical segments which makes line equations difficult (without them you can construct the line equations as x = ay+b, otherwise vertical lines are annoying), and you also have segment overlaps with 0 extent in y axis which is confusing.<\/p>\n <\/p>\n","protected":false},"excerpt":{"rendered":" I got to see 2 am twice staying up for this round, since it was scheduled for the hour when DST ended… Positive scores advanced, only about 1000 people registered. \u00a0Only 17 people got all 3 questions out. \u00a0I think I was close on solving all 3, just ran out of time on the fiddly … Continue reading TCO17 R1A<\/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-853","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\/853","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=853"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/853\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=853"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=853"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=853"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}