JongMan wins the Wildcard round!
Discuss this match
Thursday, June 28, 2007
Introduction by Olexiy
JongMan and tomek advance to the finals. They'll join Jan_Kuipers, Eryx, Vitaliy, tomekkulczynski, bmerry and darnley in the finals tomorrow, starting at 1:30 PDT. Congratulations and good luck to the finalists!
Here we must compute the coefficients of the required power series. The problem statement gives the formula for each coefficient in terms of previously computed coefficients. The real work here is the rational arithmetic, which consists of fraction manipulations, and GCD for reducing. Fortunately, the constraints allow everything to be done with 64-bit types, which removes many potential headaches.
Suppose we perform a sequence of folds. At each stage, the entire state is described by a partition of the paper into a grid of rectangles containing the respective thicknesses. If we only make folds along vertical axes, the paper is partitioned into a collection of vertical strips of varying thicknesses. Analogously, if we make only folds along horizontal axes, the paper will be partitioned into horizontal strips. If we make both kinds of folds, we can look at each kind in isolation. Each strip will have an associated thickness. The rectangle formed by the intersection of a vertical and horizontal strip will have thickness equal to the product of the thicknesses of the strips. This can be proved by induction on the number of folds made.
Knowing that the vertical and horizontal folds can be treated in isolation, we now solve the one dimensional problem (ie., assume we only had folds along vertical axes). At each step in the process we will maintain a range object. The range object will store a sequence of integers representing the edges of the paper and the strip boundaries. In addition, it will store thicknesses of the associated strips. Each time a (valid) fold is made, the coordinate of the fold axis becomes an element of the sequence of integers in the range object. Looping over the old range elements, we construct a new range object accommodating the changes associated with the fold (reflecting coordinates across the folding axis as needed). This can be done in time linear in the size of the old range object. In addition, we also update the associated thicknesses. If we process all of the folds in this manner, we will have a final range object. The highest thickness is what we desire. The return value is the product of the highest thicknesses for the vertical and horizontal ranges.
We will solve this problem using memoization/dynamic programming. The key question to ask when each integer is added to the list is whether it should also be added to the cache in order to achieve the optimal cost. The locality constraint allows us to consider only the previous 10 (actually, this is overkill) decisions we have made when deciding on the current element. This is because the number of remaining queries is at least halved at each add so, for a particular element, after 10 adds no more queries will occur. With knowledge of the previous 10 decisions, we can quickly compute the cost trade-off of adding the current integer to the cache:
This allows us to quickly compute all penalties associated with a cache add.