So, looks like this was a tough round – only 1 person solving the 4th question, and they broke the large input on question 1, so no maximal scores.\u00a0 Advancement cut-off was solving the first 2 questions small\/large with at least 6 minutes to spare.\u00a0 T-shirt cut-off was Q2 small\/large with more than 40minutes to spare.\u00a0 Safe T-shirt was Q1 small\/large and Q2 small.<\/p>\n
Q1) Given that the cost to travel between any 2 points on a line in one direction is given by a quadratic formula which has a negative quadratic component in the distance between the points (hence average cost by distance is monotonically decreasing as distance increases) and a list of trips and the number of people completing them, determine how much the total cost can be reduced by maintaining the same number of exits\/entries at each stop, but changing where a person’s ticket starts\/stops the journey.<\/strong><\/p>\n A1) My question statement above is a bit more generic than the specific one in the comp – but I think they are equivalent.\u00a0 The first thing to identify that in any case of 2 trips that touch\/overlap the best result is to have one ticket travel the long way and one ticket travel the short way.\u00a0 This leads to the greedy approach – ignore the people and just watch the tickets.\u00a0 At each trip start location, new tickets arrive, at each trip exit location we remove the newest tickets, leaving the old ones.\u00a0 This leads to a natural implementation involving a stack – order all start\/end locations from first stop to last stop, such that starts are sorted before ends when start and end locations are coincident, then walk them in order, pushing onto the stack ticket start locations and counts, and at each end location pop the stack as much as required to satisfy the exit count – putting any remnants back on the stack if we get a partially fulfilled starting location.\u00a0 Sum up all the costs from entering\/exiting and compare to the expected cost. This is O(N) in the number of distinct trips, so it will easily perform in time for the large input which only had 1000 distinct trips.<\/p>\n The real challenge for the large input is the size of the result – the number of tickets in flight can get up to 10^12,\u00a0 and they can all exit at once, or all enter at once. (Problem statement does not rule out the 1000 trips actually being identical – just that each one has a maximum of 10^9 people).\u00a0 So you need to remember to use 64bit integers at this point already.\u00a0 But then the cost of individual trips can be ~10^18 itself, so calculating the total cost can overflow 64bit multiplication.\u00a0 So you either have to remember to apply modulus before and after the multiplication, or simply do all math using BigInteger and apply the modulus at the very end.\u00a0 If you take the modulus approach, you have to remember that when taking the difference of 2 modulus values (to calculate the value saved) the answer is always positive under modulus, but the % operator in many languages will give you the negative remainder when used on a negative result.\u00a0 As a bonus, the small input is so constrained that it can’t even hit the modulus at all, so you can’t get any confidence in your modulus code before tackling the large input, without doing some manual testing yourself.<\/p>\n Q2) Given 2^N competitors where each competitor can be ranked in a strict order where higher ranked players always beat lower ranked players and p prizes to be awarded, determine the lowest rank which is guaranteed to receive a prize and the lowest rank which could receive a prize.\u00a0 Players start in potentially any order, but after each of the N rounds they have a stable sort applied based on their Win\/Loss record for the tournament so far (lexically ordered comparison favouring early wins rather than number of wins).\u00a0 Prizes are then awarded to the top p entries in the final sort.<\/strong><\/p>\n A2) This is an interesting competition structure – in order to be in the top half you have to win your first round.\u00a0 Also of note that because there are 2^N competitors and N rounds and in each round everyone will always be playing against someone with the same win\/loss record – the final results are fully ordered by the win\/loss record, no reliance on the stable sort.\u00a0 Small input is up to 10 rounds, large input is up to 50.\u00a0 So 64bit integers are again important.<\/p>\n I did not find this problem very approachable for some reason, but after some thought I think the approach to take is to binary search on rank and ask the question, how high (or how low) can this rank go in the final result.\u00a0 Comparing the result of that question to the prize threshold you can decide whether to go higher or lower to find the minimum rank which could (or is guaranteed to) win a prize.\u00a0 So then the question becomes, for a given rank, what range of placings is possible.\u00a0 Highest\/lowest ranks have no options they are always stuck in their natural position.\u00a0 Second highest\/lowest ranks can go from their natural ranking to exactly one position past the middle in the direction away from their natural rank.\u00a0 But what about the rest?\u00a0 If we consider a given rank, at each round its ‘division’ (same win\/loss record) will consist of a certain number of ranks higher and a certain number of ranks lower.\u00a0 The actual value of these ranks is not relevant, just how many there are.\u00a0 If we are trying to win we can consider what the effect of optimal strategy will have on these 2 numbers, and vice versa for trying to lose.<\/p>\n So if we have x above and y below and are trying to determine how high a final placing we can get, what is the ideal strategy?\u00a0 I would suggest it is to maximise y at all stages.\u00a0 One of the lower ranked will play you, and lose, maximising how many of the y-1 remaining win involves getting them to pair off with each other as much as possible, as every time someone from x plays against someone from y, x is guaranteed to win.\u00a0 So new y = (y-1)\/2 (rounding down) and new x = (x+y+1)\/2 – 1 – new y.\u00a0 Eventually y=0 and you have to lose, and from then on you also can’t win.\u00a0 This sequence of wins\/losses will give you the maximum placing for a given rank.\u00a0 You can also reverse everything to get a sequence of losses\/wins to get the minimum placing for a given rank.\u00a0 Assuming these strategies are correct it is also fairly obvious that the maximum\/minimum placing never has any turning points with respect to changing starting rank, so the binary search approach I originally suggested is plausible (although due to the step-function nature some extra care might be needed). On the other hand, the fact that this strategy demonstrates that ‘ideal’ scenarios always consist of sequences of wins then losses, or vice versa (but no mixing) it should be possible to come up with a much more direct approach simply calculating the size of y backwards.\u00a0 (Consistently assuming that a round down was required in the forward version, or not, in order to get the range of values that will reach a specific ‘limit’ in the ideal scenario.)\u00a0 I think this direct approach can be performed in O(N) with a sufficiently smart implementation, as compared to O(N^2) of the binary search approach.<\/p>\n Q3) Given a table of lengths of the longest increasing sub-sequences ending at i and a table of the longest decreasing sub-sequences starting from i, determine the lexicographically smallest permutation of the numbers 1 to N, which satisfies both tables.<\/strong><\/p>\n A3) Inspecting the tables gives us a bunch of inequalities regarding elements in the final sequence, from there we just find the smallest permutation which satisfies the inequalities and presto we are done?\u00a0 Somehow I think it isn’t as simple as that sounds.\u00a0 But lets start anyway.\u00a0 If two consecutive elements of the first table are increasing, we know that the values are increasing at that point as well.\u00a0 If they are decreasing in the table, we know the values are decreasing, and if they are equal in the table we know the values are decreasing.\u00a0 Corresponding logic also applies for the longest decreasing sub-sequences.\u00a0 However we can learn more.\u00a0\u00a0 Each value in the first table is either 1 (indicating a new lowest value) or it is precisely 1 more than a previous number.\u00a0 The new value is then between that previous number and all intermediate numbers.\u00a0 However there might be multiple previous numbers that are exactly one less – it appears that maybe we can assume the least constrictive of those, which will be the closest one.<\/p>\n Is that enough constraints?\u00a0 I am not sure.\u00a0 The next question is, given these constraints how do we build the output?\u00a0 My guess is we build a directed graph and perform a kind of topological sort.\u00a0 Care must be taken to ensure that in the multiple ways the topological sort can be performed, we choose the one which gives the best lexicographical output.<\/p>\n Looking at a solution, I think that I have covered all the constraints, although it can be stated more simply.\u00a0 For each entry, walk backwards through the table, the first one you are equal to, you are less than that, the first one you are exactly one more than, you are larger than that. (And vice versa for the second table).\u00a0 When stated this way, you can more clearly see that the resultant graph is fully connected and so the way to populate the topological sort is clear, leaf pruning, where the leaf to be trimmed next is always the leaf which corresponds to the earliest position in the output.<\/p>\n Q4) Given a multi-player version of pong where the paddles are points and can pass by each other and each team has to rotate through its paddles (in order) to hit it back, determine how long the game goes for (and who wins, if it ever finishes).\u00a0 You are given the initial position and velocity of the ball, the size of each team, how fast each team can move its paddles, and the size of the game world.<\/strong><\/p>\n A4) Reading the description I thought, sure this question sounds reasonable.\u00a0 Then I saw the small\/large input constraints.\u00a0 Even the small inputs contain numbers that won’t fit in 32bit integers.\u00a0 Large input contains values which barely fit in 384bit numbers…<\/p>\n Small input does at least look feasible – each team has at most 1 million players, so as long as your code is fast, you can consider each player and think about bouncing cycles and reflection, identify the few scenarios to determine whether the paddle can make it in time between each turn it has to take – calculate the smallest failure out of the up to 2 million players and return.\u00a0 The large input however has 10^100 players per team.\u00a0 The only way this version is plausible is if you can consider ever player in a team all at once, identify the worst case within the team (maybe using a binary\/ternary search?).\u00a0 Given there was only one successful solution, I don’t feel too bad at leaving my discussion there.\u00a0 In practice the implementation will require a BigRational class (or scaling all positions by the ball and paddle velocities so they are all integers in seconds per unit, cementing the need for BigInteger even for the small input).<\/p>\n","protected":false},"excerpt":{"rendered":" So, looks like this was a tough round – only 1 person solving the 4th question, and they broke the large input on question 1, so no maximal scores.\u00a0 Advancement cut-off was solving the first 2 questions small\/large with at least 6 minutes to spare.\u00a0 T-shirt cut-off was Q2 small\/large with more than 40minutes to … Continue reading GCJ13 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-694","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\/694","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=694"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/694\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=694"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=694"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=694"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}