Home PageWeb BoardProblemsStandingStatusStatisticsAward 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

Problem ID Title
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]

Contest Report

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 Burnsides 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 wont 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 1s 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 1s is equal to the number of ordered pairs of vertices (i, j) such that there exists from vertex i to vertex j.

矩阵乘法不能解决这个题目。给出的矩阵A可以看作一个有向图的邻接矩阵。由于主对角线上的元素都是1,而且矩阵的阶小于2006,所以为A2006邻接矩阵的图就是由A表示的图的传递闭包。A2006中为1的元素个数就是所有从顶点i到顶点j存在一条路径的有序顶点对(i, 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 1s to the left and to the right of some element in a string of 0s and 1s. 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是偶数,交换行列。将初始状态和目标状态的木块上的数字按行优先顺序写下来变成两个整数序列。令I1I2为它们的逆序数,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