Home Page | Web Board | Problems | Standing | Status | Statistics | Award Contest |

**Contest - POJ Monthly--2007.07.08**

Start time: 2007-07-08 12:00:00 End time: 2007-07-08 17:00:00

Current System Time: 2020-04-01 12:28:38.928 Contest Status:
Ended

Problem ID |
Title |

3242 Problem A |
3-dimensional Musical Water-fence |

3243 Problem B |
Clever Y |

3244 Problem C |
Difference between Triplets |

3245 Problem D |
Sequence Partitioning |

3246 Problem E |
Game |

3247 Problem F |
Robots |

3248 Problem G |
Soldier |

3249 Problem H |
Test for Job |

[Standings] [Status] [Statistics]

Contest Report |

Problem A: By real-life experience, the order of operations of pouring water will not affect the amount of water that flows out of the fence. Based on this fact, we can process the operations in any specific order. A clever choice of the order can greatly facilitate the simulation. In our reference solution, that order is the decreasing order by the highest levels water can reach above the squares which operations pour water upon. To further simplify the situation, contiguous squares with the same such highest levels can be grouped together. Then simulation starts, following the aforementioned order. Whenever any water flows out of the fence, it is accumulated so that the final answer is found. Problem B: This is essentially the problem of discrete logarithm. No efficient algorithm is known. The author suggests the following method. For the congruence equation K (mod Z), let L be some specially chosen constant, rewrite X as ^{Y}X = ^{Y}X · ^{uL}X, where ^{v}Y = uL + v (u, v ≥ 0, v < L). For each u = 0, 1, …, we try to determine whether there exists some v that satisfies the equation. And this is where the very hard part of the method lies. Let A = X and ^{uL}B = X, then equation is reduced to ^{v}AB ≡ K (mod Z). All possible values of B will be of the form pZ_{0} + q (0 ≤ q < Z_{0}), where Z_{0} is some divisor of Z. Therefore we can build a table to store the values of X mod ^{v}Z_{0} for every possible v and Z_{0} and use table look-ups to find the value of v.Problem C: The following identity gives the essential idea of the solution: With that, we can apply mapping Problem D: Performing bisection on the answer will reduce the problem to a new one that requires only to determine the feasibility of the value we guess, which is a little bit easier. The new problem can be solved using dynamic programming. We begin with a Problem E: Only points lying on the convex hull of all points are of interest. Each time we remove a point and fix the hull. Only the “damaged” portion of the hull has to be recomputed. The total time needed for all computations can be linear in a good implementation. Problem F: Each rotation can be represented by a square matrix. The combination of multiple rotations can be represented by the product of the rotations’ corresponding matrices. Since rotations are always applied to a contiguous portion of joints, segment trees can be used to speed up the algorithm. Problem G: If we rotate the chessboard by an angle of 45 degrees, the squares that a soldier controls will form a big square. Coloring the chessboard with two colors as in the following figure will show that squares of different colors being counted separately would make things simpler. Thus the problem is reduced to find the total area covered by multiple squares. But the existence of chessboard boundaries introduces some trouble. Therefore we employ an indirect approach. First all squares are counted with the boundaries neglected. Then squares lying outside the boundaries are counted. The difference of these two counts will be the answer. Finding the former count is easier. What is shown below presents a way to find the second count.
Problem We can use dynamic programming to find the longest path in a directed acyclic graph in linear time. |

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator