So this round was blitz’d – cut-off was top 1000, and all of them finished all of the problems. \u00a0I’m not confident I could have solved them all in time, the key observation for the second problem doesn’t seem something I would have caught.<\/p>\n
Contest analysis was posted almost immediately again, so my analysis is kind of redundant, but I’ll do it anyway!<\/p>\n
Q1) Given a sequence of characters where for each you can choose to put it at the start or end of a word you are building, determine the lexicographically largest word you can make.<\/strong><\/p>\n A1) So this is a greedy problem. At every point whichever action makes local sense, is also the path to the global maximum. \u00a0The contest analysis shows how to solve the large in 4 lines of python, I think it can be done in one (rather long) line of c# using the Aggregate\u00a0function for enumerables.<\/p>\n However both of these solutions are quadratic in the size of the input (which is fine given a maximum input size of 1000). \u00a0Its possible to do this problem in linear time using a dequeue. \u00a0This is because the larger of adding the new letter as a prefix or postfix is the same as comparing the new letter to the first letter and putting it at the back if the new letter is smaller. \u00a0This reduction of the comparison to just the first character works because the generated word will\u00a0always go down after any first sequence of repeated letters, never up, so extending the sequence of repetition is always an improvement. \u00a0Pretty sure this\u00a0property can pretty easily be proved, but I’ve not done it formally.<\/p>\n Q2) Given 2N-1 sequences of length N which are all strictly ascending and each correspond distinctly to one of the rows or columns of NxN grid where every row and column is strictly ascending, return the missing row or column values in ascending order.<\/strong><\/p>\n A2) Brute force for the small input isn’t exactly trivial to write but it is at least obvious. \u00a0Contest analysis tells me that the trick here for the large input is that every missing value will have an odd frequency due to there only being one missing row\/column. \u00a0This leads to a very straightforward solution – which would be one (very long) line of C# if there was a method to Sort and return an enumerable… \u00a0I think I might add a ToSortedArray extension method to TMD.Algo. \u00a0This is O(N^2) since the data to be sorted is length N.<\/p>\n However since I feel that trick is too hard to spot reliably, I’ll now present an alternative implementation which doesn’t rely on it, but is still O(N^2). \u00a0Its just a bit more complicated and hence not one I’m confident I could design in the time available.<\/p>\n So this other method also has a trick, but one I think is more obvious. \u00a0The smallest value in the grid is in the top left corner. \u00a0Therefore the smallest value in the first spot of any of the inputs, is the value of the top left corner. \u00a0Further more any sequence which starts with that value, must be either the top row or the left most column. \u00a0Therefore there will be at most 2 of these. \u00a0This identification takes O(N) time, since we only look at the first value of each and find min, then a second pass to tag those that are min. \u00a0The trick is that now that we’ve identified the input data which could potentially be in the first row or column, the problem has been reduced. \u00a0Ignoring the data we’ve already tagged, the smallest value in the second spot of any of the rest of the inputs is the value from the second position of the diagonal. \u00a0Again there are at most two which match and we can tag those as being the second row or column. \u00a0We can repeat this until we’ve now identified the entire diagonal of the final grid and at most two options for any row or column pair passing through each position in the diagonal.<\/p>\n So far we’ve spent O(N^2) time, but we’re not yet done, we’ve only identified\u00a0a fraction of the full grid. \u00a0Luckily we’re actually almost done. \u00a0Chose one of the elements of the diagonal that has 2 input data’s associated with it. \u00a0Since the grid is currently empty you can place these in any orientation without loss of generality, so make one the row and the other the column and place them into the grid. \u00a0Now consider the two arrays you just placed, for any indexes where they aren’t identical, the corresponding row\/column pair which crosses perpendicular\u00a0through those indexes is an interesting place to think about. \u00a0Since the values are not the same, if you have two options for that row\/column pair, only one can be the row, and the other must be the column. \u00a0Thus they can be placed. \u00a0And so on for every time you place a row\/column pair if any of the elements are different you have another row\/column pair that can be placed if its not already placed. \u00a0So use a queue and a mask to know what you’ve put in the queue already, and this cycle of placing and finding new things to place is linear in the number of values in the arrays placed so far. \u00a0The one thing is that if there isn’t anything different, or if the difference is for the row\/column where one is missing, your queue will flush, but you won’t be finished yet.<\/p>\n Here is the not quite so obviously true bit, but one I’m confident is fine. \u00a0Since you’ve gotten to a point where there is no difference in the rows or column pairs that are yet to be placed, you can simply choose arbitrarily again, just like you did for the first pair. \u00a0The known cells are guaranteed to match, and the unknown cells are guaranteed not to be influenced by anything you’ve already placed before. \u00a0Thus we can just throw a new index\u00a0on to the queue and keep going.<\/p>\n Finally there is just the row\/column pair passing through the diagonal where only one data set was tagged. \u00a0Check if the one data set matches the column, if so return the row, otherwise return the column. \u00a0Although before you return, do make sure you’ve set the diagonal value itself, it won’t have been populated yet unless you populated it at the very beginning while the diagonal values were being determined.<\/p>\n Every step along the way to fill in the values is linear in the number of values filled in, so O(N^2) just like the much simpler solution proposed by the contest analysis.<\/p>\n Q3) Given a directed graph where every\u00a0node has exactly\u00a0one outgoing edge, determine the maximum number of nodes\u00a0that can be placed in a circle such that every element in the circle is directly connected to one of its neighbouring elements.<\/strong><\/p>\n A3) Despite\u00a0this problem being worth the most number of points – I found it to be conceptually the easiest. \u00a0Yes even easier than the first problem. \u00a0That being said the implementation is a pain, even worse than my extra complicated option for Q2 large input size.<\/p>\n So the problem has two pretty straight forward cases.<\/p>\n Option 1, the circle is fully connected. \u00a0Since each node has exactly one out going edge, this implies a cycle of some length. \u00a0So step one is to find the largest cycle. \u00a0That’s one possible answer. \u00a0Having found all cycles we’ll throw away them or any nodes that are connected to them if the cycle length is greater than 2.<\/p>\n All of the remaining nodes form pairs of trees pointing to a cycle of length 2. \u00a0Option 2 is to take the longest path to each side of that cycle, sum those together, then sum across all such connected components, this is the alternative answer. \u00a0This represents taking all the longest fully connected lines and placing them into a circle. Return the largest of Option 1 and Option 2.<\/p>\n Depth first search will identify all the connected components in linear time, it will also identify the longest cycle in linear time. \u00a0A second depth first search on each connected component with cycle length of 2 will find the longest path to the cycle in linear time too if you keep track of path depth and destination to avoid recalculation when your depth first search finds somewhere you’ve searched before when starting from a new possible deepest node. \u00a0Or reverse the direction of the arrows and just do a standard height of tree calculation.<\/p>\n","protected":false},"excerpt":{"rendered":" So this round was blitz’d – cut-off was top 1000, and all of them finished all of the problems. \u00a0I’m not confident I could have solved them all in time, the key observation for the second problem doesn’t seem something I would have caught. Contest analysis was posted almost immediately again, so my analysis is … Continue reading GCJ16 Round 1A<\/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-823","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\/823","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=823"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/823\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=823"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=823"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=823"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}