|Home Page||Web Board||Problems||Standing||Status||Statistics||Award Contest|
Contest - POJ Monthly--2006.07.30
Start time: 2006-07-30 12:00:00 End time: 2006-07-30 17:00:00
Current System Time: 2020-09-25 03:16:05.081 Contest Status: Ended
|2886 Problem A||Who Gets the Most Candies?|
|2887 Problem B||Big String|
|2888 Problem C||Magic Bracelet|
|2889 Problem D||Unique Solution|
|2890 Problem E||Matrix Multiplication|
|2891 Problem F||Strange Way to Express Integers|
|2892 Problem G||Tunnel Warfare|
|2893 Problem H||M × N Puzzle|
[Standings] [Status] [Statistics]
The following is based on solutions provided by the problem setters.
Problem A: Who Gets the Most Candies?
This problem is a variant of the Josephus problem which can be solved with segment tree. Let P be the largest antiprime not exceeding N. The P-th child jumping out of the circle is the answer. Distribution of antiprimes is sparse. All antiprimes required for this problem can be computed in advance and hard-coded into the source.
Problem B: Big String
There is an algorithm whose running time does not rely on the length of the initial string. Consider the inserted characters to be inserted into gaps between successive characters of the initial string. Before each insertion, keep all previous insertions in a table ordered by their positions. To insert a character before p-th character of the current string, start from the p-th character of the initial string and walk backward to find the right position for insertion, which can be found in at most N steps. Queries can be processed in a similar way. This algorithm runs in time O(N2).
Problem C: Bracelet
This is a constrained orbit-counting problem where Burnside’s lemma applies. The constraints can be represented by a directed graph. There is a edge from vertex i to vertex j if and only if beads of kind i and kind j can be stringed next to each other. Let A be the adjacency matrix. Then the answer is given by the expression below.
Problem D: Unique Solution
This problem is to determine whether there exists a unique set of M non-overlapping segments of consecutive elements of a sequence of N integers such that the sum of elements it covers is maximum. The algorithm is based on dynamic programming and recursion. First, use dynamic programming to build an M by N table of which the element in the i-th row and the j-th column is the maximum sum under the condition that the problem is limited to i segments on the first j elements and the j-th element is covered. Second, enumerate all possible last segments in the optimal set and use recursion to determine whether the set is unique.
Problem E: Matrix Multiplication
Matrix multiplication won’t do for this problem. The given matrix A can be regarded as the adjacency matrix of a directed graph. Since all elements on the primary diagonal are 1’s and the dimensions are less than 2006, the graph with A2006 as its adjacency matrix is the transitive closure of the graph represented by A. The number of elements that are 1’s is equal to the number of ordered pairs of vertices (i, j) such that there exists from vertex i to vertex j.
Problem F: Strange Way to Express Integers
Suppose C ≡ A1 (mod B1) and C ≡ A2 (mod B2). Let C = A1 + X1B1, we get X1B1 ≡ A2 − A1 (mod B2). Find X1 using the extended Euclidean algorithm and thus find C. Let B = lcm(B1, B2), then the two equations above can be replaced by C’ ≡ C (mod B). Iterate until there is only one equation.
假设C ≡ A1 (mod B1)，C ≡ A2 (mod B2)。令C = A1 + X1B，那么X1B1 ≡ A2 − A1 (mod B2)。用扩展欧几里德算法求出X1，也就求出C。令B = lcm(B1, B2)，那么上面两条方程就可以被C’ ≡ C (mod B)代替。迭代直到只剩下一条方程。
Problem G: Tunnel Warfare
Denote the unattacked or rebuilt villages with 0 and destroyed villages with 1, then the problem is reduced to finding the first 1’s to the left and to the right of some element in a string of 0’s and 1’s. Using a binary search tree or dividing the string into segments as long as the square root of the length of the string will solve the problem. Taking advantage of the condition that reconstruction was done in the reverse order of destruction, using a binary indexed tree will also do.
Problem H: M × N Puzzle
If N is even, transpose the puzzle. Write down the numbers on the tiles in both the starting and goal states (0 for the missing tile) in row-major order to form two sequences of integers. Let I1 and I2 be the numbers of inversions of the sequences and D be the Manhattan distance from the position of the missing tile in the starting state to that in the goal state. The puzzle is solvable if and only if I1 + I2 + D is even.
如果N是偶数，交换行列。将初始状态和目标状态的木块上的数字按行优先顺序写下来变成两个整数序列。令I1和I2为它们的逆序数，D为空位在初始状态和目标状态中位置的曼哈顿距离。游戏可解当且仅当I1 + I2 + D为偶数。
Home Page Go Back To top
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator