So round 3 was last weekend, and no exceptional circumstances were declared so just the top 500 went through (which didn’t include me).<\/p>\n
With only the top 25 going onwards, the questions were always going to be tough, and for the 4 questions, getting all the small inputs and 2 of the large inputs in a decent time was sufficient to get through.<\/p>\n
Only 370 people out of the top 500 got a positive score, and having an initial look through the questions I doubt I would have done very well – maybe a couple of small inputs out.\u00a0 One of the 2 remaining Australians got 66th place, quite impressive.<\/p>\n
On to the questions I guess, although I’m going to have to refer to the post contest analysis this time for sure!<\/p>\n
Q1) Given a sequence of numbers which are at most D digits in size, determine whether the sequence is predictable if it is governed by S(n) = A*S(n-1)+B mod P and if so return the next number.\u00a0 P is prime and less than 10^D, A and B are non-negative.<\/p>\n
A1) The small input D was at most 4, meaning that a brute force on P and A, solving for B, verifying the rest of the numbers fit, and determining whether the set of next numbers was unique, is easily done.\u00a0 That would have been easy.\u00a0 The large input however D is at most 6, making a brute force of P and A impossible.\u00a0 What we need to do is consider each P and the set of numbers to determine both A and B simultaneously.\u00a0 If we have 3 numbers, we have 2 simultaneous linear equations, Y=A*X+B mod P and Z=A*Y+B mod P (if we don’t have 3 numbers, the sequence is not predictable… for every A there exists a B which gives the result).\u00a0 If we subtract these equations we get Y-Z = A*(X-Y) mod P.\u00a0 and so long as X-Y is non-zero since P is prime, this equation has a unique solution which we can solve using extended GCD (which is in TMD.Algo).\u00a0 This still leaves a few special cases.\u00a0 Specifically the X=Y case.\u00a0 If X=Y then Y will also equal Z, due to symmetry, regardless of A and B and P.\u00a0 So any case of repeated numbers is predictable. This includes the 2 number case, despite what I said just before…<\/p>\n
Looking at the contest analysis seems I was on the money here. So, worst case I would have come 250th… lets see if I can do better…<\/p>\n
Q2) Given up to 100 unique integer lengths of fencing, determine the minimum number of fencing pieces required to create a fence with a length of exactly L.\u00a0 L is between 10^10 and 10^18.<\/p>\n
A2) For the small input the maximum length of each piece of fencing was 100.\u00a0 For the large that jumped to 100000.\u00a0 I think that a key point to this question would have to be that L has a very large minimum value.\u00a0\u00a0 For the small input I would posit that it can be solved using dynamic programming on the lengths of fence to create lengths less than 10000, then for each of positions up to 10k prior to the target L using only the largest piece, check if there exists a way to reach L using the DP table, and find the minimum amongst those options.\u00a0 When the fence size jumps to 100k, my approach becomes infeasible, because the DP needs to go to 100k squared.\u00a0 Going to have to check the solutions for this one.<\/p>\n
Okay, so I would probably not have gotten the large out, although the intuitive leap does appear within my level.\u00a0 Take the largest board, use it until we get just short of L (or exactly L).\u00a0 Then we need to determine how to make the remainder using smaller fences, or to make the remainder + largest fence, or +2 largest fence…\u00a0 We can do this by creating a graph, starting with nodes 0 to largest fence-1, and adding edges as follows.\u00a0 For each fence length less than max, add an edge from each node to node + length of weight 1 if node+ length < max or to node + length -max of weight 0 otherwise.\u00a0 Then given this potentially 100k node graph with, maybe 10million edges, find shortest path from 0 to remainder (This can be done in O(E) time).\u00a0 The length of that shortest path + number of max length boards to reach 0 is the answer.\u00a0 This only works because the shortest path will never have more than 100k weight 0 edges, and L is greater than 100k squared.<\/p>\n
Based on my reading of the answer, I believe my small input answer is correct, so that would bring me to 21points or 187th place.<\/p>\n
Q3) Given up to 200 locations at integer coordinates on a (very long) line each containing 1 or more items, you want to move them so that there is at most 1 at any spot.\u00a0 However your only option for moving them is if there are 2 or more on a spot you can move 1 to the left and 1 to the right.<\/p>\n
A3) Small input is up to 200 items, large input is up to 100k items.\u00a0 Even the small input seems tricky here… would seem to need some kind of strategy.\u00a0 Thinking about each move, it doesn’t change the centre of mass, so if we can find the centre of mass, the number of moves is minimally limited to those which spread them to being every spot filled with 1 about that centre of mass. That however may not be possible.\u00a0 Movements at the centre of mass are more useful than other movements since they are the only ones which actually separate things.\u00a0 The problem may also be separable into sub problems which don’t interact.\u00a0 In that case the centre of mass of each sub problem seems important.\u00a0 Small input I guess can be done via simulation of a strategy of centre of mass first or maybe largest first.\u00a0 I probably would have just tried one to see if it solved it, since you get answers for the small input immediately.\u00a0 Large input however requires better than straight simulation…\u00a0 Time to check the answers again…<\/p>\n
Well, turns out strategy isn’t needed for the small input, so I would have solved it ‘by accident’ – the actual series of moves is irrelevant, the final configuration is always the same and takes the same number of moves to get to regardless of strategy.\u00a0 Apparently this is a ‘famous theorem’ which probably means there are a few thousand people in the world who know it \ud83d\ude1b\u00a0 With this observation (and one other leap I would have been unlikely to get) the problem becomes quite simple.\u00a0 Simply construct the final answer and from there determine how many moves were required to get to it.\u00a0 Constructing the final answer can be easily done by simply building up the input.\u00a0 Adding each stack one item at a time, it either goes into an empty spot, or it causes the current end stack to split in 2.\u00a0 If you keep a stack of segments, the possible scenarios are, top 2 segments join, top segment splits or top segment splits and the bottom part joins with the one below it.\u00a0 Each operation is therefore O(1), giving an O(n) simulation to get the final position.\u00a0 Now the trick to get the number of moves is to take the sum of squares of the original positions and compare them to the sum of squares of the final positions.\u00a0 What will be found is a difference which when divided by 2 is the number of moves. This can be proven by considering how the sum of squares changes with each move.\u00a0 I suspect that if I had of known the theorem I would have tried to count the number of moves while simulating building up the stack.\u00a0 Each addition adds a number of moves related to the lengths of the splits it causes in a segment. Doubt I would have solved that in a competitive scenario anyway…<\/p>\n
I’m willing to give myself the small input though, bringing me to 27 points and 158th in my imaginary competition where I hadn’t flunked in the previous round.<\/p>\n
Q4) How many ways can you add 1 or more different numbers to give k, subject to a rather complex restriction…\u00a0 The restriction is, if the numbers are written in base B, the dth digit (counting from the right) of each number will be unique across all the numbers. Different orderings of the same numbers all count as the same way.<\/p>\n
A4) This question strikes me as pure evil, but interestingly enough slightly more people got out the large input for this than for the previous question…\u00a0 The small input limits B to be binary to decimal and k to be no more than 100.\u00a0 The large input however raises B to being anything up to base 70 and k to be up to 10^18…\u00a0 I think the key to do even just the small input is to realise that we can reorganise the digits freely between numbers, without changing the sum.\u00a0 But even with that it seems a bit tricky, dp over sums s less than k, with the number for the largest digit rearrangement being n, also less than k.\u00a0\u00a0 Then we need to work out how to multiply the total to get the actual answer.\u00a0 I think we may need to break the dp down into number of sums of n numbers to get to s, since I think the reordering count depends on that.\u00a0 However the fact that 0’s on the front don’t need to be distinct is a problem.\u00a0 At this point I give up and look at the solutions.\u00a0 Its not like I would have had any time left to solve this question in the competition anyway…<\/p>\n
Apparently I was complicating things too much – the small input can be done by simple brute force, the number of partitions of 100 with distinct integers is only a few hundred thousand, you can just generate them all.<\/p>\n
However I was starting to get on the right track for the large input.\u00a0 It is a dynamic programming problem, and the order of digits is not relevant for each column, but the needed approach is to build up one digit at a time, and using a nested DP to count the number of reorderings for each column.\u00a0 So you need to keep track of the carry, and how many of the numbers are finished and whether there is a 0.\u00a0 The zero allows for the termination of a number, but I am not sure why just the fact of a 0 rather than the number of 0’s is needed to be known.\u00a0 It almost makes sense, but I would need to implement it to be sure.<\/p>\n
Anyway 0 points for me here so I’m stuck with my theoretical 158th place.<\/p>\n
158th would have been close to my best ever placing, which was 115th in the first GCJ when it was still run by top coder… (and 100 people were going to be flown to the US) and the depth of field has definitely increased since back then… (In a super imaginary world where I had made the intuitive leap for Q2 large input, I would have gotten 51st… ahh I can dream :P)<\/p>\n","protected":false},"excerpt":{"rendered":"
So round 3 was last weekend, and no exceptional circumstances were declared so just the top 500 went through (which didn’t include me). With only the top 25 going onwards, the questions were always going to be tough, and for the 4 questions, getting all the small inputs and 2 of the large inputs in … Continue reading GCJ10 Round 3<\/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,6],"tags":[],"class_list":["post-183","post","type-post","status-publish","format-standard","hentry","category-code-competitions","category-random-musings"],"_links":{"self":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/183","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=183"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/183\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=183"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=183"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=183"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}