The all important t-shirt round, top 500 advance but 1000 t-shirts were on offer.\u00a0 Four problems for round 2, in the end advancing meant solving all the small inputs and the easiest large input, or one less small in a very fast time.\u00a0 Even with a slow time that was enough to get the t-shirt, 2 small and a large was okay if you were fast, or the second small was for the hardest problem.\u00a0 I think I stood a decent chance of advancing if I had of been competing this year, definitely would have gotten the t-shirt…<\/p>\n
Q1) Given a 2D grid where some cells propel you in a direction, what is the minimum number of cell with direction that need to be changed to ensure that regardless of starting location, you never fall off the edge?\u00a0 (Note its not always possible to solve, so return ‘impossible’ if there is no solution.)<\/strong><\/p>\n A1) I didn’t immediately get this problem, but when I looked at it again I realized it was trivial.\u00a0 Seems the contestants agreed, with very high success ratio and high solving rate.<\/p>\n In the end it boils down to the question, why would you fall off the edge at all?\u00a0 Because a cell is pointing there with nothing else in the way.\u00a0 So for each such cell, just point it at another cell with a direction.\u00a0 If you can’t then the problem is impossible and you should return as such.\u00a0 Otherwise you are done, just count how many cells you had to change.\u00a0 The run time of the simple brute force is obviously no more than O(WH*max(W, H)) which given the constraints is trivial.\u00a0 A tighter bound is actually O(WH) every cell can only be traversed at most 5 times, once to find the cells with direction, and then 4 times from being reached from each direction by other cells. So even if the problem had of allowed much larger grids, it would still have performed in time.<\/p>\n Q2) Determine the minimal time to fill a container of volume V to temperature X, given a bunch of sources of flow rate F_i and temperature T_i.<\/strong><\/p>\n A2)\u00a0 The small input here has only 2 flow sources, and the problem gives the formula for mixing temperatures.\u00a0 Solve simple simultaneous equations in 2 variables and you are done.\u00a0 The inputs are given to 4 decimal places, and the answer is 1 part in 10^6 accuracy, so doubles sound like they would be fine here.\u00a0 But this isn’t quite like other such floating point problems.\u00a0 This one has the ‘can’t be done’ answer, if both temperatures are the same side of the actual temperature.\u00a0 So you need to be sure that you don’t introduce a numerical error which means that in the case where one of the input temperatures is equal to the desired temperature, you incorrectly return impossible.\u00a0 One solution is to ignore the fact that the question specifies things as 4dp, and just multiply everything by 10000.\u00a0 These factors of 10000 cancel out in determining the time, so you can switch to mostly integer arithmetic, just converting back to floating point for the final division.\u00a0\u00a0 You have to be careful with overflows though.<\/p>\n The large input is too large to brute force, which suggests a greedy approach.\u00a0 My best guess was to order them by temperature.\u00a0 I took a look at some passing solutions and one of them did exactly this.\u00a0 Order by temperature, then slowly prune either the hottest or coldest until you switch from the output being too hot to being too cold or vice versa.\u00a0 Then its like solving the small input, just with one high flow mixed temperature of everything, and the last temperature you removed.\u00a0 I found it interesting that they didn’t bother to solve the simultaneous equations though, they just binary searched for the flow rate that produced the right output temperature. (Since you can simulate lower flow rates just be having that tap turned off for part of the time.)<\/p>\n Another solution I saw instead binary searched over ‘can it be solved by time x’.\u00a0 They also sorted by temperature, but instead of pruning backwards one by one, they built outwards from the middle.\u00a0 Given the time t, they had actual volumes rather than rates, and could determine if each volume from a given tap could be mixed with some from another to create the right temperature.\u00a0 As they used up each tap, they moved to the next one out.\u00a0 Eventually all of the colder than target taps or all of the hotter than target taps get used up, and the the rest is discarded.\u00a0 If the total used volume is greater than or equal to target, success and binary search a smaller time, otherwise a longer time is needed.<\/p>\n Q3) Given a set of sentences which are in ‘English’ or ‘French’ determine the minimum number of words that must be in common between English and French.\u00a0 The first two sentences are labelled, the rest are unknown. <\/strong><\/p>\n A3) The small input looks like a trivial brute force, but unless you start by replacing strings with numbers, the hash\/equality cost is quite high and will probably stop your code from running in time.\u00a0 So relabel everything to numbers.\u00a0\u00a0 Given the constraints there will be no more than a few hundred distinct words which you can number consecutively 0 to N, so rather than hash lookups you can just used indexed arrays.\u00a0 Enumerate the 2^18 scenarios adding to the counts of times you’ve seen each ‘word’ against either English or French arrays.\u00a0 Then sweep them both looking for anything which has both positive for the same index.<\/p>\n The large input however had me stumped.\u00a0 My best guess was some kind of maximal matching or flow graph, but I couldn’t see how to construct it.\u00a0 Looking at other solutions it appears max flow graph was the answer.<\/p>\n Each sentence has two nodes, each distinct word has two nodes.\u00a0 Unlimited flow from the first to second nodes for each sentence, but only unit flow between the first and second nodes for each distinct word.\u00a0 Then connect the second node of each sentence to the first node of each distinct word in the sentence, and vice versa – both with unlimited flow.\u00a0 The answer is then the maximum flow from the first node of the first sentence, to the second node of the second sentence.<\/p>\n I don’t understand why this works though, maximum flow for a minimal answer.\u00a0 Even the meaning of each node doesn’t seem obvious.\u00a0 The two nodes per sentence seems redundant since there is only unlimited flows involved, probably just a convenience rather than having source and sink nodes for the first two sentences especially.\u00a0 A flow between the two nodes for a word means they must be both English and French.<\/p>\n Looking at the case of just the input two sentences, every word in common allows a flow which goes first node of first sentence, second node of first sentence, first node of word, second node of word, first node of second sentence, second node of second sentence.\u00a0 Words not in common don’t allow flows because they just form a cycle with their parent sentence.\u00a0 Next simplest example, one word third sentence which is in common with English (or French) but not both.\u00a0 It gets ignored.\u00a0 Good.\u00a0 Three word sentence with two in common with English and one in common with French.\u00a0 One more flow, from first sentence through the fact its in common with English, to third sentence, then over to French by the one in common with that.\u00a0 The second potential flow gets stuck at the 3rd sentence.\u00a0 It all works, but the why still escapes me.<\/p>\n <\/p>\n Q4) Given a cylinder labelled with a rectangular grid of positive numbers such that each number has exactly that many neighbours of the same value determine how many such labelling exists, modulo 1 billion and 7.\u00a0 Two labellings are considered distinct only if they aren’t rotations of each other.<\/strong><\/p>\n A4) Brute force on the small input here seems scary, but back tracking algorithm stands a good chance of running in time, because the problem is so restrictive.\u00a0 Some smarts might still be needed.\u00a0 Pure brute force is 3^36, which is obviously too slow. (4 and higher can’t be on the board, 5+ trivially, 4 because it implies an infinite board.)<\/p>\n Looking more deeply unlocks this problem.\u00a0 There are limited number of ‘units’ which a solution can be made up of.\u00a0 A row of 2’s where nothing above or below is a 2.\u00a0 2 row’s of 3 where nothing above or below is a 3.\u00a0 These 2 are the obvious ones given in the question itself.\u00a0 The trick is to come to understand there are only 3 more building blocks.\u00a0 They all involve just 1’s and 2’s.<\/p>\n Each can only be placed next to itself in a row, and each can be rotated a number of places equal to its width, but again rotated versions can only be next to rotated versions.<\/p>\n The problem then becomes a DP over rows.\u00a0 2 rows of 3s separating one of 4 scenarios of 2’s.\u00a0 One which uses one row, 2 which use 2 rows, but have 3 or 6 rotation variants, one which uses 3 rows with 4 variants.\u00a0 The trick is to make sure you don’t over count.\u00a0 Each variant is like a rotation, so if you only use one pair of rows of mixed 1 and 2, you have actually over counted by exactly 3 or 6 times.\u00a0 One solution is to assume that you are always going to over count by a factor of 12, so divide the result by a factor of 12.\u00a0 Then at the deepest level of your recursion, force over counting to be 12.\u00a0 If you’ve not used any 1 or 2 mixed, return 12, if you’ve used only the first kind, return 4, only the second kind (or second and first), return 2, only the 3rd kind return 3, both the 1st and 3rd or 2nd and 3rd (or all 3) return 1.\u00a0 The DP is then on rows and 4 bools representing whether you’ve ever used each of the 3 types of 1,2 mixed and whether the last set of rows were all 3’s or not.<\/p>\n","protected":false},"excerpt":{"rendered":" The all important t-shirt round, top 500 advance but 1000 t-shirts were on offer.\u00a0 Four problems for round 2, in the end advancing meant solving all the small inputs and the easiest large input, or one less small in a very fast time.\u00a0 Even with a slow time that was enough to get the t-shirt, … Continue reading GCJ15 R2<\/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-798","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\/798","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=798"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/798\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=798"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=798"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=798"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}122\n122\n\n112222\n222112\n\n1222\n1212\n2212<\/pre>\n