Posted on 17th April 2015
As ever, links to: Official Contest Analysis and my code on GitHub.
Of current interest is how to progress: top 1000 people go through, and for that you'd need 42 points in any time faster than basically the whole 2.5 hours. This seems more reasonable...
Problem A, The Repeater: Given some input strings and Omar can make a move: he can pick one string, and one character in that string, and either repeat it once more (so "abc" -> "abbc" or "aabc" or "abcc") or if the character is already repeated, he can delete one copy (so "aabcc" -> "abcc" or "aabc"). Can he make all the strings the same, and if so, what's the minimal number of moves to do so?
The "invariant" is obviously the characters ignoring multiplicity, and if they all agree, we can treat each character type independently. So this reduces to this problem: - Given numbers \(n_1, \cdots, n_k\), each time step we can increase or decrease each number by 1. What's the minimum number of steps until they are all equal? This is the same as choosing a target number \(n\), and then the time is \(\sum |n_i-n|\). - Order the numbers \(n_1 \leq n_2 \leq \cdots \leq n_k\), so clearly the optimal \(n\) satisfies \(n_1 \leq n \leq n_k\). - Suppose we have \(n_i \leq n < n_{i+1}\) and we increase \(n\) by 1 (here we allow \(i=k\) and \(n_{k+1}:=\infty\)). Then we move 1 away from \(n_1,\cdots,n_i\) and 1 closer to \(n_{i+1},\cdots,n_k\) so the "cost" changes by \(i - (k-i) = 2i-k\). - It follows that the best choose for \(n\) is the "mid-point" of the sequence: the middle term if we have an odd number of terms, or otherwise any value between (inclusive) the two middle terms of an even length sequence.
Problem B, New Lottery: In Python, the small case is a trivial search:
def combs(A, B, K):
count = 0
for x in range(A):
for y in range(B):
if (x & y) < K:
count += 1
return count
Or I guess a fancy generator comprehension (which is slightly slower), using the boolean get prompted to ints:
def combs(A, B, K):
return sum( (x & y) < K for x in range(A) for y in range(B) )
This is too slow for the "large" case though. Somehow this problem suggests "dynamic programming" and after a lot of thought, we come up with the following. We want to count the set \[ V(A,B,K) = \{ (x,y) : 0 \leq x \le A, 0 \leq y \le B, x\& y \le K \} \] and the hint seems to be to consider the pairs \( (x,y) \) as a whole. The "and" operation works "bit-wise", so look at the lowest-order bits, which can be of four types:
x and y are both even, say \( x=2x', y=2y' \). Then \( x\& y = 2(x'\& y') \le K \). Now, for integers, \( 2a \le b \ \Leftrightarrow \) \( 2a \leq b-1 \ \Leftrightarrow \) \( a \leq \frac{b-1}{2} \ \Leftrightarrow \) \( a \leq \lfloor \frac{b-1}{2} \rfloor \ \Leftrightarrow \) \( a \le \lfloor \frac{b+1}{2} \rfloor \). So \( (x,y) \in V(A,B,K) \) if and only if \( (x',y') \in V(\lfloor \frac{A+1}{2} \rfloor, \lfloor \frac{B+1}{2} \rfloor, \lfloor \frac{K+1}{2} \rfloor) \).So we can subdivide each case into four "smaller" cases. As ever, this sort of thing, naively implemented, it slow, because you end up computing small cases repeatedly. A standard dynamic programming approach (which would be faster with a std::map style data structure, a dictionary which keeps it keys in order) is very fast. See my IPython Notebook for a comparison.
Problem C: Bored Travelling Salesman: Slight proud of myself for figuring this out. As the ZIP codes are all the same length, the smallest concatenation comes from the "smallest" route where we try to visit the lowest zip code first, and then the next lowest, and so on, subject to having a valid route. This is very reminiscient of the 2013 Qualification round, Problem D. Here the algorithm tries the next "best" move, and then tests to see if the problem still has a solution. So, can we do something similar here?
The trick is to notice that when visiting a city, we retain a "return" ticket, which we can use later. So when traversing the graph, we can always "back-track" to the city we started from originally (or just back up part way).