Home Page | Web Board | Problems | Standing | Status | Statistics | Award Contest |
Contest - POJ Founder Monthly Contest – 2008.03.16
Start time: 2008-03-16 12:00:00 End time: 2008-03-16 17:00:00
Current System Time: 2024-11-06 19:07:40.234 Contest Status:
Ended
Problem ID | Title |
3527 Problem A | Generalized Connect Four |
3528 Problem B | Ultimate Weapon |
3529 Problem C | Matrix Analysis |
3530 Problem D | A Modular Arithmetic Challenge |
3531 Problem E | Alternating Sum of Digits |
3532 Problem F | Resistance |
3533 Problem G | Light Switching Game |
3534 Problem H | Escape of Life and Death |
[Standings] [Status] [Statistics]
Contest Report | ||||||||||||||||||||||||||||||||||||||
Table of Contents
Problem A: Generalized Connect FourA naïve implementation of the negamax search is unlikely to pass all test cases within the time limit. A common and simple improvement to the negamax search is a technique called alpha-beta pruning. The alpha-beta search maintains two values, α and β, which represent the minimum score that the maximizing (next) player has been assured of so far and the maximum score that the minimizing (previous) player has been assured of at the same moment respectively. The initial values of α and β are the minimum and maximum possible scores respectively. Out of the nature of zero-sum games, α′ = −β and β′ = −α are passed as arguments in each recursive call to the search procedure, and the return value is negated as ρ to update α with the greater one of the two (thus making the alpha-beta window smaller). When α becomes greater than β during the search, the current position cannot be the result of the best play by both players because the minimizing player will not allow the maximizing player to achieve a higher score than β. At this point, pruning occurs as the current position is not further explored. In the optimal case, alpha-beta pruning can reduce the effective branching factor to its square root and thus allows the algorithm to search twice as deep with the same of amount of computation. Problem B: Ultimate WeaponThe continuous, closed and convex surface that encloses a set of points and has the smallest surface area is the convex hull of the points. There are many algorithms to construct three-dimensional convex hulls. Here only the incremental algorithm is described. Assuming the absence of degeneracy, the incremental algorithm works as follows.
Problem C: Matrix AnalysisDenote by βk the vector formed by concatenating the columns of Bk in order for each k ≥ 1. It is clear that there exists a mn × mn matrix A such that βk = Aβk−1 for each k > 1. This results in an O((mn)3 An alternative approach derives from the observation that for each given pair (i, j), the value of bijk is a polynomial function in k, i.e. , where δij is the order of the polynomial and cijt is the coefficient of kt. To compute the coefficients, we can first rewrite the given recurrence relation defining bijk as , then sum both sides over 2, 3, …, k, which gives . The two summations in parentheses above are in general of the form , where f(t) is a polynomial in t. Breaking f(t) into separate terms reduces the summation to the well-known problem of computing sum of powers, whose solution involves Bernoulli numbers. Problem D: A Modular Arithmetic ChallengeFor the sake of convenience, we shall first address those cases where there is no solution. Such cases are characterized by either trivially L > min{R, M − 1} or no multiple of gcd(M, D) falls between L and R (inclusive). For the rest of our discussion, we assume that the solution x exists and, without loss of generality, 0 ≤ L ≤ R < M. Instead of finding x directly, we first determine the value of Dx mod M, with which we can compute x later. If some multiple of D falls between L and R (inclusive), i.e. , it is evident that in this case. Otherwise, it must hold that Dk < L ≤ R < D(k + 1) where . In addition, under the assumption of existence of x, it must also hold that M mod D ≠ 0. Denote by x′ the solution to the instance of the problem with M′ = D, D′ = D − M mod D, L′= L mod D, R′ = R mod D. We then have Dx = Dk + D′x′ mod D. The value of D′x′ mod D can be found recursively. Once we have found the value of Dx mod M, we can use the extended Euclidean algorithm to compute x. Problem E: Alternating Sum of DigitsWe explain the solution using an example where K = 3 and N = 1011. First of all, we group all numbers from 1 to 1011 by their radix lengths into maximal groups whose sizes are powers of 3 except for the last group, as listed below.
In the list above, underlined digits are preceded by plus signs in the summation while the others are preceded by minus signs; digits in red are the common prefixes shared by numbers in the same group. Next, we will focus on summation within a single group. Summation within one group can be found by computing the sum over the common prefixes and that over the suffixes separately. Computing the former is intuitively easier since it has a regular pattern. To facilitate the computation of the latter, we break the suffixes of the numbers into individual digits and handle the digits by radix place. When listed in order, digits in each radix place of the suffixes of the numbers make up a sequence of the form (0x1x2x)y where x and y are powers of 3 (ak represents k consecutive occurrences of a; the parentheses indicate grouping). The pattern may be incomplete in the last group, but that should not be too difficult to address. Whether the digits in the sequence are preceded by alternating signs is decided by the radix length of the numbers. The sign before the leading 0 is decided by the total count of digits in previous groups and the radix place. Problem F: ResistanceTo compute the equivalent resistance measured between two designated junctions in a circuit of resistors, we can either connect the two junctions to the ends of a constant voltage source and compute the current across the circuit, or connect them to the ends of a constant current source and compute the potential difference between them. In either way, we establish a system of linear equations in voltages at the junctions and currents over the resistors according to Kirchhoff’s current law and Ohm’s law, which are quoted as follows.
Then we can use Gaussian elimination to solve the linear system. In the case of using a constant current source, the problem can be alternatively formulated as a convex cost flow problem. The circuit is regarded as an undirected flow network where the cost of an arc is defined as the heat generated by the current flowing through the corresponding resistor. We establish a flow of current on this network that generates the least heat and compute the equivalent resistance using the generated heat according to Joule’s first law. The successive shortest path algorithm for minimum (linear) cost flow still works, but special care has to be taken when computing the costs of augmenting paths since the cost of any arc is a quadratic function in the flow over it. Problem G: Light Switching GameBefore examining the game in a cube of arbitrary dimensions, we shall first analyze a simplified version where the cube is restricted to be of dimensions n × 1 × 1. We claim that a game with lights on in cells (x1, 1, 1), (x2, 1, 1), …, (xk, 1, 1) is equivalent to a game of Nim with k piles of chips containing x1, x2, …, xk chips respectively. This is because
Consequently, the nimber of the aforementioned game is x1 ⊕ x2 ⊕ ⋯ ⊕ xk, where ⊕ denotes nimber addition, which is effectively bitwise exclusive-or. Now we are ready to scrutinize the original game. Assume that the game has lights on in cells (x1, y1, z1), (x2, y2, z2), …, (xk, yk, zk). It remains valid to decompose the game into the sum of k sub-games each having a distinct light on. Less well-known, the nimber of any sub-game (x, y, z) can be written as x ⊗ y ⊗ z, where ⊗ denotes nimber multiplication. The set of nimbers, , in conjunction with nimber addition and multiplication, constitutes a field , with 0 and 1 as the additive and multiplicative identities respectively. To evaluate x ⊗ y, we can take advantage of the following two lemmas concerning Fermat 2-powers (numbers of the form 22n) in addition to the properties of the field :
The following example demonstrates how techniques are combined to evaluate 32 ⊗ 16:
Problem H: Escape of Life and DeathThe underlying model of this problem is the shortest path problem on direct acyclic graphs. After topologically sorting the vertices, one can compute the shortest path in linear time. References
|
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator