Last on-line round of the TCO/GCJ ‘season’. 138 people eligible to compete, 125 turned up. Unlike last time the first 2 problems were completed by a significant proportion, so advancing required a fast time for both the first 2 problems. Only one person solved all 3, the same person also had the only solution to the 3rd problem.
Q1) Given a sequence of numbers where each element is between 1 and n, determine how many sequences of equal length with each element also between 1 and n are a ‘match’ with the original sequence if you remove one element from each sequence. Since the answer is large, return modulo large prime.
A1) At first glance this doesn’t seem too complicated, consider the original sequence, remove each element in turn, and count how many sequences you can create by adding one element. The problem is of course that this double counts. Even just considering a single case, if you insert the same value before/after a given number, the sequences are the same. So either we need to determine how many double counts occur and subtract them off, or use a different approach entirely.
Looking at a solution (because I feel lazy today) scenarios can be divided in to 2 cases. Where the number we insert is a member of the original sequence, and where it is not. If it is in the original sequence, we have complicated possibility of double counting, if it is not, then it is much simpler. So for each element removed (up to 50 cases) for each insertion position ( up to 50 places) for each distinct original value (up to 50 values) we have something which needs checking for duplicates. This is a fairly small sample size, so we can easily use a set. For each of the element removed, for each insertion position, we can also insert the n-distinct_count_options other values. There is still the ability to double count here, but these cases can be grouped by what the inserted value is (regardless of whatever that value is), so we can use a place holder (0 for instance) and the same set, and each time we get a non-match we add n-distinct_count_options to the final result.
Q2) Given pairs of values, determine the minimum number of individual value swaps (swapping one value from one pair with one value from another pair) is required such that all pairs have a maximum difference of k. If it is impossible, return -1.
A2) There is only a maximum of 16 pairs here, which suggests bit-masks may play a role.
But again, I am feeling lazy today, so I went straight to a solution. The first step is to determine whether the problem is possible at all. It seems that if you take all the values from the set of pairs, put them together, and sort them, they must fall out pairwise into values which are close enough. The logic behind this seems to be rather straight forward – if you consider the smallest value you need a value close enough, and if there are multiple which work, choosing anything other than the smallest of those, can only potentially make it harder to form the next pair.
To find the minimum number of swaps we can look at this problem from a different angle. Any solvable situation can easily be done in at most n-1 swaps, if we look at the sorted order pairing, we can swap the second to be next to the first, the 4th to be next to the 3rd, and so on, until the final number is already in the right place, the question is how much can we short cut that. If we have a solvable scenario which can be divided into 2 solvable subsets, worst case we can do the first in k-1 steps and the second in n-k-1 steps, giving n – 2 steps. What remains is to determine the most number of steps which can be saved, by following this down recursively. The maximum number of steps which can be saved by a scenario is the best sum of the maximum number of steps that can be saved over each partition into 2 solvable subsets. With a minimum of 1. Since we already have worked out how to determine if a situation is solvable, we can perform that for every subset, then considering every subset, of every subset (which is not a small number, but is achievable), determine if that subset and its compliment are both solvable, and use that as the framework to build up a recursive cache of maximum number of steps to be saved for a given subset. Then the final answer is n – maximum number of steps saved for the full set, assuming it is solvable. If it isn’t the answer is of course -1.
Q3) Determine the minimum number of jumps to get from 0,0 to x,y if each jump can’t be more than a distance sqrt(d) in a straight line, and jumps may only be to/from integer coordinates.
A3) Unusual bit here is that rather than just asking this question once, each test case can be up to 50 of these questions, which you have to answer all at once. For d=1 the answer is |x| + |y|. For d=2 the answer is max(|x|,|y|). From there the question that first needs to be asked I think is whether a greedy solution is correct. If so we should be able to find a pattern in the jumps which repeats and use that to ‘accelerate’ to the finish.
Looking at the solution again, it appears some fancy maths comes into play. Given d, you start off by determining the pair of maximal distance jumps which are either side of the angle connecting 0,0 to |x|,|y|, do this by constructing each possible maximum distance jump and watching the crossproduct change signs as we go from one side to the other. (May want to take care of the x= 0 or y = 0 cases separately just to be sure you don’t screw that up.) Once you have this pair of vectors it just becomes a question of how many of one and how many of the other to add together to give the right destination. This is where the maths seems to get a bit fancy. Taking directly from the solution, the answer is crossproduct((x,y),V2-V1) / crossproduct(V1, V2-V1), rounded up. I’m not quite sure how to derive this exactly, but at first glance I wouldn’t say it was wrong.