Contest - PKU Local 2007 (POJ Monthly--2007.04.28)

Start time:  2007-04-28 12:00:00  End time:  2007-04-28 17:00:00
Current System Time:  2024-04-25 12:55:34.675  Contest Status:   Ended

 Problem ID Title 3218 Problem A Alignments 3219 Problem B Binomial Coefficients 3220 Problem C Context-Free Languages 3221 Problem D Diamond Puzzle 3222 Problem E Edge Pairing 3223 Problem F Football Game 3224 Problem G Go for Lab Cup! 3225 Problem H Help with Intervals

[Standings]  [Status]  [Statistics]

 Contest Report Problem A: AlignmentsThe four alignments have to be handled separately. Possibly the most tricky point lies in the calculation of gap widths, which demands some care.Problem B: Binomial CoefficientsThe parity of C(n, k) can be determined by calculating the exponent of 2 in its factorization.Problem C: Context-Free LanguageAn efficient solution is based on dynamic programming. We first decide what variables each terminal in the string can be derived from using rules of the form A → a. When we have decided information about derivation for all substrings of length not longer than k, we can next decide that for all substrings of length k + 1 by trying to divide each of them into two parts to match the rules of the form A → BC. The string belongs to the language of the grammar if and only if it can be derived from the start symbol S.Problem D: Diamond PuzzleThe minimum numbers of steps required for every configuration of the puzzle can be precomputed by performing a (backward) breadth-first search from the final configuration and stored in a table. Rest of the job is merely table lookups.Problem E: Edge PairingA simple undirected graph with an even number of edges can always have its edges grouped into incident pairs. Below is a proof by construction.Let r be some vertex in the graph. We grow a depth-first search tree T rooted at r. Since the graph is connected, T actually spans every vertex. We then construct the pairing bottom up,  starting from the leaves. We mark all edges connecting a leave and its parent as unpaired. When working on some vertex x, we count how many unpaired edges connect x and its descendants. If the number of such edges is even, they will all be paired using x as the shared vertex, then the tree edge connecting x and its parent will be marked as unpaired; otherwise pairing fails leaving a single edge, which will be paired with that tree edge. The latter case never occurs with r. The reason is that when we work on r, all edges not connecting r and some of its descendants will have been paired, totaling to an even count. If at this moment pairing leaves a last unpaired edge, this would imply that the graph has an odd number of edges, contradicting the condition that the graph has an even number of edges.Problem F: Football GameLet’s first consider the simplified case where P is allowed to be anywhere on the straight line through UV.In the above figure, a circle through A and B touches UV at tangent point Q, which is to the right of R, the intersection of UV and the extension of BA. We claim thatfor any point P on the ray RQ, ∠APB ≤ ∠AQB; ∠APB is a convex function with respect to the position of P;∠APB reaches its maximum when P coincides with Q.These three lemmas allow the employment of the bisection method. And the method also works with the original case where the choice of P is restricted to between UV.Additionally, the tangent point Q can also be analytically determined taking advantage of the fact that Q is the projection of O, the center of the circle, on UV. Since O is equidistant to A, B and UV, it lies on the parabolas with A and B as the foci and UV as the common directrix, and therefore is one of their intersections. Finding O from the formulæ of parabolas requires only solving a univariate quadratic equation.Problem G: Go for Lab Cup!Intended as the easiest one, this problem requires only a straightforward implementation of its ideas.Problem H: Help with IntervalsEfficient representation and manipulation of the set S requires a subtle choice of data structure. Segment tree is one among possible ones. Each node in the tree stores information about membership in S of its corresponding interval, namely whether the interval completely, partially or do not belong to S and whether membership is inverted in this interval (used for quick handling of symmetric difference). Information stored in each node is carefully maintained in each operation. Finally the composition of S can be extracted from the tree.