As usual round 2 is pretty competitive, to advance required all 4 small inputs and the 2 easiest large problems, and even then time was a minor factor…\u00a0 T-shirt was the 2 easiest large problems and one of the remaining small inputs, the harder one to not have to worry about time.<\/p>\n
Q1) Given a set of containers of equal size and a list of item sizes and a maximum of 2 items per container, determine the minimum number of containers needed to pack all the items.<\/strong><\/p>\n A1) This can be solved by a greedy approach.\u00a0 Take the largest item, if there is another item which fits in the container with it, take it.\u00a0 If you want you can choose to take the largest of such other possible items for the ‘most greedy’ approach.\u00a0 But I am pretty sure you can just take the smallest and it makes no difference.\u00a0 This later scenario makes the problem trivial, as you just walk inwards from the ends of a sorted version of the list of items, advancing when you can take them to count the items.\u00a0 This works well for the large input since it is an O(N) approach (after the O(N log N) of sorting).\u00a0 But even with 10^4 items the simple O(N^2) implementation of the ‘most greedy’ approach will run in time with a decent compiler.\u00a0 Or it could be implemented with a sorted dictionary (specifically one with a ‘find value or prior’ method) for O(N log N), but in this case you have to be careful how you handle multiple items of the same size, since they will have the same key.<\/p>\n Q2) Determine the minimum number of neighbour swaps to make a sequence be sorted such that it has a single maximum, that is it is either all descending\/ascending or ascending followed by descending.<\/strong><\/p>\n A2) I had to go remind myself about minimum neighbour swaps to work out how to do this question.\u00a0 Even the small input looked tough, brute forcing all possible swap locations and orderings was way way too slow.<\/p>\n So this question boils down to two parts.\u00a0 Minimum neighbour swaps to make a specific permutation, and deciding which permutation takes the minimum neighbour swaps to satisfy the criteria.<\/p>\n Minimum neighbour swaps to make a permutation is pretty straight forward.\u00a0 But it requires knowing things which aren’t exactly obvious.\u00a0 For instance the bubble sort is optimal in the number of swaps, so for the small input you can just use the bubble sort to sort the items, relabelled by the desired index to move them to.\u00a0 For large input you need to know that a merge sort can be used to count the number of swaps a bubble sort would have done, but with batches rather than 1 by 1, allowing it to run in O(N log N) even though the number of swaps is O(N^2).\u00a0 Some Google searching found me the algorithm, which is not that complicated.\u00a0 Every time an item in the merge is taken from the top half instead of the bottom half, you add the distance it would have had to move assuming the halves were joined in sequence rather than being merged into a destination array.<\/p>\n Deciding the permutation had me stumped for a while.\u00a0 Obviously the largest value in the input is the pivot point, but which elements should be on its left, and which should be on the right?\u00a0 In hindsight the small input brute force is obvious here, just try every combination of values other than the largest being assigned left, or right.\u00a0 Once they are labelled, sort the lefts ascending, and the rights descending and that determines the desired permutation to calculate the minimum swaps for.\u00a0 The large input on the other hand is I think far from obvious.\u00a0 I think it can be done just by using a hill climb.\u00a0 For each value see if the minimum swaps decreases by switching sides, repeat until you can’t make it any better.\u00a0 I can’t prove this however…\u00a0 This hill climb could be O(N^3 log N) (which is quite slow for N=1000) if switching sides made things better to switch back for others, but I think it is much closer to O(N^2 log N) in practice.<\/p>\n Looking at a solution on the other hand shows another option which is much simpler, and is intuitive, but not obvious.\u00a0 The idea seems to be that you select the smallest value in the item and then swap it to the closest end.\u00a0\u00a0 Lock that one in, and repeat the process.\u00a0 Can be made to run in O(N log N) although given the large input is still only at most 1000 items, the simpler O(N^2) option is fast enough.<\/p>\n Q3) Given a grid of squares determine the maximum flow from the bottom edge to the top edge, if each square has a capacity a flow limit of 1 and can flow through its edges, but some cells have 0 flow capacity.\u00a0 All bottom edges are an input flow of 1, all top edges are accumulated for the maximum flow.<\/strong><\/p>\n A3)\u00a0 So if you have a maximum flow implementation at the ready, the small input here is probably not too crazy.\u00a0 However with 100000 nodes in the graph and each node having 4 connections, and a potential maximum flow of 100 it will need to be the Ford Fulkerson algorithm with its O(E max(f)) running time as anything O(VE) or worse will run way way way too slow.<\/p>\n The large input however has a grid height of 10^8 which ensures the O(W^2 * H) Ford Fulkerson approach is implausible.\u00a0 However there is a limit of 1000 blocked out areas, which means there is only at most 2000 different interesting positions in the height.\u00a0 However even O(W^2 * count_interesting(H)) is pretty slow and determining how the flow graph looks even for that is tricky.\u00a0 I am not clear on how horizontal elements can be safely coalesced to give edges with maximum flow greater than 1, because there is a limit to how fast a given flow can migrate left or right, and so you would have to ensure that everything that was coalesced can make it to the next area in time rather than just blindly coalescing everything which is horizontally connected.<\/p>\n To discuss the bit I think which is interesting (but probably not sufficient to solve) is how flows can migrate left or right across a distance.\u00a0 If there are 4 adjacent flows entering an ‘open’ area, one of them can migrate to anywhere after one cell down as it can flow across all the empty spaces.\u00a0 Then after the second cell down another can join it, then 3rd can move after 3 and so on.\u00a0 These would probably be represented with cross links in the graph with a specific capacity dependent on the height difference between the current position and the next.\u00a0 If there are 2 ‘streams’ coming down to an open area these links would be set up so that flow can’t go both directions.<\/p>\n Q4) Determine the worst case for the number elements in the tries created by splitting the input works in to k groups, then determine how many ways this worst case can be performed.<\/strong><\/p>\n A4)\u00a0 Small input is pretty easy here, only 4 groups and 8 items,\u00a0 gives only 2^16 base scenarios to consider in a pure brute force.\u00a0 From there eliminate the ones where any group has no elements, the build the tries and sum the counts and if worse reset counter to 1, if equal increment counter, otherwise ignore.<\/p>\n The first part of this question is actually quite easy, just count how many times each substring exists in each word, choose the smaller of that and the number of servers, sum all those values and that is the worst case.\u00a0 Basically this just states that any given substring can always be distributed amongst the servers to potentially be counted a number of times equal to the number of servers.<\/p>\n The number of ways that it can be done is a much more difficult problem.\u00a0 How many ways a given substring could be distributed amongst the servers such that it is spread out as much as possible is a fairly simple combinatorics question, but you can’t just multiply these together because they have correlations because the shorter substrings have to match the servers of their corresponding longer servers.<\/p>\n Trying to reverse engineer the logic from reading a solution is beyond me right now, so I think I will leave this question for another day…<\/p>\n","protected":false},"excerpt":{"rendered":" As usual round 2 is pretty competitive, to advance required all 4 small inputs and the 2 easiest large problems, and even then time was a minor factor…\u00a0 T-shirt was the 2 easiest large problems and one of the remaining small inputs, the harder one to not have to worry about time. Q1) Given a … Continue reading GCJ14 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-762","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\/762","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=762"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/762\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=762"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=762"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=762"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}