


Ying wins Room 1
Coherencyby dgoodmanFirst we might as well sort the given sequence. If any adjacent values differ by more than maxjump, the answer is 0. The crucial values (articulation points?) are the ones whose 2 neighbors differ by more than maxjump. Any sequence that visits a crucial point without first visiting either all of the values greater than it, or all the values less than it, cannot visit all the values without having too big a jump. So a nonjumping sequence cannot start at a crucial value or anywhere between 2 crucial values. On the other hand, if we start at a value below the lowest crucial value (or at a value higher than the largest crucial value) we can successfully construct a nonjumping sequence by decreasing down to the lowest value skipping one value each time, and then finishing the sequence by increasing to the next available value at each step. So the possible places to start are anywhere below the smallest crucial value, or anywhere above the greatest crucial value. So: sort the sequence if any adjacent pair differs by more than maxjump, return 0 find vlo and vhi the lowest and highest crucial values if there was no crucial value, return the number of distinct values in the sequence return number of distinct values less than vlo + number of distinct values greater than vhi Architectsby dgoodmanOriginally this problem was going to be to design a building with smooth sides whose crosssections could support the weight above them. It's a nice problem, but a little too easy to solve analytically as a differential equation problem instead of using approximation techniques. So this is a discrete version of that problem. Rectangular sections of a building are represented by boxes, stacked one on top of another. They each have a height of 10, and each box must have the same width/length proportions as the given size of the bottom box. The sizes must satisfy two constraints (the overhang rule and the strength rule), and the goal is to maximize the size of the roof. This suggests that we should choose the box sizes from the known bottom box up, but this approach is too hard because the constraints for a box depend on the boxes above it, not the ones below it. So the key is to recognize that we can easily solve the reverse problem: given the roof size we can construct the building from the top down trying to minimize the size of the bottom box. The greedy strategy of choosing the smallest possible box solves that problem. And it is clear that the bigger the starting roof size, the bigger will be the size of the bottom box. So we can use bisection to find the roof size that corresponds to the desired size of the bottom box. The pseudocode for solving the problem of minimizing the bottom size given some roof_area would be top box area = roof_area; for each box down minO = smallest allowed so previous box doesn't overhang too much if(this is bottom box) minS = smallest area that will support all previous boxes else minS = smallest area that will support itself + all previous boxes this box area = maximum(minO, minS) The full (horizontal) diagonal of a box is the diagonal of the bottom box times the square root of the ratios of its area to the area of the bottom box. The overhang from a box with area Aj on top of a box with area Ak is half the difference in their diagonals. Solving algebraically, we get that the overhang is 50 when 50 = .5* sqrt( (w*w+l*l)/(w*l) ) * ( sqrt(Aj)  sqrt(Ak) ) where w and l are the given width and length of the bottom box. So minO is either 0 (when Aj has a diagonal less than 100) or minO is (sqrt(Aj)  mess)2 where mess is a fixed number. minS (except for the bottom box) is calculated from the equation minS*K = minS*10 + sum_of_previous_volumes. Thus minS = sum_of_previous_volumes / (K10) provided that K>10. Now putting it all together, we first take care of the special case n=1. In that case there is only one box whose size is given. If K<10 then no box (other than the bottom box) can support its own volume so the answer is 1. If K=10 the only possible solution is when n=2 and the top box can be as big as the given bottom box. Finally we do bisection starting with lo=0 and hi = 10^99 (overkill, since the overhang rule by itself makes it impossible for the roof to be too big). Bisecting 1000 times will reduce the gap between lo and hi to 10^200 or the machine accuracy and doing it this way guarantees that you won't get in an infinite loop with machine accuracy issues. Amazingby radeyeExhaustive search won't quite work. Ten trips, with eleven endpoints, each of which can be any of ten cities, gives an overall count of 10^11 routes to evaluate. If it were just five trips, we could do it. So we need a way to do each half of the trip separately, and then somehow combine the two searches to get a final answer. Let us say we have a list of all possible 5trip solutions, weighted appropriately for the first half, and a second list of all possible 5trip solutions, weighted appropriately for the second half. Can we somehow find the best pair of solutions from these lists without enumerating them all? Absolutely. All we need to do is scan the lists with two pointers, at every step keeping the total as close to our target as possible. The following elegant code does that, given a target and sorted arrays a and b: int i = 0 ; int j = b.length  1 ; int best = Math.abs(a[i] + b[j]  target) ; while (true) { value = a[i] + b[j] ; best = Math.min(best, Math.abs(valuetarget)) ; if (value < target && i+1 < a.length) i++ ; else if (j > 0) j ; else break ; } It essentially iterates over one array, tracking the value in the other array that takes us closest to the target. At each step it uses the information on whether it is too high or too low to decide which pointer to advance. When it can no longer improve the result, it exits. Only two minor complications remain. The trips must be joinable; the first half must end in the same city the second half starts. In order to handle this, we simply wrap an outer loop around the whole algorithm that iterates over the possible cities, and requires that the first half end at the first city and the second half start at the second city. Dealing with the difficulty factors is straightforward; the weight at trip i is simply factor^i. 
