luca123 Posted August 5, 2015 Report Share Posted August 5, 2015 Here are the solutions to the Hacker Cup 2015 Finals problems. Read on and download the official input and output!The Final Round is available here: https://www.facebook.com/hackercup/problems.php?round=1556405007936780Fox Blocks(Problem author: Jacob Plachta)When querying the range of indices a..b, consider the following algorithm:Find the smallest index i such that a < i ? b and Hi > Ha, if any. If such an index is found, then each column a..(i-1) must have a water level of Ha inches, so these columns in total hold Ha * (i - a) - (Ha + Ha+1 + ... + Hi-1) square inches of water. Then, repeat this process from index i instead of a (find the first index j such that i < j ? b and Hj > Hi, and so on), until the leftmost column x with maximum height in the range of indices a..b has been found (and all of the water to its left has been totaled up).The above strategy can then be repeated starting at index b and going to the left, up to the rightmost column y with maximum height. Finally, the water level of columns x..y must be Hx inches, so they hold Hx * (y - x + 1) - (Hx + Hx+1 + ... + Hy) square inches of water.The algorithm described above clearly takes O(N) time per query naively. To attempt to speed it up, we can precompute the prefix sums of H (to query sums of intervals of H values in O(1) time). Additionally, for each index, we can precompute the next key index to the right and the total water stored between them (as described above), by iterating over the array right-to-left and keeping a stack of indices sorted by column height. Similarly, we can precompute this going to the right, for the second part of the algorithm. On random data, this may save time on searching for the next index at each iteration of the algorithm - however, it will still take O(N) time per query in the worst case.Finally, to improve the time complexity to O(log N) per query, we can store not only the next index (in each direction), but also the one 2 steps ahead, 4 steps ahead, 8 steps ahead, and so on. For each query, we can then repeatedly skip ahead as much as possible from a without overshooting b (and vice versa), which will take at most O(log N) skips.Input: https://www.dropbox.com/s/ievk6o4z51ea557/fox_blocks.in?dl=0Output: https://www.dropbox.com/s/n2vyjvxj85hc823/fox_blocks.out?dl=0Fox Lochs(Problem author: Jacob Plachta)It can be shown that there exists a longest line segment that passes through at least 2 vertices of the union of the rectangles (in fact, this extends to the union of a set of arbitrary polygons). Each vertex of the union is either the vertex of a rectangle, or an intersection point of two rectangles. Therefore, the union has O(N2) vertices, and we must consider O(N4) different lines, finding the longest valid segment of each.For each line, we can compute its (at most two) intersection points with each rectangle, which (if they exist) define a range of the line which is within the union. Note that calculating the intersection of a line with only axis-aligned line segments may be done with simpler code than general line intersection. Finally, we can do a line sweep over the line to find maximal ranges which lie within at least one rectangle. Sorting the line's intersection points with rectangles takes O(N log N) time, and so the total time complexity of this algorithm is O(N5 log N).Input: https://www.dropbox.com/s/4paspa7w1jxjbp4/fox_lochs.in?dl=0Output: https://www.dropbox.com/s/ujkjm3mhl5blypf/fox_lochs.out?dl=0Fox Focks(Problem authors: Andrew Henrey and Jacob Plachta)We can start by taking each Fock's given one-step color transition matrix to a large power (250 is easily enough) with standard fast matrix exponentiation, to compute the probability Pi,c that the ith Fock has color c at time 250 (for 1 ? i ? N and 1 ? c ? 3). This takes N * 50 * 33 time.Now, one might be tempted to guess that all of the P values are the same for time 250 as for time 250 + 1. In fact, this is true for many initial matrices. However, it's possible to construct matrices for which the P values instead eventually become periodic every 2 or 3 time steps, such as these:0 50 50100 0 0100 0 00 100 00 0 100100 0 0Therefore, all of the P values must eventually become periodic as a whole every 6 time steps. As such, we can compute the probability of a strict majority of a Fock color at each time 250..(250+5), with the final answer being the average of these 6 values. Furthermore, for each time, the events of each of the 3 colors having a strict majority are mutually exclusive, so we can compute their probabilities and add them up.There are two different intended ways to solve the above subproblem for a given time and color. One is based on the simple O(N2) DP solution, in which we calculate Di,j as the probability of j of the first i Focks having the current color at the current time. We can observe that, for each i, Di,j can only have a "significant" value (larger than some threshold such as 10-12) for quite a limited range of j values. Keeping track of this range as we iterate i from 0 to N, the inner loop will pass over significantly fewer than N values each time, allowing the DP to run easily in time.The other possible intended method uses computes the probability Ci of having i Focks of the current color with a divide-and-conquer strategy over indices of Focks. For a range with a small number of Focks (for example, no more than 100), the C values can be computed with the simple DP mentioned above. On the other hand, a larger range can be recursively split in half, with the C arrays of its two halves then combined together with a fast Fourier transform. This algorithm has a time complexity of O(N log2 N).Input: https://www.dropbox.com/s/nvxhklxbxkt3ax5/fox_focks.in?dl=0Output: https://www.dropbox.com/s/r9vz088kyh31wc4/fox_focks.out?dl=0Fox Hawks(Problem author: Vladislav Isenbaev)To approach this problem, we need to be able to count the number of solutions to the boolean expression with some variables possibly having fixed values (true or false), or determine that the number of solutions is larger than 1018. If we can do that, then we can determine the value of each variable from N down to 1 in turn using the following standard procedure:Fix variable N to be false, and count the number of solutions. If it's no greater than K, then variable N must be false, due to the fact that all sets without hawk N have smaller values than all sets with hawk N. Otherwise, variable N must be true, and we can subtract that solution count from K going forward. We can then repeat this process with variable N-1, while keeping variable N fixed at its determined value, and so on.Now, the tricky part is determining the solution count each time it's needed, with new variables having fixed values. To begin with, we should parse the boolean expression and store it in the well-known format of a binary expression tree, with each leaf node representing a variable, and each internal node representing an operator (operating on the subexpressions represented by its two children). Furthermore, for each node, we'd like to calculate the number of satisfying solutions for its subexpression, and and the number of non-satisfying solutions. For a leaf node, these values depend on the variable's fixed value (if any), and for an internal node, these values can be computed from its children's values. The number of solutions to the whole boolean expression is then stored in the root node.All of the values in the tree can initially be computed in O(N) time, and then when a variable's value is fixed, only its node's ancestor's values need to be recomputed. However, there can be O(N) such ancestors each time, so this is too slow. To improve the time complexity of each iteration to O(log2 N), we can perform heavy-light decomposition on the tree, creating a segment tree for each run of heavy edges. Basically, each node of each segment tree will end up storing 4 values - the number of true/false solutions for its range's top node's subexpression in terms of the number of true/false solutions for its range's bottom node's subexpression.Input: https://www.dropbox.com/s/ket1jsfkese6idz/fox_hawks.in?dl=0Output: https://www.dropbox.com/s/ouxboghrhdb1rbd/fox_hawks.out?dl=0Fox Locks(Problem author: Jacob Plachta)Due to the constraint regarding opening each lock adjacent to the central hub at most once (and closing it immediately afterwards), we'll end up choosing some sequence of distinct canals to "use", each time increasing the hub's water level as much as possible.When a canal c is "used", it can be observed that it's always optimal to first open some prefix of p of its locks (those between sections 1 and 2, between 2 and 3, and so on up to the one between p and p+1), for some 0 ? p < Nc, and then open and close the lock between section 1 and the hub. If the hub has a current water level of h1, then its water level h2 after this sequence of lock toggles will be (h1 + Wc,1 + Wc,2 + ... + Wc,p+1) / (p + 2).Due to the constraints on the input, there can only be at most 16 "large" canals (those with multiple sections). Conveniently, it can be shown that it's always optimal to use the remaining "small" canals (those with 1 section) in non-descending order of water level in their single section, possibly skipping some - this is basically due to the fact that there's only one choice of p for these canals. As such, we can use the overall approach of bitmask DP, calculating the maximum hub water level Db,i after the bitmask b of large canals have been used, and the first i small canals (after sorting) have been considered. In the worst case, there are 216 * 35 ? 2*106 states, with at most 17 transitions from each state. Therefore, when considering a new large canal to use from a given state, trying all possible values of p will be far too slow. A single optimal value of p can't be precomputed for each canal either, as it can vary depending on the current water level of the hub.For each value of p for a given large canal, considering plotting h1 (the current hub water level) against h2 (the resulting hub water level), on the x- and y-axes of a graph respectively. Note that each p produces a line with a slope of 1 / (p + 2), and that the optimal value of p given a certain h1 corresponds to the line with the largest y at x=h1. As such, we're interested in the upper hull of these lines. Each line will be part of the hull for a single contiguous range of x-coordinates (or never). Therefore, for each large canal, we can iterate over its lines and precompute a set of ranges of x-coordinates, with a corresponding optimal line equation for each range, and then binary search over them during the DP to find the best way to use a certain canal c given a certain current hub water level in just O(log Nc) time.Input: https://www.dropbox.com/s/xcoeysz8ct8kcav/fox_locks.in?dl=0Output: https://www.dropbox.com/s/99hay5su5j69v4i/fox_locks.out?dl=0Register: https://www.facebook.com/hackercup/registerPagina de facebook: https://www.facebook.com/hackercup Quote Link to comment Share on other sites More sharing options...
