Posted on 23th April 2015
As ever, links to: Official Contest Analysis and my code on GitHub.
What did you need to do to progress? Score 30 points in 100 minutes, or more points. So doing problems A and B would be enough. Again, tackling the "small" problems quickly is worthwhile.
Problem A, Part Elf: At generation 40, everyone is 1 or 0 elf. So at generation 39, everyone is \( \frac12 (a+b) \) elf, where \( 0 \leq a,b \leq 1 \). By induction, at generation \( 40-n \) everyone is \( a/2^n \) elf, for some integer \( 0 \leq a \leq 2^n \). So read in P and Q, use Euclid's algorithm to find the gcd and hence write P/Q in lowest terms, and then we need \( P/Q = a / 2^{40} \) so Q should be a power of 2, less than or equal to 40, and we need \( P \leq Q \).
If we an ancestor who is 1 elf in generation \( 40-n \) then in the next generation, the offspring is \( \frac12 (1 + a/2^n) \) elf, for some \( 0 \leq a \leq 2^n \). By induction, in generation 0, you are \( \frac{1+x/2^n}{2^{40-n}} \) elf, where \( 0 \leq x \leq 2^{40} - 2^n \). That is, test \[ \frac{P}{Q} = \frac{2^n + x}{2^{40}} \] and if \( Q = 2^M \) then we need \( 2^n \leq 2^{40-M} P \leq 2^{40} \) for the maximum \( n\) as the answer is \( 40-n\). So just check all \(n\).
Problem B, Reordering Train Cars: Given a bunch of strings, and want to know how many ways we can concatenate them so that in the final single string, all letters appear consecutively: so "aabbc" is okay but "abac" is not. My approach was simply to look at each letter in turn:
- If no string contains this letter, carry on.
- If one string contains this letter, check that the letters are consecutive. Don't forget this case!
- If more than one string contains this letter, then split the strings into those which are just the letter repeated, and those which contains other letters as well. Say we get x = ___aaa, y = aaa___ then we can only arrange these as xy with the various repeats of a in the middle. Similarly check other cases.
- In all cases, we end up with one possible concatenated string (though perhaps many ways to form this one string). So remove all the old strings and add this new one in, and then repeat with a new letter.
I guess the difference between the small and large cases is that the small one can be solved by brute force (though this is slow in Python). The difficult part is remembering all the different cases. And, in my case, reading the question properly as the final answer should be returned mod 1,000,000,007.
Problem C, Enclosure: No way I could have done this in the time limit. Place rocks on grid points, and then a point is "enclosed" if a rock is on it, or moving up/down/left/right, you'll eventually hit a rock regardless of how you move. You can solve this by a lot of up front analysis:
- Again, carefully reading the problem, given K we want to find the least number of rocks which can enclose at least K points. This optimisation problem is equivalent to, for a fixed R, finding the maximum number of points we can enclose with R rocks.
- Let's think how to "improve" a given arrangement.
- Let's say a point which is enclosed, but doesn't have a rock on it, is "internal".
- Intuitively the best solution is "connected", in that all the internal points are connected. I'm not 100% sure how to show this rigourously.
- If you have two connected components, you can move them around until they are sharing rocks.
- Any rock which is not "enclosing" an internal point (that is, no internal point is next to that rock) can be moved at will.
- I think these moves are enough to reduce a disconnected case to a connected one...
- Anyway, assuming this, consider all the rows which contain rocks. If the first row is like this: ***...*** where * = rock, . = blank then we can walk from column 2 to column 8, say, and so in columns 4,5,6 there must be rocks somewhere below the 1st row. Move these up, and we increase the number of enclosed points, but don't increase the number of rocks. So we may assume that the top row is a continuous segment.
- The same argument applies to the left, right and bottom.
- Now consider the upper-left corner, which could look like:
*** ****
** ------> *
* *
* *
That is, we can always "move up" various rocks, or similarly "move left" rocks (which might then cause other rocks to be moved up or left) until the upper-left corner is just a line of rocks at a 45 degree angle.
- Similar do the same transformation to the other corners. We conclude that the optimal shape is a rectangle which has had triangles, at a 45 degree angle, removed from each corner. We now analyse all such shapes, in terms of rocks needed and enclosed points. Then it's very each just to check all such shapes to find the best case. We could then speed this up by some "memorisation" techniques, but actually, it's already easily fast enough for the "large" case. (Mental node: the functools decorator @functools.lru_cache can do this automatically in Python!)
- Imagine we take the top-left corner and change the first n rows to a triangle. So n=1 does nothing, and n=3 does the following:
**** **
* -------> *
* *
* *
So we have changed 2n-1 rocks to n rocks (removed n-1 rocks) and changed n*n interior points to 1+2+...+n = n*(n+1)/2 points (removed n*(n-1)/2 points). - So doing this with parameters a,b,c,d on the four corners, we end up using 2*(n+m) - (a+b+c+d) rocks and having n*m - (a*(a-1) + ... + d*(d-1))/2 interior points. We don't want to remove overlapping corners, and the constraints for this are that a+b, c+d <= n+1 and a+c, b+d <= m+1. - You can check that the maximum occurs when a,b,c,d are roughly equal (that is, all equal to k or k+1 for some k>=1). - So we just check the cases when all a,b,c,d = k, one equals k+1, two equal k+1 or three equal k+1. You can exactly solve the inequalities, but I just implemented a binary search. - Don't forget the special case when n=1 or m=1 (best we can do is just a row/column of rocks) and that for various values, it doesn't make sense to consider e.g. a,b,c=k+1 and d=k.