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 a decent time was sufficient to get through.
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. One of the 2 remaining Australians got 66th place, quite impressive.
On to the questions I guess, although I’m going to have to refer to the post contest analysis this time for sure!
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. P is prime and less than 10^D, A and B are non-negative.
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. That would have been easy. The large input however D is at most 6, making a brute force of P and A impossible. What we need to do is consider each P and the set of numbers to determine both A and B simultaneously. 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). If we subtract these equations we get Y-Z = A*(X-Y) mod P. 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). This still leaves a few special cases. Specifically the X=Y case. If X=Y then Y will also equal Z, due to symmetry, regardless of A and B and P. So any case of repeated numbers is predictable. This includes the 2 number case, despite what I said just before…
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…
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. L is between 10^10 and 10^18.
A2) For the small input the maximum length of each piece of fencing was 100. For the large that jumped to 100000. I think that a key point to this question would have to be that L has a very large minimum value. 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. When the fence size jumps to 100k, my approach becomes infeasible, because the DP needs to go to 100k squared. Going to have to check the solutions for this one.
Okay, so I would probably not have gotten the large out, although the intuitive leap does appear within my level. Take the largest board, use it until we get just short of L (or exactly L). Then we need to determine how to make the remainder using smaller fences, or to make the remainder + largest fence, or +2 largest fence… We can do this by creating a graph, starting with nodes 0 to largest fence-1, and adding edges as follows. 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. 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). The length of that shortest path + number of max length boards to reach 0 is the answer. This only works because the shortest path will never have more than 100k weight 0 edges, and L is greater than 100k squared.
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.
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. 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.
A3) Small input is up to 200 items, large input is up to 100k items. Even the small input seems tricky here… would seem to need some kind of strategy. 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. Movements at the centre of mass are more useful than other movements since they are the only ones which actually separate things. The problem may also be separable into sub problems which don’t interact. In that case the centre of mass of each sub problem seems important. Small input I guess can be done via simulation of a strategy of centre of mass first or maybe largest first. I probably would have just tried one to see if it solved it, since you get answers for the small input immediately. Large input however requires better than straight simulation… Time to check the answers again…
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. Apparently this is a ‘famous theorem’ which probably means there are a few thousand people in the world who know it 😛 With this observation (and one other leap I would have been unlikely to get) the problem becomes quite simple. Simply construct the final answer and from there determine how many moves were required to get to it. Constructing the final answer can be easily done by simply building up the input. 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. 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. Each operation is therefore O(1), giving an O(n) simulation to get the final position. 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. 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. 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. 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…
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.
Q4) How many ways can you add 1 or more different numbers to give k, subject to a rather complex restriction… 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.
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… The small input limits B to be binary to decimal and k to be no more than 100. The large input however raises B to being anything up to base 70 and k to be up to 10^18… 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. 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. Then we need to work out how to multiply the total to get the actual answer. 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. However the fact that 0’s on the front don’t need to be distinct is a problem. At this point I give up and look at the solutions. Its not like I would have had any time left to solve this question in the competition anyway…
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.
However I was starting to get on the right track for the large input. 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. So you need to keep track of the carry, and how many of the numbers are finished and whether there is a 0. 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. It almost makes sense, but I would need to implement it to be sure.
Anyway 0 points for me here so I’m stuck with my theoretical 158th place.
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)