Here are the solutions to the Hacker Cup 2016 Round 3 problems. If you had a rejected solution and want to find out where you went wrong, read on and download the official input and output!
Input / Output: https://www.dropbox.com/sh/rjs1vvfrizuypmw/AADt6tVna4xFLVO-7q-PwDcma?dl=0
Chess Showdown, Boomerang Farm, and Boomerang Umbrella were written by Jacob Plachta. Matt Laundro was written by Aleksandar Ilic. Public Transportation was co-written by Jacob Plachta and Vladislav Isenbaev.
Chess Showdown
Each player's optimal strategy is to try to lose each of the first N - 1 games, and then try to win the final game. When a player loses, the color they choose for the following game will clearly be the one which maximizes their probability of achieving their desired result in that game. For example, if L_w > L_b and W_b > W_w, then for the first N - 2 games, Andrew will try to lose and choose white (while Jacob will try to lose and choose black), and in the second-last game, Andrew will try to lose and choose black (while Jacob will try to lose and choose white).
Now that we know what each player will try to do throughout the match, we'd like to compute each probability P[i] that Andrew will play as white in the ith game. P[1] = 1, and for each 1 <= i <= N - 2, P[i + 1] can be computed based on P[i] based on the players' strategies of trying to lose and pick the color that will most likely make them lose again. P[N] can then be computed based on P[N - 1] in a similar fashion, and finally the answer will be P[N] * W_w + (1 - P[N]) * W_b.
To speed up the O(N) algorithm described above, we can directly compute P[N - 1] with matrix exponentation (noting that the evaluation of P[i + 1] based on P[i] is constant for 1 <= i <= N - 2), yielding an O(log N) solution.
Boomerang Farm
Each boomerang always has a horizontal and a vertical section — the horizontal section may point either to the left or to the right of the centre, while the vertical section may point either to the top or to the bottom. The key insight to be made is that rotating a boomerang by 90 degrees in one direction only toggles the state of its horizontal section, while rotating it in the other direction only toggles the state of its vertical section. Therefore, its horizontal and vertical sections are completely independent.
Considering the horizontal sections in a single row of the grid, each one has an initial orientation (either left or right) which can be independently toggled at the cost of 1 minute. A pair of boomerangs touch horizontally whenever a certain section points to the right and the following section points to the left. A similar concept applies to the vertical sections in each column of the grid.
From there, a standard dynamic programming solution becomes evident. We can iterate over the horizontal sections row-by-row, and then the vertical sections column-by-column, with the state consisting of the index of the current section, the orientation of the previous section in the same row/column (if any), and the number of minutes used so far. There are two transitions from each state, involving either leaving the current section alone or toggling its orientation (taking 1 minute), one of which incurs a cost of 1 depending on the orientation of the previous section. The time complexity is O(N^2 * M).
Boomerang Umbrella
Without loss of generality, let's say that we'll initially throw the boomerang towards the right (the algorithm can then be repeated with inverted x-coordinates). Let's also think of the raindrops' impact times as y-coordinates. The boomerang's path can then be divided into 3 sections — diagonally up-right (with slope 1 / V), vertically up, and diagonally up-left. There will always be an optimal path such that the vertical section touches at least one drop (even if the vertical section has length 0). As such, let's consider splitting this path in half. Let A[i] be the maximum number of drops on a path that goes diagonally up-right and then vertically up, ending at drop i. Similarly, let B[i] be the maximum number of drops on a path that starts at drop i, going vertically up and then diagonally up-left (note that B[i] can be computed just like A[i] if we think of reversing the path and inverting all y-coordinates). There's then a valid path passing through drop i that hits A[i] + B[i] - 1 drops, so we just need to find the largest such sum!
What remains is computing A[i] efficiently. We can sort the N drops "diagonally", by increasing V * y - x, breaking ties by increasing x, and iterate over them in this order. For each drop i (at coordinates (x, y)), there are 3 ways to get to it:
Directly along its diagonal
Directly up from a lower drop
Up from a lower diagonal
We should compute the number of drops along each of these approaches, take the largest one, and add 1 to it to yield A[i]. The first value is simply the count c of previous drops which had the same value of V * y - x. To get the second value, we need to get the largest A[j] for some earlier drop j with x-coordinate x, which can be done efficiently using a map.
The third value is the trickiest — we need to maintain a "convex" set of pairs (x, c), sorted by increasing x and having increasing c, populated with the x and c values for drops which have already been processed. This set's property of increasing c values must be preserved by deleting obsolete pairs as necessary (for example, if (x1, c1) is inserted, each pair (x2, c2) such that x2 >= x1 and c2 <= c1 should be deleted). If we then find the largest pair (x', c') such that x' is no larger than drop i's x-coordinate, then c' will be our needed third value, as there must have been a diagonal path that ended at x-coordinate x' after hitting c' drops, which can continue up to drop i's x-coordinate and then extend vertically up to drop i.
The total running time of this algorithm is O(N log N), as its key components (sorting the drops, maintaining a map for the second value, and maintaining a convex set for the third value) each have this time complexity.
Matt Laundro
http://www.pdf-archive.com/2016/01/...
Public Transportation
Let P[i] be the position of the ith bus stop, when they're sorted in increasing order and numbered from 0 to N - 1. Consider a stop i (0 <= i < N), a gap size k (1 <= k <= K), and a second stop j = (i + k) % N. Of the C(N, K) possible subsets of bus stops left on the road, there are C(N - k - 2, K - k) of them for which there are no stops in the gap extending clockwise from stop i to stop j. This gap has a size of d = (P[j] - P[i] + L) % L. For each of these subsets, if your starting position is in that gap (which happens with probability d / L), your expected walking distance will be d / 4. Therefore, the contribution of this pair of stops to the total answer is C(N - k - 2, K - k) / C(N, K) * d^2 / 4L. Assuming that appropriate modular arithmetic is used, including the precomputation of factorials modulo 10^9 + 7, we can simply sum these values over all NK pairs of values (i, k).
O(NK) is too slow, so we'll have to make some observations about the above expression. Clearly, C(N, K) and 4L can be factored out and divided by at the end. Another interesting fact is that, while d depends on both i and k, C(N - k - 2, K - k) only depends on k. Therefore, computing the sum S[k] of all N d^2 values for a given k will be useful.
How can we compute S[0..K] efficiently?
We'll start by computing another sequence of values F[0..2N], where F[i] = sum{ j=0..i | P[j] * P[i - j] }. This is a well-known computation that can be completed in O(N log N) time using a fast Fourier transform (FFT). In this problem, we need these results to be exact integers. It's possible to compute them accurately enough using a good implementation of a regular FFT, rounding each of them off to the nearest integer. However, a more stable solution is to use a number-theoretic transform (NTT). This process can yield exact integral results modulo a prime p — however, it's a requirement that p - 1 be a multiple of M (where M is the size of the input array, which must be a power of 2 greater than N), so it won't work with p = 10^9 + 7. Instead, we can compute two NTTs, for two appropriate primes p1 and p2 in the vicinity of 2 billion (such that p1 * p2 > NL^2), and use the Chinese Remainder Theorem to combine each of their results into the exact value modulo p1 * p2.
With F[0..2N] computed, we can proceed by computing S[0..K], which can be done in O(K) by carefully rearranging the equations involved. We should first precompute the sum of squares of P values (s = sum{ i=0..(N-1) | P[i]^2 }), P's prefix sums (A[i] = sum{ j=0..i | P[j] }), and P's suffix sums (B[i] = sum{ j=0..i | P[N - j - 1] }). It can then be shown that S[k] = 2s - 2(F[k] + F[k + N]) + (j + 1)L^2 + 2L(A[k] - B[k]).
Finally, we have what we need to compute the answer in O(K) time — it will be sum{ k=0..K | C(N - k - 2, K - k) * S[k] } / C(N, K) / 4L. The time complexity of this solution is O(N log N + K).
