My first non-competing round of the season… will see how many of these I bother to write up – if previous years is anything to go by, not many!<\/p>\n
Q1) Given a set of tasks which each have a time to complete, and percentage chance of failure, determine the order which minimises the expected time to completion if failure of any task means you have to restart your order from scratch.<\/strong><\/p>\n A1) This was a sneaky question, not insanely difficult, but they set the restrictions on the small input that the time to complete of every task was identical.\u00a0 In that scenario the solution is trivial, you sort by most likely to fail to least likely to fail (using a stable sort, or secondarily sorting based on original index).<\/p>\n The large input isn’t much more complicated, the only question is what is your sort operator look like when the times of the tasks are not identical.\u00a0 Unfortunately my initial guess would have been length of task times the chance of failure, when the correct answer is length of time divided by chance of success. Fraction class works here, or you can define your sort operator as a.Time*(100-b.FailChance) < b.Time*(100-a.FailChance).\u00a0 Pretty sure I’ve seen this question somewhere before…<\/p>\n Q2) Given a hexagonally shaped hexagonal grid and a series of ‘moves’ which fill in hexagons, determine the first point in time that either 2 corners are connected, 3 edges (which don’t include the corners) are connected, or a ring is formed. (A ring is a connected loop of hexagons where there is at least 1 empty hexagon inside.)<\/strong><\/p>\n A2) The large input has a hex grid with side lengths of up to 3000, and 10k moves, so the implementation needs to be reasonably efficient.\u00a0 Having written LoopDeLoop, I’ve had opportunity to consider similar problems in the past, so I think I had a chance of solving this problem if I had of been in the round.\u00a0 We can solve the 3 sub-problems independently, but there will be a common theme.<\/p>\n Corners. if we use a union-find data structure and associate properties with each set representative (specifically the number of corners the set touches), we can do this in linear time. Each move is handled easily Each surrounding position is either empty or a member of a set.\u00a0 Gather the number of corners for the distinct sets, union them all together, add in the new position and set the number of corners equal to the total (adding 1 if the move is in a corner).\u00a0 If total exceeds 1 we are done.<\/p>\n Edges.\u00a0 Almost identical to the corners, only instead of summing, we use a 6bit number to represent the edges touched, and use bitwise or to combine them.\u00a0 And rather then checking total we do a pop-count.<\/p>\n Loops.\u00a0 Here is the tricky bit.\u00a0 Again we can use the union-find data structure, but this time rather than aiming to union things together and track status, we are looking to see if the current move has 2 neighbours which are already in the same set.\u00a0 There is also the possibility that the move doesn’t create a loop, but just fills in the edge of a ‘blob’.\u00a0 If precisely 2 of the neighbours are the same set, and they aren’t touching, we have definitely created a loop.\u00a0 If 3 of the neighbours are the same set and they aren’t ‘sequential’, we’ve created a loop.\u00a0 If 4, same applies.\u00a0 If 5 or more there isn’t anyway to not have them sequential (and specifically 6 can never happen since it is already a loop).\u00a0 Edge and corner placements don’t really change this logic, although you certainly can’t go all the way to 6.<\/p>\n Plenty of opportunity to screw up, but overall I think I had a better chance here than with the large input of the first question…<\/p>\n Q3) Given a delivery fee per delivery, and cost of types of food, and length of time until stale, how long can you eat delivered food given a certain amount of money.<\/strong><\/p>\n A3) For a given number of days to survive on a single delivery, the answer is fairly obvious.\u00a0 For each day take the cheapest food which would not be stale.<\/p>\n The problem comes in deciding how many days to go between deliveries.\u00a0 Obviously if a type of food exceeds the cost of the cheapest food plus delivery fee, that type of food will never be selected, but since the delivery fee is averaged over multiple days the crossover point could be lower.\u00a0 It wouldn’t be too hard to do an infinite money scenario maximum efficiency but for a finite amount of money the problem is trickier.<\/p>\n The large input is huge, 10^18 money and up to 10^18 stale time.\u00a0 But the number of food types is much smaller, only 200.\u00a0 I looked up some solutions, and the one which I think most matches where my thinking was heading is assuming that the solution consists of d day cycles or d-1 cycles to make up the total number of days achievable. Binary search to find the maximum number of days, and ternary search inside that to find the minimum cost to complete that many days.\u00a0 If minimum cost is below the total amount of money, binary search goes up, otherwise it goes down.<\/p>\n Q4) Given a sequence of characters, some of which can be substituted with numbers, determine the length of the shortest string which contains every possible length k consecutive subsequence of the original sequence or any of its substituted variations.<\/strong><\/p>\n A4) Large input has k up to 500, small input is only 2.\u00a0 Small input we can build the list of distinct pairs, including substitutions.\u00a0 Then you have to work out how short you can make the joining.\u00a0 For each distinct pair you have to have at least 1 character in the output string, but do you need 2?\u00a0 For each unique character in the input we can count how many pairs start with it, and how many end with it.\u00a0 The difference (if positive) is how many times you can’t reuse that character.\u00a0 Finally even if you could theoretically reuse everything, there is always the first character, so there has to be something which can’t be reused. (I read a solution because I wanted to finish writing this blog post before 1am… but I don’t think this is too hard to come up with…)<\/p>\n The large input, I have no clue!\u00a0 Unlike with the size 2 input, you can have multiple different length overlaps to save you characters.\u00a0 (Not to mention that 500 character sequence can have 2^500 versions using substitutions…) Only 1 person solved this during the competition, so I don’t feel to bad…\u00a0 Turns out he used a mincost\/maxflow, although I certainly am not going to read the pages of code to try and understand how mincost\/maxflow solves this problem…<\/p>\n","protected":false},"excerpt":{"rendered":" My first non-competing round of the season… will see how many of these I bother to write up – if previous years is anything to go by, not many! Q1) Given a set of tasks which each have a time to complete, and percentage chance of failure, determine the order which minimises the expected time … Continue reading GCJ12 R3<\/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-570","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\/570","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=570"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/570\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=570"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=570"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=570"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}