Here are the solutions to the Hacker Cup 2015 Round 1 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! Round 1 is available here: https:// facebook/hackercup/ problems.php? round=344496159068801 Homework If we precompute the primacity of each number, then answering test cases just takes a sweep over the precomputed results. To compute the primacity, one option is to used a modified Sieve of Eratosthenes (en.wikipedia.org/ wiki/Sieve_of_Eratosthenes). In the normal sieve we iterate upwards and whenever we find a prime number we cross off all multiples of it from our list of primes. Rather than crossing off a multiple, we can add 1 to a counter that keeps track of its primacity. For example, 2 is prime, so we add 1 to the primacity of 4, 6, 8, 10, 12, etc. 3 is the next prime, so we add 1 to the primacity of 3, 6, 9, 12, 15, etc. The time complexity is the same as the standard sieve, O(N log log N) for the integers 1 to N. Input: pastebin/tUftWCVR Output: pastebin/60yhTXsR Autocomplete The go-to data structure for this problem is a trie ( en.wikipedia.org/wiki/Trie ). As each word comes in, we add it to the trie in O (L) time, where L is the length of the word. In the same amount of time, we can determine what the shortest unique prefix is. If we traverse the trie all the way to the end of a word W, then some word W must already exist that has W as a prefix. In this case, we must type all of W. However, if we hit a leaf node in the trie, then we know that the prefix well type is one letter longer than the word stored in that leaf node. Input: https://dropbox/ s/8u5hbw54dgr48m0/ autocomplete.full.in?dl=0 Output: pastebin/GRZriZCB Winning at Sports This problem has a fairly standard dynamic programming formulation: Let f(u, t, U, T) be the number of ways to achieve a stress-free victory when we currently have u points, the opponent has t points, and the final score will be U-T. The answer were looking for is then f(0, 0, U, T). We can define f recursively as follows, assuming u < U and t < T: f(U, T, U, T) = 1 (were done!) f(u, T, U, T) = 1 if u > T (all thats left is for us to finish scoring) f(u, T, U, T) = 0 otherwise (this victory is not stress-free) f(U, t, U, T) = 1 (all thats left is for them to finish scoring) f(u, t, U, T) = 0 if u > 0 and u ≤ t (this victory is not stress-free) f(u, t, U, T) = f(u+1, t, U, T) + f(u, t+1, U, T) otherwise (either team can score next) Similarly, let g(u, t, U, T) be the number of ways to achieve a stressful victory: g(U, T, U, T) = 1 (were done!) g(u, T, U, T) = 1 (all thats left is for us to finish scoring) g(U, t, U, T) = 0 (this victory is not stressful) g(u, t, U, T) = 0 if u > t (this victory is not stressful) g(u, t, U, T) = g(u+1, t, U, T) + g(u, t +1, U, T) otherwise (either team can score next) Obviously the latter two parameters dont change, so we just need O(U * T) memory to memoize the results, and the time complexity will also be O(U * T). Input: pastebin/zbf0GYiD Output: pastebin/cQutFFcq Corporate Gifting This problem is equivalent to the following graph theory formulation: given a tree T with N nodes, color the nodes with colors 1, 2, 3, ..., such that no two adjacent nodes have the same color, and that the sum of all colors is minimal. Since a tree is a bipartite graph, it can be always be colored with two colors 1 and 2, but this does not always yield the minimal solution as shown in the following simple example: First we need to construct the adjacency lists for each node. This can be achieved by using vectors or lists in order to use O(N) memory. Assume that the number of different colors used in the minimal solution is C. We can formulate a recursive solution (though note that this can also be computed bottom-up by removing leaves from the tree as we go). For each node v, let f(v, c) be the minimal sum of colors in the subtree rooted at node v, given that c in {1, 2, ..., C} is the color of node v. Let v1, v2, ..., vk be the children of v. We can try any of the colors 1, 2, ..., C for the node v, and compute f(v, c) as: f(v, c) = c + [min over c1, c1 ≠ c] f(v1, c1) + ... + [min over ck, ck ≠ c] f(vk, ck) Therefore, direct implementation of the above method gives us a solution with time and memory complexity O(N * C2). We can also prove that O(log N) is an upper bound for C. Let C(k) be the size of the smallest tree that needs all colors 1, 2, ..., k in an optimal coloring. Trivially, it holds that C(1) = 1 and C(2) = 2. Without loss of generality, we can pick the node with color k to be the root. In that case, the root needs to be adjacent to all colors from 1 to k-1 and we can apply the inductive hypothesis as follows: C(k) ≥ C(k-1) + ... + C(2) + C(1) + 1 ≥ 2k - 1 + ... + 21 + 2 + 1 = 2k. This completes the proof. The above algorithm therefore has complexity O (N log2 N) in both time and memory. We leave the problem of constructing a minimal tree that requires k colors as an exercise for the reader. However, there is also an algorithm with O(N) time and memory complexity. The above formula can be simplified if we just use the two best values for each node, together with the colors where these minimum values are achieved. Let ci and di be the best and second- best colors for the node vi respectively. Now, f(v, c) = c + [f(v1, c1) if c ≠ c1, otherwise f(v1, d1)] + ... + [f(vk, ck) if c ≠ ck, otherwise f(vk, dk)] This appears to still take O(C * k) time as we need to try all C colors, leading to a O(N log N) solution. However, we can improve this to O(k) time. Let B be our base cost, the minimum we must pay for the subtree rooted at v: B = c + f(v1, c1) + ... + f(vk, ck) Now, let Ai be the additional cost if we decide to use color i: Ai = Σj [f(vj, dj) - f(vj, cj), where cj = i] We can precompute A in O(k) time, and then we can get the minimum cost of coloring vs subtree in O(k) time with: B + min (A1, ..., Ak) And with that, our solution is now O (N)! Input: https://dropbox/s/ coz49bgunnm0b18/gifting.full.in?dl=0 Output: pastebin/xe9yFycs
Posted on: Fri, 23 Jan 2015 04:56:06 +0000